51考研网 > 考研备考 > 正文

2023计算机考研408数据结构知识:二叉排序树

计算机考研专业课,很多学校以408为主!接下来,小编为帮助备考2023计算机考研408的学子们,在头脑中有一个专业课思维框架,特意精心为大家整理出-计算机考研408数据结构知识:二叉排序树,供考生

计算机考研专业课,很多学校以408为主!接下来,小编为帮助备考2023计算机考研408的学子们,在头脑中有一个专业课思维框架,特意精心为大家整理出-计算机考研408数据结构知识:二叉排序树,供考生参考。

2023计算机考研408数据结构知识:二叉排序树

一、定义

左子树上所有结点的关键字小于根结点,右子树上所有结点的关键字大于根结点,左右子树又各是一颗二叉排序树,中序遍历可得到递增有序数列

二、查找

非递归实现,递归简单但效率低

三、插入

插入的新结点一定是某个叶结点(只有树为空的时候才会插入)

四、构造

即使插入元素相同,顺序不同时,构造的BST也不同

五、删除

叶结点: 直接删除

i只有一棵左/右子树: 让i的子树成为i父结点的子树,替代i位置

i有左右两棵子树: 令i的中序直接后继/前驱代替i,再删去直接后继/前驱,转换为1,2情况

六、查找效率分析

平均查找长度ASL=(每层个数*对应层数)/总个数

较坏情况: 类似有序单链表O(n)

较好情况: 平衡二叉树O(㏒₂n)

查找过程: 与二分查找类似,但二分查找的判定树唯一

综上是“2023计算机考研408数据结构知识:二叉排序树”,希望对计算机考研者们有所帮助!世界上唯一可以不劳而获的就是贫穷,唯一可以无中生有的是梦想。没有哪件事,不动手就可以实现。世界虽然残酷,但只要你愿意走,总会有路;看不到美好,是因为你没有坚持走下去。人生贵在行动,迟疑不决时,不妨先迈出小小一步。前进不必遗憾,若是美好,叫做精彩;若是糟糕,叫做经历!加油!

推荐阅读:

2023计算机考研408数据结构知识点总结

本页标签:

发表评论
0评