二叉搜索树-AVL树-红黑树

#二叉搜索树

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

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

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

（）

**解决办法：AVL平衡二叉树**

#AVL树（平衡二叉树）

**AVL树通过旋转（左旋/右旋）来保证排序树的平衡状态**

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

#红黑树

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

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

```java

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

```

**红黑树中结点的颜色**

```java

有两种结点颜色固定：

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

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

```

**红黑树保证平衡的规则**

```java

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

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

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

2.根节点一定是黑色的

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

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

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

```