文件名称：平衡二叉搜索树-cis_orcad 本地数据库配置方法
文件大小：5.89MB
文件格式：PDF
更新时间：2024-06-28 07:12:09
数据结构 邓俊辉
第7章 搜索树 §7.3 平衡事叉搜索树 220088 14 else { //若左右子树均存在，则选择v癿直接后继作为实际被摘除节点，为此需要 15 w = w->succ(); //（在右子树中）找刡*v癿直接后继*w 16 swap(v->data, w->data); //交换*v和*w癿数据元素 17 BinNodePosi(T) u = w->parent; 18 ((u == v) ? u->rChild : u->lChild) = succ = w->rChild; //隑离节点*w 19 } 20 hot = w->parent; //记弽实际被初除节点癿父亲 21 if (succ) succ->parent = hot; //幵将被初除节点癿接替者不hot相联 22 release(w->data); release(w); //释放被摘除节点 23 return succ; //迒回接替者 24 } 代码7.7 事叉搜索树removeAt()算法 效率 可见，删除操作所需时间主要消耗于对search()、succ()和updateHeightAbove() 的调用。这三个操作的共同之处是，在树中任一高度至多涉及一个节点，故在最坏情况下， 其总体的渐进时间复杂度不超过全树的高度。 §7.3 平衡二叉搜索树 7.3.1 树高与性能 根据7.2节对二叉搜索树的实现与分析，search()、insert()和remove()等主要接口 的运行时间，在最坏情况下均线性正比于二叉搜索树的高度。因此，若不能有效地控制树高， 则就实际的性能而言，二叉搜索树较之此前的向量和列表等数据结构将无法体现出明显优 势。比如在最坏情况下二叉搜索树可能彻底地退化为列表，此时的查找效率甚至会降至 O(n)，线性正比于树（列表）的规模。 那么，出现此类最坏或较坏情况的概率有多大？或者，从平均复杂度的角度看，二叉搜 索树的性能究竟如何呢？实际上，就这一问题而言“平均”一词的定义并不唯一。以下就按 照两种常用的随机统计口径，就二叉搜索树的平均性能做一分析和对比。 随机生成 不妨设各节点对应于n个互异关键码{e1, e2, ..., en}。于是按照每一排列 = (ei1, ei2, ..., ein)，只要从空树开始，反复调用insert()接口将各关键码依次插入，即可得 到这n个关键码的一棵二叉搜索树T()。与随机排列如此相对应的二叉搜索树T()，称作 由“随机生成”（randomly generated by）。 图7.8以三个关键码为例，给出了由各全排列生成的二叉搜索树。 图7.8 由三个兰键码{1, 2, 3}癿6种全排列生成癿事叉搜索树