二叉搜索树

左子节点< 根节点 < 右子节点

向二叉排序树添加6，5，7，3的过程

image

一般情况下，利用二叉排序树查找比链表查找要快，但是在特殊情况下，二叉排序树就失去了他的效果。（例如：插入8，7，6，5，4）

image

解决办法：AVL平衡二叉树

AVL树（平衡二叉树）

AVL树通过旋转（左旋/右旋）来保证排序树的平衡状态，AVL树会保证树的左右子树高度差始终是 <=1,AVL树达到的平衡状态是绝对平衡（左右子树的高度差<=1）

向平衡二叉树添加8，7，6，5，4的过程：

image

红黑树

定义：红黑树是实现了自平衡的二叉排序树，红黑树达到的是相对平衡状态，而不是绝对平衡状态。相对平衡时指左右子树的高度可以大于1（2，3，4...）。红黑树中所有节点的颜色要么是黑色要么是红色。

红黑树是怎样实现平衡状态的

通过旋转和调整结点的颜色，两种操作来保证树的平衡状态

红黑树中结点的颜色

有两种结点颜色固定：

1.根结点的颜色必然是黑色；

2.新添加的元素颜色一定是红色的，不过添加成功后，颜色可能会被改变。

红黑树保证平衡的规则

红黑树是通过旋转和该百年结点的颜色来保持平衡的

红黑树满足以下五大原则：

1.节点一定是红色或者黑色；

2.根节点一定是黑色的

3.所有叶子节点都是黑色的（叶子节点是NTL节点，为空）；

4.每个红色节点的两个子节点都是黑色（从每个叶子节点到根路径上不能有两个连续的红色节点） -- 红色节点不能连续出现

5.从任意一个节点到它的每个叶子节点所经历的简单路劲上包含黑色节点的个数相同

应用：TreeMap，它的实现就是红黑树