红黑树 | BRUCE

红黑树的代码实现：https://github.com/brucewayne9064/Algorithms/blob/main/MyRBTree.java

一、二叉搜索树（binary search tree）

什么是二叉搜索树

BST称为二分搜索树、二叉查找树、二叉搜索树、有序二叉树或排序二叉树。满足以下几个条件：

若它的左子树不为空，左子树上所有节点的值都小于它的根节点。
若它的右子树不为空，右子树上所有的节点的值都大于它的根节点。

它的左、右子树也都是二分搜索树。

时间复杂度

查找操作（插入操作的复杂度相同，插入本身复杂度为$O(1)$）：

最好情况：当bst是平衡的时候（树的每个节点的左右子树高度差不超过1），查询的时间复杂度为$O(log_2(N))$。
最坏情况：BST退化成链表，查询的时间复杂度为$O(N)$。

总结

建立在BST的基础上，AVL，红黑树都属于自平衡的二叉搜索树。AVL树通过平衡因子（左子树高度和右子树高度的差值）来维持平衡，并通过旋转操作来调整树的结构。红黑树通过给节点赋予颜色（红或黑）并维护一系列红黑树性质来保持平衡。

AVL树更适合查找操作非常频繁的场景，因为它们的高度平衡保证了更快的查找时间。
红黑树更适合插入和删除操作非常频繁的场景，因为它们在这些操作上的性能开销更小。

二、平衡二叉树（AVL）

什么是AVL树

平衡二叉树又称AVL树。它可以是一颗空树，或者具有以下性质：

它是二叉搜索树
它的左子树和右子树的高度之差(平衡因子)的绝对值不超过1。

深度是从根节点数到它的叶节点，高度是从叶节点数到它的根节点。

它的左子树和右子树都是一颗平衡二叉树。

时间复杂度

查找和插入的时间复杂度为：$O(log_2(N))$。调整本身时间复杂度为$O(1)$。

元素调整方法

https://www.cnblogs.com/banmei-brandy/p/13608479.html

当新插入一个节点，导致不平衡，进行手动调整。

步骤有四步：

找到最小不平衡子树（和其根节点）
从根节点出发，沿插入路径找三个节点。
调整这三个节点。（找出中位数，让中位数作为根节点，其余两个一左一右）
剩下的节点，左右子树的位置保持不变，再找到最后一个节点的插入位置。

插入演示：

（1）先以三个节点的情况演示，假设插入了15，3，7，出现不平衡。

最小不平衡子树就是三个节点。找出中位数7，作为根节点。然后3放到左边，15放到右边。调整完成。

（2）继续插入10和9，导致不平衡。

最小不平衡子树如图所示。从根节点出发找到三个节点。

调整这三个节点的位置，方法和上面一样，把中位数10作为根节点。

（3）继续插入8导致不平衡，以及最小不平衡子树。

7是根节点。从7开始，找到7，10，9三个节点。调整这三个。

让9做根节点，7在左，10在右。

对于剩下的节点，左右子树位置保持不变。3仍然在最左，15仍然在最右。

然后再找到8应该插在哪里就行了。调整完成。

三、红黑树（自平衡二叉查找树）

为什么需要红黑树？

为了解决BST的缺陷：BST的形状取决于节点插入的顺序。如果节点是按照升序或降序的方式插入的，那么二叉查找树就会退化成一个线性结构，也就是一个链表。这样的情况下，二叉查找树的性能就会大大降低。

性能分析

红黑树通过节点的颜色（红或黑）和一系列红黑性质来维持平衡，平衡条件相比于avl树更为宽松，允许树的高度有更大的变化。但会导致查找性能略弱。
红黑树的插入删除比avl更有效率，因为重新平衡次数更少更简单。调整次数控制在$O(log_2(N))$内。调整本身（旋转和颜色变更）是$O(1)$。
查找和插入的时间复杂度为：$O(log_2(N))$。

红黑树的特点

路径：从任意节点到达某个叶子结点为一条路径

长度（黑色高度）：指的是路径里黑色的数量

除了叶子结点之外，每个结点都有两个子节点。
**每个节点非红即黑。**红黑树中的每个节点都被涂成红色或黑色。颜色用于维护树的平衡。
**根节点总是黑色的。**根节点被定义为黑色，以满足所有路径上的黑色节点数量相同的要求。
**每个叶子节点都是黑色的空节点（NIL 节点）。**红黑树中的叶子节点（通常是树的底部的空节点）都被涂成黑色。这些空节点不存储任何数据，它们的存在是为了维持树的平衡性质。
**不能有连续两个红色节点。**这条规则确保了不会有两个连续的红色节点，从而避免了一条路径比另一条路径短很多的情况（因为红色不计入长度）。
**从任意节点到它的叶子节点的每条路径，必须包含相同数目的黑色节点。**这保持了树的大致平衡，从而保证了查找操作的最坏情况时间复杂度为 O(log n)。

红黑树的结构

//静态常量RED，表示节点的颜色为红色。
private static final Boolean RED = false;
//静态常量BLACK，表示节点的颜色为黑色。
  private static final Boolean BLACK = true;

  public class RBNode<T extends Comparable<T>, D> {

      private Boolean color;//节点颜色，红黑树使用颜色来确保在插入和删除操作后，树保持大致平衡。
    	//键值，是Comparable<T> 类型的泛型参数，实现了Comparable接口，可以进行比较。红黑树中，键值用于确定节点的顺序。
      private T key;
      private D data;//具体的数据，不用于排序，仅仅是需要与key一起存储的附加信息。
      private RBNode<T, D> parent;  //父节点
      private RBNode leftChild; //左节点，key小于等于父节点
      private RBNode rightChild; //右节点，key大于父节点

		//全参数的构造函数
      public RBNode(Boolean col, T key, D data, RBNode paret, RBNode leftChild, RBNode rightChild) {
          this.color = col;
          this.key = key;
          this.data = data;
          this.parent = parent;
          this.leftChild = leftChild;
          this.rightChild = rightChild;

      }

  }

插入数据：

按照BST的方法插入，默认插入红色（如果插入黑色会直接破坏路径黑节点数量一致原则），再检查有没有违反规则，进行调整染色。

如果父节点为黑色，直接插入。

如果父叔为红，颜色调换（父叔和爷爷换）。

如果父红叔黑，先颜色调换，再移动（爷爷下来，叔叔上去-》左旋）。

如果父红叔黑，但是自己，父亲，爷爷不在一条直线上（不同路），自己和父亲调换（右旋），再按照上一条操作。

单个红色节点删除：

直接删除

带有一个子节点删除：

当一个节点只有一个子节点时（不包括叶子节点），该结点必然是黑结点，其子节点必定是红色节点。删除方法是用红色子节点的值替换，然后直接删除红色子节点。

带有两个子节点删除：

找到节点的中序遍历的直接前驱结点，和节点的值进行交换，然后删除该节点的方法依照其他的来。

单个黑色结点删除：

兄黑
- 对侄红（指方向相反的侄结点，如果当前结点是左节点，对侄就是右节点，这里的侄子节点包括叶子）
  
  先删除自己，然后父兄交替旋转，然后按照父红兄弟黑换色。
- 顺侄红（指方向相同的侄结点，如果当前结点是左节点，对侄就是左节点，这里的侄子节点包括叶子）
  
  兄侄交替旋转，并调换颜色，就变成了兄黑对侄红的情况。
- 双侄黑
  
  删除本身，然后兄变成红色，父亲变成黑色。如果父亲本身是黑色，就对父亲按照单个黑色节点处理。
兄红

删除本身，然后父兄交替旋转，父兄交换颜色。新的兄弟节点变成黑色，然后按照兄黑处理。