http://www.sohu.com/a/201923614_466939

 

BST的特性：

　

在树上搜索就是二分查找的方法，查找的最大次数等于树的高度。

 BST树的缺陷：依次插入如下五个节点：7,6,5,4,3时，树会变得有一边很长。

平衡二叉树就是为了解决BST树的缺陷。有：RBT，B树

RBT（红黑树）：

特点：

1.根节点是黑色。

3.最后的叶子 结点的是黑色空结点（NIL节点）。

4 父子不同色

5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

插入：默认插入红色子结点；插入之后要修复

变色+旋转（左旋转用右替代，自己到左边，（它的左边和它本来右子结点的左边都挪到旋转之后左的下面）左左下，右右上；右旋转用左替代，自己到右边，右右下。左左上）　　

左旋：左旋转的时候把右子结点的左子结点扔过去，然后开始66——120这个杆开始逆时针转、

--------------------

 

 

 右旋的时候把左子节点的右子节点扔过去给66当左结点，然后杆66-50这个杆开始顺时针旋转一直到50为最高结点：

------------------------