关于平衡二叉树的原理
平衡二叉排序树是
1、左子树与右子树的高度之差的绝对值小于等于1
2、左子树和右子树也是平衡二叉排序树
那么如何维持一棵平衡二叉排序树呢？原理又是什么呢？
LL型平衡二叉排序树的证明， LR, RR,RL与之同理
设 Bh 为二叉树左子树高， Ar 为A右子树高，BL为B的左子树，BR为B的右子树S为新加的节点
Bh - Ar = 2
Bh = Bl + 1(B) + 1(S)
Bl + 2 - Ar = 2
Bl = Ar
Bl + 1(S) = Ar + 1(A)//B的原左子树加上S后的高度 = A的右子树的高度加上A节点