实际上我们可以这样归结问题： ·空树或者只有一个节点的树，一定是平衡的： ·假设树T是平衡的： ·树上增加一个节点（因为是BST所以一定是叶节点） ·可能仍然平衡，ok ·如果不平衡： ·寻找包含该节点的最小的不平衡子树，通过旋转使之平衡 ·两种情况下简单旋转即可实现，另外两种情况，两次旋转即可 ·继续寻找，直至不存在不平衡（子）树 ·新树是平衡的
实际上我们可以这样归结问题： • 空树或者只有一个节点的树，一定是平衡的； • 假设树T是平衡的； • 树上增加一个节点(因为是BST,所以一定是叶节点) • 可能仍然平衡，ok • 如果不平衡： • 寻找包含该节点的最小的不平衡子树，通过旋转使之平衡 • 两种情况下简单旋转即可实现，另外两种情况，两次旋转即可 • 继续寻找，直至不存在不平衡(子)树 • 新树是平衡的
红黑树是一种什么样的实现方式？ ·红黑树一定是平衡的吗？ ·近似平衡：黑高相等，路径长度最多是两倍 ·但性能依然足够好：gn ·红黑树的维持关键 ·Insert和delete ·红黑树的5个性质 ·两种色彩；根为黑色；叶(i为黑色；红节点的子女为黑色；黑高相等 ·同一条路径上两个节点颜色红黑交换 ·有颜色交换的树的旋转
红黑树是一种什么样的实现方式？ • 红黑树一定是平衡的吗？ • 近似平衡：黑高相等，路径长度最多是两倍 • 但性能依然足够好：lgn • 红黑树的维持关键 • Insert和delete • 红黑树的5个性质 • 两种色彩；根为黑色；叶(nil)为黑色；红节点的子女为黑色；黑高相等 • 同一条路径上两个节点颜色红黑交换 • 有颜色交换的树的旋转