【数据结构】红黑树基础
发布时间:2020-12-15 05:59:01 所属栏目:安全 来源:网络整理
导读:1、红黑树 红黑树是一种自平衡二叉搜索树,在实际应用中有很广泛的用途。 STL 中的 set,multiset,map,multimap 的底层均是由红黑树实现的。 红黑树有一下 4 个特性: (根据后面的例子看以下几个特性) 1 、红黑树中的每一个节点不是黑色就是红色; 2 、根节
1、红黑树
红黑树是一种自平衡二叉搜索树,在实际应用中有很广泛的用途。STL中的set,multiset,map,multimap的底层均是由红黑树实现的。
红黑树有一下4个特性:(根据后面的例子看以下几个特性) 1、红黑树中的每一个节点不是黑色就是红色; 2、根节点(root)和叶子(叶子节点的孩子节点NIL)是黑色的; 3、如果一个节点为红色,那么它的父节点一定是黑色的; 4、从任何节点出发到叶子的路径经过的黑色节点数目必定相等(树黑色高度相等)。 上述4个特性是红黑树必须要满足的条件。
2、为什么能保持红黑树的平衡
一个有n个结点的红黑树的树高h满足: h≤2lg(n+1) 下面来简单证明:
3、红黑树的元素插入
红黑树的元素插入过程:想将待插入的元素标记为红色,将元素插入到合适的位置。按照规则改变节点的颜色,适当的旋转树结构。针对上述红黑树,假设插入元素15,分析插入过程。
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |