红黑树相对于普通平衡二叉树的优点 |
您所在的位置:网站首页 › 红黑树的高度包括叶子结点吗对吗 › 红黑树相对于普通平衡二叉树的优点 |
黑树属于平衡二叉树。它不严格是因为它不是严格控制左、右子树高度或节点数之差小于等于1,但红黑树高度依然是平均log(n),且最坏情况高度不会超过2log(n)。 红黑树(red-black tree) 是一棵满足下述性质的二叉查找树: 1. 每一个结点要么是红色,要么是黑色。 2. 根结点是黑色的。 3. 所有叶子结点都是黑色的(实际上都是Null指针,下图用NIL表示)。叶子结点不包含任何关键字信息,所有查询关键字都在非终结点上。 4. 每个红色结点的两个子节点必须是黑色的。换句话说:从每个叶子到根的所有路径上不能有两个连续的红色结点 5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点 红黑树相关定理 1. 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。 根据上面的性质5我们知道上图的红黑树每条路径上都是3个黑结点。因此最短路径长度为2(没有红结点的路径)。再根据性质4(两个红结点不能相连)和性质1,2(叶子和根必须是黑结点)。那么我们可以得出:一条具有3个黑结点的路径上最多只能有2个红结点(红黑间隔存在)。也就是说黑深度为2(根结点也是黑色)的红黑树最长路径为4,最短路径为2。从这一点我们可以看出红黑树是 大致平衡的。 (当然比平衡二叉树要差一些,AVL的平衡因子最多为1) 红黑树的树高(h)不大于两倍的红黑树的黑深度(bd),即h=2^bd’-1,将这两个不等式相加有nl+nr>=2^(bd’+1)-2,将该不等式左右加1,得到n>=2^(bd’+1)-1,很显然bd’+1>=bd,于是前面的不等式可以 变为n>=2^bd-1,这样就证明了一颗有n个内部结点的红黑树满足n>=2^bd-1。 在根据定理2,h=2^(h/2)-1,那么h |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |