未完待续..（例题代码什么的再补）

如果树中节点的数量为 n，则一棵满足O($log_2{n}$) 渐进运行时间的树的高度应接近于比$log_2{n}$小的最大整数。
对于一棵二叉查找树，往往不能事先知道所有的数据从而并不能保证树的形状合适，例如在不断输入数据并且不断查询的情况下。
如果我们能实时调整树使其满足最高效率的形状就好了。为此我们有自平衡二叉查找树。
有多种自平衡结构，如AVL树、红黑树、2-3树、2-3-4树、伸展树、B树等等。

首先是节点具有颜色：红、黑二色；其次是存在一种NIL节点，作为伪叶子节点连接着内点。 满足性质：

1. 根节点是黑色
2. NIL节点是黑色
3. 如果节点的颜色是红色，则其子节点均为黑色
4. 从任一节点到其后代任一叶子节点的路径上的黑色节点的数量相同

按照BST的插入方式在计算出的位置插入一个红节点。设该节点为K，父节点为P,P父节点为G，P的兄弟节点为S。
1.若P为黑色，则符合红黑树的性质，不需要做改动。
2.若P为红色:
$\quad\quad $2a.若S是黑色或为空，则需要进行旋转，分为四种情况，前两种情况是P是G的左孩子，后两种情况为P是右孩子。


$\quad\quad $2b.若S是红色，则需要对P、S、G重新着色：将P和S着色为黑色，将G着色为红色。

这样的重新着色不会影响G及以下的性质，但可能出现G与其父节点同红的情况，此时需要遵循上述方式向上递归地进行调整。

对于每一个节点，其左右子树的高度差不超过1。

按照二叉查找树