实际上我们可以这样归结问题： ·空树或者只有一个节点的树，一定是平衡的： ·假设树T是平衡的： ·树上增加一个节点（因为是BST所以一定是叶节点） ·可能仍然平衡，ok ·如果不平衡： ·寻找包含该节点的最小的不平衡子树，通过旋转使之平衡 ·两种情况下简单旋转即可实现，另外两种情况，两次旋转即可 ·继续寻找，直至不存在不平衡（子）树 ·新树是平衡的实际上我们可以这样归结问题： • 空树或者只有一个节点的树，一定是平衡的； • 假设树T是平衡的； • 树上增加一个节点(因为是BST,所以一定是叶节点) • 可能仍然平衡，ok • 如果不平衡： • 寻找包含该节点的最小的不平衡子树，通过旋转使之平衡 • 两种情况下简单旋转即可实现，另外两种情况，两次旋转即可 • 继续寻找，直至不存在不平衡(子)树 • 新树是平衡的