二叉查找树

二叉查找树，又称二叉树或者二叉搜索树

特点：每一个节点上最多又两个子节点

任意节点左子树上的值都小于当前节点 

任意节点右子树上的值都大于当前节点

二叉查找树添加节点：规则

小的存左边

大的存右边

一样的不存

平衡二叉树（规则）

任意节点左右子树高度差不超过1

旋转机制

规则1:左旋

规则2:右旋

触发机制：当添加一个节点之后，该树 不再是一颗平衡二叉树

左旋：确定支点：从添加的节点开始，不断的往父节点找不平衡的节点

步骤：以不平衡的点作为支点，把支点左旋降级，变成左子节点，晋升原来的右子节点

平衡二叉树需要旋转的四种情况

1.左左               一次右旋

2.左右               先局部左旋，，再整体右旋

3.右右               一次左旋

4.右左               先局部右旋，再整体左旋

红黑树

红黑树是一种自平衡的二叉查找树，是计算机科学中用到的一种数据结构

是特殊的二叉查找树，红黑树的每一个节点上都有存储位表示节点的颜色

每一个节点可以是红或者黑；红黑树不是高度平衡的，它的平衡是通过“红黑规则”进行实现的

红黑规则：

1.每一个节点是红色的，或者黑色的

2.根节点必须是黑色

3.如果一个节点没有字节的或者父节点，则该节点相应的指针属性值为Nil，这个Nil视为叶节点，每个叶节点Nil是黑色的

4.如果某一个节点是红色，那么它的子节点必须是黑色（不能出现两个红色节点相连的情况）

5.对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同的黑色节点

默认颜色：添加节点默认是红色的（效率高）