二叉排序树的查找序列_二叉排序树查找的时间复杂度

二叉排序树的查找序列_二叉排序树查找的时间复杂度8.3.1 二叉排序树返回目录:Chilan Yu:《数据结构》目录链接1. 二叉排序树定义与描述二叉排序树(二叉查找树),它是一种特殊结构的二叉树。其定义为:二叉树排序树或者是一棵空树,或者是具有如下性

8.3.1 二叉排序树   返回目录:   Chilan Yu:《数据结构》目录链接   1. 二叉排序树定义与描述   二叉排序树(二叉查找树),它是一种特殊结构的二叉树。   其定义为:二叉树排序树或者是一棵空树,或者是具有如下性质的二叉树: (1)若它的左子树非空,则左子树上所有结点的值均小于根结点的值; (2)若它的右子树非空,则右子树上所有结点的值均大于(或大于等于)根结点的值; (3)它的左右子树也分别为二叉排序树   由定义可以得出二叉排序树的一个重要性质:中序遍历一个二叉排序树时可以得到一个递增有序序列。   2. 二叉排序树的插入与创建   (1)二叉排序树的插入   【算法思想】   已知一个关键字值为Key的结点s,插入的方法: ①若二叉排序树是空树,则Key 成为二叉排序树的根; ②若二叉树排序树非空,则将key与二叉树排序树的根进行比较: a. 如果key的值等于根结点的值,则停止插入。 b. 如果key的值小于根结点的值,则将key插入左子树。 c. 如果key的值大于根结点的值,则将key插入右子树。   二叉排序树的插入算法的时间复杂度是
O(log_2n)   (2)创建二叉排序树   【算法思想】   首先,将二叉排序树初始化为一棵空树,然后逐个读入素,每读入一个素,就建立一个新的结点,并插入到当前已生成的二叉排序树中,即通过多次调用二叉排序树的插入新结点的算法实现,注意插入时比较结点的顺序始终是从二叉排序树的根结点开始。   二叉排序树的插入与创建小结   3. 二叉排序树的查找   【算法思想】   首先将待查关键字key与根结点关键字t进行比较,如果: (1)k=t:则返回根结点地址;(2)k<t:则进一步查左子树; (3)k>t:则进一步查右子树。   (1)二叉排序树查找的递归算法   其中用Layer计层数。   (2)二叉排序树查找的非递归算法   其中用Layer计层数。   小结   二叉排序树的查找完整代码:   4. 二叉排序树的删除   从二叉排序树中删除一个结点,必须保证删除后所得的二叉树仍然满足二叉排序树的性质不变。   【算法思想】   首先确定被删除的结点是否在二叉排序树中。若不在 ,则不做任何操作;否则,假设要删除的结点为p,结点p的双亲结点为f,并假设结点p是结点f的左孩子(右孩子的情况类似)。   下面分三种情况讨论: (1)若p为叶结点,则可直接将其删除: (2)若p结点只有左子树,或只有右子树,则可将p的左子树或右子树直接改为其双亲结点f的左子树。即: (3)若p既有左子树,又有右子树, 如下图(a),则处理的方法有两种:
二叉排序树的查找序列_二叉排序树查找的时间复杂度
二叉排序树的查找序列_二叉排序树查找的时间复杂度   方法一:首先找到p结点在中序序列中的直接前驱s结点,如图 (b) 所示,然后将p的左子树改为f的左子树,而将p的右子树改为s的右子树:结果如图 (c) 所示。
二叉排序树的查找序列_二叉排序树查找的时间复杂度
二叉排序树的查找序列_二叉排序树查找的时间复杂度   方法二:首先找到p结点在中序序列中的直接前驱s结点,如图 (b) 所示,然后用s结点的值,替代p结点的值,再将s结点删除,原s结点的左子树改为s的双亲结点q的右子树:结果如图 (d) 所示。
二叉排序树的查找序列_二叉排序树查找的时间复杂度
二叉排序树的查找序列_二叉排序树查找的时间复杂度   小结   二叉排序树的删除完整代码:   5. 二叉排序树的特性   对于二叉排序树,若中序遍历,则可以得到一个递增有序序列。 若逆中序遍历(RDL),则可以得到一个递减有序序列。   返回目录:   Chilan Yu:《数据结构》目录链接

2024最新激活全家桶教程,稳定运行到2099年,请移步至置顶文章:https://sigusoft.com/99576.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处:https://sigusoft.com/66135.html

(0)
上一篇 2024年 8月 9日
下一篇 2024年 8月 9日

相关推荐

关注微信