南京大学：《计算机问题求解》课程教学资源（PPT课件讲稿）红黑树

红黑树 一种重要的平衡二叉搜索树实现方法 陶先平

红黑树 一种重要的平衡二叉搜索树实现方法 陶先平

平衡二叉搜索树 我们有没有简单的方法得到一棵相对“平衡的”二叉搜索树？ 哪些因素可能会导致二叉搜索树的不平衡？

平衡二叉搜索树 哪些因素可能会导致二叉搜索树的不平衡？ 我们有没有简单的方法得到一棵相对“平衡的”二叉搜索树？

平衡二叉树的本质含义： ·当以节点n为根时，若定义Lson(n)为n的左子树，定义Rson(n)为n 的右子树，当该树满足以下条件时，称该树为平衡二叉树： IH(Lson(n)》-H(Rson(n)川<=1，其中H(m)指以m为根的树的高度，m=nil 时H(m)=0 ·因此，维护平衡性只要做到： ·判断哪个子树“超”高了 ·记录高度 ·通过旋转降低高度

平衡二叉树的本质含义： • 当以节点n为根时，若定义Lson(n)为n的左子树，定义Rson(n)为n 的右子树，当该树满足以下条件时，称该树为平衡二叉树： |H(Lson(n))-H(Rson(n))|<=1,其中H(m)指以m为根的树的高度，m=nil 时H(m)=0 • 因此，维护平衡性只要做到： • 判断哪个子树“超”高了 • 记录高度 • 通过旋转降低高度

左/右旋转的同时保持二叉搜索性质 LEFT-ROTATE(T.x) 051111111111111i11n RIGHT-ROTATE(T,y) B B Y 以左转为例，新树平衡了吗？

左/右旋转的同时保持二叉搜索性质 以左转为例，新树平衡了吗？

新树平衡了 50 50 25 15 15 5

50 15 10 25 20 30 40 25 40 15 10 30 50 20 新树平衡了

新树仍然不平衡 50 50 25 15

50 15 10 25 20 40 17 25 15 40 10 50 20 17 新树仍然不平衡

这个问题有多严重呢？ B E G G G X V X 四种基本模型：有且仅有

这个问题有多严重呢？ A F B C G D E A F B C G D E A F B C G D E A F B C G D E X √ √ X 四种基本模型：有且仅有

所以，问题的焦点在于以下结构 F和G存在一个或者两个同时存在，一次旋转已经解决不了问题

所以，问题的焦点在于以下结构 A F B C G D E F和G存在一个或者两个同时存在，一次旋转已经解决不了问题 A F B C G E D

所以，问题的焦点在于以下结构 D E 通过两次旋转！ 以A的右子树根为中心，右旋：未加剧高差！ 以A为中心，左旋，平衡！

所以，问题的焦点在于以下结构 A F B C G D E 通过两次旋转！ F A B C G E D A E B D G F C 以A的右子树根为中心，右旋：未加剧高差！ 以A为中心，左旋，平衡！

两次旋转得到新平衡树 50 50 50 平衡 非平衡 非平衡 15 15 20 25 25

50 15 10 25 20 40 17 两次旋转得到新平衡树 非平衡 50 15 10 20 25 40 17 非平衡 50 15 10 20 25 17 40 平衡