红黑树与AVL树

---

前言

红黑树与AVL树是数据结构中避不开的话题，也是面试中常问的问题。今天就把他们总结在一起。

一、AVL是什么？

向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。为什么高度差的绝对值不超过1而不是0呢？因为如果高度差的绝对值不超过0，那么二叉树就变成满二叉树了，因此绝对值不能超过1。这就引入了平衡二叉树的概念：

AVL树也是一种自平衡的二叉搜索树，它通过节点的平衡因子（左子树高度减去右子树高度）来保持树的平衡性。AVL树的平衡性维护主要通过旋转操作来实现。

二、AVL的插入与删除

插入

1、插入新节点时，按照二叉搜索树的规则将其插入到合适的位置。

2、自底向上遍历从插入节点到根节点的路径，更新每个节点的平衡因子。
3、如果某个节点的平衡因子超过了1或-1，表示树失去了平衡，需要进行旋转操作来恢复平衡。
a、如果插入节点在失衡节点的左子树的左子树中，进行右旋操作。
b、如果插入节点在失衡节点的右子树的右子树中，进行左旋操作。
c、如果插入节点在失衡节点的左子树的右子树中，先对失衡节点的左子树进行左旋操作，再对失衡节点进行右旋操作。
d、如果插入节点在失衡节点的右子树的左子树中，先对失衡节点的右子树进行右旋操作，再对失衡节点进行左旋操作。
重复步骤2和步骤3，直到达到根节点。

删除

删除节点时，按照二叉搜索树的规则找到要删除的节点。
如果要删除的节点是叶子节点或只有一个子节点，直接删除并调整平衡即可。
如果要删除的节点有两个子节点，可以选择前驱或后继节点来替代删除节点，然后删除前驱或后继节点，并调整平衡。

1、自底向上遍历从删除节点到根节点的路径，更新每个节点的平衡因子。
2、如果某个节点的平衡因子超过了1或-1，表示树失去了平衡，需要进行旋转操作来恢复平衡。
a、旋转操作的类型和步骤与插入节点时的旋转操作相同。
重复上面，直到达到根节点。

三、红黑树是什么

   学过二叉查找树的同学都知道，普通的二叉查找树在极端情况下可退化成链表，此时的增删查效率都会比较低下。为了避免这种情况，就出现了一些自平衡的查找树，比如 AVL，红黑树等。这些自平衡的查找树通过定义一些性质，将任意节点的左右子树高度差控制在规定范围内，以达到平衡状态。
1

红黑树主要有这五条性质。
1.节点不是红色就是黑色
2.根节点是黑色
3.叶子节点(NIL)为黑色
4.每个红色节点的两个子节点都是黑色。（(从每个叶子到根的所有路径上不能有两个连续的红色节点）
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

四、红黑树的插入与删除

插入

1. 初始时，根节点为黑色。
2. 插入新节点时，并将新节点插入为红色节点。
3. 如果插入节点的父节点是黑色，无需进行调整。
4. 如果插入节点的父节点是红色，那么需要进行调整以保持红黑树的性质。
   a. 如果插入节点的叔节点（父节点的兄弟节点）也是红色，那么将父节点和叔节点变为黑色，祖父节点变为红色，并以祖父节点为当前节点继续向上进行调整。
   b. 如果插入节点的叔节点是黑色或不存在，需要进行旋转和变色操作。
   i. 左旋或右旋操作：根据插入节点、父节点和祖父节点的相对位置进行旋转。旋转操作可以保持二叉搜索树的性质。
   ii. 变色操作：进行颜色的交换，使得父节点变为黑色，祖父节点变为红色。这样可以保持红黑树的黑高度不变。

删除

红黑树的删除操作相对比较复杂，因为删除一个节点可能会引发多种情况，需要仔细考虑旋转和颜色调整来维持红黑性质。以下是红黑树中执行删除操作的详细步骤，包括可能涉及的旋转和颜色调整。

删除操作的基本步骤：
找到要删除的节点： 首先，找到需要删除的目标节点。如果目标节点有两个子节点，可以选择它的后继节点（即右子树中最小的节点）来替代删除。
删除节点并用子节点替代： 删除目标节点，并用它的子节点（或者后继节点）来替代它的位置。

颜色调整和旋转： 在删除操作中，可能会导致红黑性质被破坏。以下是删除操作中可能需要考虑的情况：

删除节点为红色节点： 如果删除的节点是红色的，它不会破坏红黑性质。只需将它从树中移除即可。

删除节点为黑色节点： 删除的黑色节点可能会引发性质的破坏，需要进行颜色调整和旋转操作。

a. 删除节点有一个红色子节点： 如果删除的节点有一个红色子节点，用红色子节点替代删除节点，然后将子节点染成黑色，以保持黑高度性质。

b. 删除节点没有红色子节点： 如果删除的节点没有红色子节点，那么需要通过颜色调整和旋转来修复。

五、红黑树与AVL树的对比

红黑树（Red-Black Tree）和AVL树（Adelson-Velsky and Landis Tree）都是自平衡二叉搜索树，用于在动态数据集上进行高效的插入、删除和搜索操作。它们之间有一些相似之处，但也存在一些关键的区别。下面是红黑树和AVL树的比较：

平衡性：
红黑树：红黑树保证了一种弱平衡，即树的高度最多是2倍的对数级别。这使得红黑树在插入和删除操作时具有更高的灵活性，但可能导致一些操作稍微不如AVL树高效。
AVL树：AVL树是一种严格的平衡树，保证任何节点的左子树和右子树的高度差（平衡因子）不超过1。这确保了AVL树在平衡方面表现更好，但在插入和删除操作时可能需要更多的旋转来维持平衡。
插入和删除操作的性能：
红黑树：由于红黑树的平衡性要求相对较弱，插入和删除操作通常需要更少的旋转操作，因此在这些操作上性能可能比AVL树更好。
AVL树：AVL树的严格平衡性可能导致插入和删除操作需要更频繁的旋转操作，因此在这些操作上可能比红黑树略逊一筹。
搜索性能：

两者在搜索操作上都表现良好，因为它们都是二叉搜索树，保持了有序性。
存储空间：

红黑树：红黑树在维护平衡的同时，需要存储额外的颜色信息，因此通常比AVL树占用更少的存储空间。
AVL树：AVL树由于需要维护严格的平衡，可能需要更多的额外指针和信息，因此通常比红黑树占用更多的存储空间。
适用场景：
红黑树：适用于在插入和删除操作较频繁、搜索操作相对较少的场景，例如在数据库索引中。
AVL树：适用于搜索操作频繁、插入和删除操作相对较少的场景，以及对于对树的平衡性要求较高的场景。