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