红黑树 一种重要的平衡二叉搜索树实现方法 陶先平
红黑树 一种重要的平衡二叉搜索树实现方法 陶先平
平衡二叉搜索树 我们有没有简单的方法得到一棵相对“平衡的”二叉搜索树？ 哪些因素可能会导致二叉搜索树的不平衡？
平衡二叉搜索树 哪些因素可能会导致二叉搜索树的不平衡？ 我们有没有简单的方法得到一棵相对“平衡的”二叉搜索树？
平衡二叉树的本质含义： ·当以节点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 新树平衡了