【数据结构】树

之前我们已经学了数组和链表。它们是 Arraylist 和 LinkedList 的底层结构。

集合命名和数据结构的关系：

1. **二叉树

这是一个普通二叉树。

• 节点：每一个圆就是一个节点
• 根节点：最顶层的节点，该二叉树为 9
• 度：每一节点的子节点数量（二叉树要求任意节点的度<=2）
• 树高：树的总层数，该二叉树为 4
• 左子节点：左下方的节点
• 右子节点：右下方的节点
• 根节点的左子树：紫线
• 根节点的右子树：蓝线

注意别的节点也可以有子树

节点的内部结构：

由于普通二叉树排序无规律，查找数据时效率慢，
因此有了二叉查找树（又称二叉排序树或者二叉搜索树）

**2. 二叉查找树：

特点：

• 每一个节点上最多有两个子节点（因为还是二叉树）
• 任意节点左子树上的值都小于当前节点
• 任意节点右子树上的值都大于当前节点

3. **二叉树的遍历：

前序遍历：

从根节点开始，然后按照当前节点，左子节点，右子节点的顺序遍历

中序遍历：

从最左边的子节点开始，然后按照左子结点，当前结点，右子结点的顺序遍历

后序遍历：

左子节点–>右子结点 --> 当前节点

举例：

层序遍历：

一层一层的去遍历

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

4. **平衡二叉树

查找二叉树的弊端：可能出现长短腿的情况，退化成链表了

这时就有了平衡二叉树:

平衡二叉树的规则：

前提是二叉查找树

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

下面这个二叉树就违背了规则

5.** 二叉树的演变

6. 平衡二叉树是如何保持平衡的？

平衡二叉树的旋转级制：

1. 左旋
2. 右旋

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

左旋：

步骤：

如：当添加 12 后不再是平衡二叉树 向上找到不平衡节点 10（右子树高 2，左子树高 0，高差超过 1） 将 10 作为支点，左旋完得：

特殊情况：
步骤：

此时 7 为不平衡节点，将其作为支点左旋

右旋：

步骤：

如：添加 1 后为不平衡， 先找到不平衡点 4， 作为支点右旋

特殊情况：
步骤：

添加完 1 后不平衡，7 为不平衡点，并作为支点，右旋，

**触发时机：**当添加一个节点后，该树不再是一颗平衡二叉树 又具体分为以下几种：

左左：一次右旋解决
左右：先局部左旋，再找支点右旋
右右：一次左旋解决
右左：先局部右旋 ，再找支点左旋

根节点的左子树

根节点的左子树得左子树

此时添加 1，不平衡了

此时 7 是不平衡点，作为支点，右旋

得：

我们在根节点左子树的右子树上添加 6

先不找平衡点，先将局部左旋

再整体右旋得：

7 为不平衡点，作为支点，直接左旋得

先局部右旋：得

再找平衡点 7，作为支点，左旋得：

7. 平衡二叉树小结：

1. 小的放左，大的放右，重复不放
2. 小的在左，大的在右
3. 为了平衡，提升查找效率
4. 当添加节点后 二叉树某一节点的左右子树高差大于 1
5. 根节点的左子树的左子树有节点插入，导致不平衡。一次右旋
6. 根节点的左子树的右子树有节点插入，导致不平衡。局部左旋，再整体右旋
7. 根节点的右子树的右子树有节点插入，导致不平衡。一次左旋
8. 根节点的右子树的左子树有节点插入，导致不平衡。局部右旋，再整体左旋

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

8. 红黑树：

为什么要有红黑树？
频繁的旋转操作使平衡二叉树的性能大打折扣

• 是一种自平衡的二叉查找树，又叫平衡二叉B树。
• 节点可以是红色或黑色
• 红黑树不是高度平衡的，它的平衡是通过**“红黑规则”**进行实现的

和平衡二叉树的区别：

红黑规则：

1. 每个节点必须是黑色或红色
2. 根节点一定是黑色
3. ** Nil 视为 叶子节点**，黑色

引用：
Nil：NIL节点也称为外部节点或空节点，NIL节点不存储实际的数据，如果一个节点没有左子节点或右子节点，那么它的对应子节点就是一个NIL节点。通过将红黑树的所有叶子节点都替换为NIL节点，我们可以保证红黑树的每个节点都至少有一个子节点。这样，我们就可以通过判断节点的子节点是否为NIL节点来处理边界情况，避免了在处理节点时需要特殊处理叶子节点的情况。

4. 不能出现两个红色节点相连的情况
5. 对每一个节点，从该节点到其 所有后代 叶节点的简单路径上（不可倒回），均包含相同数目的黑色节点；

如 17->15>Nil 和 17->25->22->Nil 均为两个黑色节点

下面这个就违背了规则 5

红黑树节点结构：

添加节点默认是红色（因为效率高）

如，
若添加黑色 值为 18 的节点，就违背了规则 5

若：
添加 红色 18 节点，直接可构成红黑树

（红黑树）添加节点的规则：

红黑树增删改查的性能都很好