平衡树

平衡树(Balance Tree，BT)

即平衡二叉树
它是一个空树或它的左右两个子树的
高度差的绝对值不超过1
并且左右两个子树都是一棵平衡二叉树

平衡二叉树的常用算法有

• 红黑树
• AVL
• Treap
• 伸展树
• SBT

最小二叉平衡树的节点的公式如下:
F(n) = F(n-1) + F(n-2) + 1;

可以参考Fibonacci数列
1是根节点，
F(n-1)是左子树的节点数量
F(n-2)是右子树的节点数量