数据结构与算法 7. 二叉搜索树 2021-07-24 浏览量 519 暂无评论 [TOC] ## 7.1 概述 借鉴了列表的特点，又借鉴了有序向量的特点（质的提高）。 BST的优势集中体现在一个子集--平衡二叉搜索树BBST - 定义 - 特点 - 接口 ### 循关键码访问--call-by-key 数据项之间，依照各自的关键码区分。 **条件**：大小比较 + 相等比对 **词条**  ### 有序性 节点 ~ 词条 ~ 关键码（等效） 任一节点均不小于/不大于其左/右后代  ### 单调性 局部有序性 -> 单调性（中序遍历--二叉树垂直投影） 这也是二叉树为BST的充要条件。 ### 接口  虚函数： - 派生类重载基类的虚函数后，指向派生类的基类指针`human* test = new man("dd");`可以调用派生类的虚函数，因为派生类的虚函数表中对应的函数地址已替换为重载后的函数地址；如果派生类重载了基类的普通函数，那么指向派生类的基类指针只能调用基类的普通函数 - 地址存在虚函数表中，每个含有虚函数的类都有一个虚函数表指针，指向该类的虚函数表 - 含有纯虚函数`virtual 返回值类型 函数名字(参数) = 0`的类不能实例化，称作抽象类。 ## 7.2 查找 减而治之，类似有序向量的二分查找。**共性**：存在某一部分整体不大于某数，另一部分整体不小于该数。 ```cpp template <typename T> BinNodePosi(T) & BST<T>::search(const T & e) { return searchIn(_root, e, hot = NULL); } static BinNodePosi(T) & searchIn( BinNodePosi(T) & v, const T & e, BinNodePosi(T) & hot) { if (!v || (e == v->data)) return v; // 记录当前非空的节点 hot = v; return searchIn(((e < v->data) ? v->lChild : v->rChild), e, hot); } ``` **时间复杂度**：$O(h)$ **语义**：成功时，返回命中的真实存在的节点；失败时，返回假想的命中节点（空节点），这样，_hot就总是指向命中节点的父亲。 ## 7.3 插入 <font color='red'>假设不存在重复词条</font> 先调用`search(e)`找到应该插入的位置的节点的引用，再将值赋给该引用。 ```cpp template <typename T> BinNodePosi(T) BST<T>::insert(const T & e) { BinNodePosi(T) & x = search(e); if (!x) { x = new BinNode<T>(e, _hot); _size++; updateHeightAbove(x); } return x; } ``` 时间复杂度：$O(h)$ ## 7.4 删除 当只有一个孩子时，直接用这个孩子替换； 当左右孩子都存在时，**化繁为简**，找到要删除节点的后继（中序遍历的下一个节点），交换，再删除。 ```cpp template <typename T> bool BST<T>::remove(const T & e) { BinNodePosi(T) & x = search(e); if (!x) return false; removeAt(x, _hot); _size--; updateHeightAbove(_hot); return true; } template <typename T> static BinNodePosi(T) removeAt(BinNodePosi(T) & x, BinNodePosi(T) & hot) { BinNodePosi(T) w = x; BinNodePosi(T) succ = NULL; // 其实这里也处理了同时有左右孩子时的左孩子 if (!HasLChild(*x)) succ = x = x->rChild; else if (!HasRChild(*x)) succ = x = x->lChild; // 能不能将右子树接到左子树的最右端呢？ else { w = w->succ(); swap(x->data, w->data); BinNodePosi(T) u = w->parent; (u == x ? u->rChild : u->lChild) = w->rChild; } hot = w->parent; if (succ) succ->parent = hot; release(w->data); release(w); return succ; } ``` 时间复杂度取决于succ()，不会超过$O(h)$ ## 7.5 平衡与等价 二叉搜索树本意是要结合向量与列表的优点，即查找地快、插入/删除地快，而目前，最坏的时间复杂度都为$O(h)$。 考虑退化的情况，所有节点的度不超过1，树退化为单链，最坏情况时间复杂度均变为$O(N)$。 ### 随机生成 n个节点，可以有n!种排列 平均高度为$O(log(n))$，有重复计算的情况。 ### 随机组成 n个节点，可以有catalan(n)种，即互异BST树的数量，也是拓扑互异的二叉树的数量。 $C_{n+1}=C_0C_n+C_1C_{n-1}+...+C_nC_0$，前几项为$1, 1, 2, 5$ 平均高度为$O(\sqrt{n})$，更符合实际，但比随机生成的高度更高。 ### 什么样的树高度更低呢？ - 节点数目固定时，兄弟子树高度越接近平衡，全树也将倾向于更低 - 由n个节点 组成的二叉树，高度不低于$\lfloor log_2n \rfloor$--恰为$\lfloor log_2n \rfloor$时，称作理想平衡。 完全二叉树、满二叉树满足理想平衡，但不切实际。 退一步，只要渐进地不超过$O(logn)$就行了，叫适度平衡。 拓扑结构不同，但中序遍历相同的BST，称作等价BST。 ### 等价变换 zig, zag  ## 7.6 AVL树--重平衡 ### 平衡因子 节点左子树与右子树高度之差 若对任意节点，平衡因子绝对值均小于等于1，则称为AVL树。 ### 适度平衡  ### 接口  ### 失衡 + 复衡 插入一节点后，可能引起一系列祖先高度变化； 删除一节点后，只会引起一个高度最低祖先高度变化。 **疑问**：在例子中，如果删除节点N+，那一系列祖先的高度不就都变化了吗？ <font color='red'>纠正：不是高度，是平衡性</font>  ## 7.7 插入 ### 单旋 p的左子树变为g的右子树，g变为p的左子树，祖父变为p 包含gpv节点的子树高度不变。 zagzag：gpv斜向右下 zigzig：gpv斜向左下  ### 双旋 zigzag 两轮旋转 先对p进行zig，再对g进行zag，最终把v提到最高，gp等高。 包含gpv节点的子树高度不变。  ### 实现  ## 7.8 删除 ### 单旋 只做一次旋转 包含gpv节点的子树高度可能变化。  ## 双旋  ## 实现  # 7.9 (3+4)重构 观察上面插入和删除后重平衡的BBST，发现都是3个节点加4个子树，并且拓扑结构一致，并且等价变换后中序遍历一样，那可以直接将该3个节点和4个子树拼接起来。  确定abc，T0~T3的顺序。   赞赏 微信支付 支付宝支付
