数据结构：红黑树

为什么要以这个结构为题？那就要追溯到C++STL库中的两种map/set，分别基于红黑树与哈希表，我是根本分不清楚。为了搞清楚其区别，我会重点聊聊红黑树和哈希表。

当然也会简单介绍一下树的结构。

---

树 Tree

首先需要简单了解树这个数据结构的一些术语。

度：树中某个节点的孩子的个数称为节点的度，整个树中节点的度的最大值即为树的度。

叶子节点：度为零的节点，又叫终端节点。

分支节点：度大于零的节点，有非终端节点。

结点的深度：是从根结点开始自顶向下逐层累加的。

结点的高度：是从叶结点开始自底向上逐层累加的。

树的高度(或深度)：是树中结点的最大层数。

路径和路径长度。树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的,而路径长度是路径上所经过的边的个数。

有序树和无序树：树中结点的各子树从左到右是有次序的,不能互换,称该树为有序树,否则称为无序树。

森林：多个互不相交的树的集合。

树的表示方法有三种。

双亲表示法：一个节点保存自己的数据和父节点的指针。

struct TreeNode {int data;TreeNode* parent;TreeNode(int data) :data(data), parent(NULL) {}
};

孩子表示法：一个节点保存自己数据之外，保存其子节点的指针集合，可以是数组或链表。

struct ChildNode {TreeNode* child;ChildNode* next;ChildNode(TreeNode* node) : child(node), next(nullptr) {}
};
//这里用链表，也可以用vector
struct TreeNode {int data;ChildNode* firstChild;TreeNode(int data) : data(data), firstChild(nullptr) {}
};

双亲兄弟表示法：因为对于任何一个节点，第一个孩子和下一个兄弟如果存在就是唯一的，能够将任意一棵树变为二叉树。

struct TreeNode {int data;TreeNode* firstChild;//第一个孩子TreeNode* nextSibling;//下一个兄弟TreeNode(int val) : data(val), firstChild(nullptr), nextSibling(nullptr) {}
};

斜树：所有的结点都只有左子树的二叉树叫左斜树，右边一样。

满二叉树：每层的节点都填满了。

完全二叉树：就是满二叉树从后往前按顺序删掉几个节点。(现在知道了，堆因为底层是数组，所以按顺序排成树一定是完全二叉树)

二叉排序树：左子树上所有节点的值均小于根节点的值，右子树上所有节点的值均大于根节点的值，任意子树都满足上述性质。

平衡二叉树：树上任一结点的左子树和右子树的深度之差不超过1，即AVL树。

二叉树的三种遍历方法，感觉是根据遍历根节点的位置定义的。

前序遍历：根节点->左子树->右子树。

void preOrder(TreeNode* root) {if (!root) return;cout << root->val << " ";preOrder(root->left);preOrder(root->right);
}

中序遍历：左子树->根节点->右子树。

void inOrder(TreeNode* root) {if (!root) return;inOrder(root->left);cout << root->val << " ";inOrder(root->right);
}

​​​​​​​前序遍历：左子树->右子树->根节点。

void postOrder(TreeNode* root) {if (!root) return;postOrder(root->left);postOrder(root->right);cout << root->val << " ";
}

​​​​​​​平衡二叉树

平衡二叉树(AVL Tree)最大的作用就是查找,AVL树的查找、插入和删除在平均和最坏情况下都是O(logn)。

我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF (Balance Factor) ， 那么所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。所以在新结点插入后，若造成查找路径上的某个结点不再平衡，则受平衡因子的约束做出相应的调整。

同时，平衡二叉树必须遵循二叉搜索树（BST）的基本性质：左子节点的值 < 根节点的值 < 右子节点的值。这是所有平衡二叉树保持高效查找能力的前提条件。

如何调整？有以下四种情况，调整的对象都是最小不平衡子树。

LL平衡旋转(右单旋转)：

RR平衡旋转(左单旋转)：

LR平衡旋转(先左后右双旋转)：

RL平衡旋转(先右后左双旋转)：

可以看到，这种动态调整的方法使平衡二叉树十分平衡。

红黑树

相较于平衡二叉树，红黑树不受平衡因子制约，用颜色替代严格平衡，降低维护成本，只需要满足以下5条规则。

1、根节点为黑色

2、每个节点不是黑色就是红色

3、所有叶子节点(空节点，NIL节点)都是黑色的

4、不能有两个连续的红色节点(可以连续黑哦)

5、从任一节点到其每个叶子节点(空节点)的所有路径都包含相同数目的黑色节点(称为该节点的黑高)。

struct RBTreeNode {int data;Color color;RBTreeNode* left;RBTreeNode* right;RBTreeNode* parent;RBTreeNode(int val, Color c) : data(val), color(c), left(nullptr), right(nullptr), parent(nullptr) {}
};

​​​​​​​在插入新节点时，需要保持二叉搜索树性质和保持红黑性质。新节点一律被标为红色。

如果父节点是黑色，不用动。如果父节点是红色，看父节点的兄弟节点是什么颜色，他要是黑色或者NIL节点，旋转调整。兄弟节点颜色呼唤。要是他也是红色，把他俩的红色改成黑色，向上递归。

以下为C++实现。

//枚举标记颜色
enum  Color { RED, BLACK };
struct RBTreeNode {int data;Color color;RBTreeNode* left;//左子RBTreeNode* right;//右子RBTreeNode* parent;//父RBTreeNode(int val, Color c = RED) : data(val), color(c), left(nullptr), right(nullptr), parent(nullptr) {}RBTreeNode(int val, Color c = RED, RBTreeNode* parent, RBTreeNode* left, RBTreeNode* right) : data(val), color(c), left(left), right(right), parent(parent) {}RBTreeNode(Color c = RED) : data(0), color(c), left(nullptr), right(nullptr), parent(nullptr) {}
};
//树主体，封装各种操作
class RBTree {
public:RBTree() {NIL = new RBTreeNode(BLACK);root = NIL;}RBTreeNode* root;//根节点RBTreeNode* NIL;//代表NIL节点//插入删除查找void insert(int val);void remove(int val);RBTreeNode* search(int val);
private://内部调整方法void leftRotate(RBTreeNode* x);void rightRotate(RBTreeNode* y);void insertFixup(RBTreeNode* z);void deleteFixup(RBTreeNode* x);
};
RBTreeNode* RBTree::search(int val) {RBTreeNode* current = root;while (current != NIL && val != current->data) {if (val < current->data) {current = current->left;}else {current = current->right;}}return current;
}
//左旋(传旧的根节点)
void RBTree::leftRotate(RBTreeNode* x) {RBTreeNode* y = x->right;x->right = y->left;if (y->left != NIL) {y->left->parent = x;}y->parent = x->parent;if (x->parent == NIL) {root = y;}else if (x == x->parent->left) {x->parent->left = y;}else {x->parent->right = y;}y->left = x;x->parent = y;
}
//右旋
void RBTree::rightRotate(RBTreeNode* y) {RBTreeNode* x = y->left;y->left = x->right;if (x->right != NIL) {x->right->parent = y;}x->parent = y->parent;if (y->parent == NIL) {root = x;}else if (y == y->parent->right) {y->parent->right = x;}else {y->parent->left = x;}x->right = y;y->parent = x;
}
void RBTree::insert(int val) {//新节点必须是红节点RBTreeNode* z = new RBTreeNode(val, RED, NIL, NIL, NIL);RBTreeNode* y = NIL;RBTreeNode* x = root;//标准BST插入(二叉搜索树)//y一直是x的父节点//从根开始探测while (x != NIL) {y = x;if (z->data < x->data) {x = x->left;}else {x = x->right;}}//确定z的父节点z->parent = y;//确定y的子节点if (y == NIL) {root = z;}else if (z->data < y->data) {y->left = z;}else {y->right = z;}//进行修复insertFixup(z);
}
void RBTree::insertFixup(RBTreeNode* z) {//只有红红冲突才需要修复while (z->parent->color == RED) {if (z->parent == z->parent->parent->left) {//看所谓的叔叔节点是什么颜色RBTreeNode* y = z->parent->parent->right;if (y->color == RED) {z->parent->color = BLACK;y->color = BLACK;//将叔叔和父亲的父节点染红z->parent->parent->color = RED;//现在这个父节点成为新的可能产生冲突的红节点z = z->parent->parent;}else {//检查一下是否需要左旋if (z == z->parent->right) {//防止影响后续变色操作z = z->parent;leftRotate(z);}z->parent->color = BLACK;z->parent->parent->color = RED;rightRotate(z->parent->parent);}}else {RBTreeNode* y = z->parent->parent->left;if (y->color == RED) {z->parent->color = BLACK;y->color = BLACK;z->parent->parent->color = RED;z = z->parent->parent;}else {//检查一下是否需要右旋if (z == z->parent->left) {z = z->parent;rightRotate(z);}z->parent->color = BLACK;z->parent->parent->color = RED;leftRotate(z->parent->parent);}}}root->color = BLACK;
}

​​​​​​​我还没有写红黑树的删除操作，因为其是最难理解的操作了。在此之前，需要先回顾一下一般二叉搜索树的删除方法。

对于一般二叉搜索树，“删除有两个子节点的节点”最终会转换为“删除拥有一个子节点的节点”或者“删除没有子节点的节点”，要么直接删掉要么让子树代替。那么对于红黑树的删除也是一样的，但是删除不同于插入，他可能删掉的是黑色节点从而破坏红黑树的黑高一致性。那么此时的删除就需要分情况讨论了。

现在详细谈谈删除没有子节点的节点时，且其还是黑色的情况。为了在后续向上或者向下递归时方便理解，我引入了“问题根”的概念(我瞎起的只是为了方便理解)，问题根是某一串子树的根节点，有这样的特性：如果目标节点的兄弟节点为黑色，那么问题根两个子树黑高相差1，大的那边的子节点的两颗子树与另一边的整个子树的黑高相同。

然后我们看图理解。

在知道原理之后，我们再来写C++实现。

//找到右子树中的最小值，即后继节点
RBTreeNode* RBTree::minimum(RBTreeNode* node) {while (node->left != NIL) {node = node->left;}return node;
}
//节点的代替方法，后者代替前者
void RBTree::transplant(RBTreeNode* u, RBTreeNode* v) {if (u->parent == NIL) {root = v;}else if (u == u->parent->left) {u->parent->left = v;}else {u->parent->right = v;}v->parent = u->parent;
}
//删除操作
void RBTree::remove(int val) {RBTreeNode* z = search(val);if (z == NIL) { return; }RBTreeNode* y = z;//记录目标节点的颜色Color y_original_color = y->color;//分情况if (z->left == NIL && z->right != NIL) {//只有右子树,直接换transplant(z, z->right);}else if (z->right == NIL && z->left != NIL) {//只有左子树，直接换transplant(z, z->left);}else if (z->left == NIL && z->right == NIL) {if (z->color == RED) {//是红色，直接换成NILtransplant(z, z->right);}else {//是黑色进行调整//替换掉以后，再调整transplant(z, z->right);//z是问题根下黑高少1的子树的根节点deleteFixup(z);}}else if (z->left != NIL && z->left != NIL) {//处理左右都有子树的情况//找到后继节点y = minimum(z->right);//更新目标节点的颜色y_original_color = y->color;//替换数据z->data = y->data;//要删的节点变化z = y;if (z->left == NIL && z->right->color == RED) {//只有右子树,直接换transplant(z, z->right);}else if (z->right == NIL && z->left->color == RED) {//只有左子树，直接换transplant(z, z->left);}else if (z->left == NIL && z->right == NIL) {if (z->color == RED) {//是红色，直接换成NILtransplant(z, z->right);}else {//是黑色进行调整//替换掉以后，再调整transplant(z, z->right);//z是问题根下黑高少1的子树的根节点deleteFixup(z);}}}//释放内存delete z;
}
//调整
void RBTree::deleteFixup(RBTreeNode* x) {//这里的x就是目标节点,x递归到根节点时跳出循环//x永远是问题根的出问题的子树的根节点while (x != root) {if (x == x->parent->left) {//记录兄弟节点RBTreeNode* w = x->parent->right;if (w->color == RED) {w->color = BLACK;x->parent->color = RED;leftRotate(x->parent);//问题根下移，更新兄弟节点w = x->parent->right;}//此时兄弟节点绝对为黑色，不用进入循环if (w->left->color == BLACK && w->right->color == BLACK) {w->color = RED;//问题根上移，进入循环调整，目标节点更新x = x->parent;}else {//看看是否需要右旋if (w->right->color == BLACK) {w->left->color = BLACK;//防止影响下一步染色w->color = RED;rightRotate(w);w = x->parent->right;}w->color = x->parent->color;x->parent->color = BLACK;w->right->color = BLACK;leftRotate(x->parent);//跳出循环x = root;}}else { RBTreeNode* w = x->parent->left;if (w->color == RED) {w->color = BLACK;x->parent->color = RED;rightRotate(x->parent);w = x->parent->left;}if (w->left->color == BLACK && w->right->color == BLACK) {w->color = RED;x = x->parent;}else {//看看是否需要左旋if (w->left->color == BLACK) {w->right->color = BLACK;//防止影响下一步染色w->color = RED;leftRotate(w);w = x->parent->left;}w->color = x->parent->color;x->parent->color = BLACK;w->left->color = BLACK;rightRotate(x->parent);x = root;}}}//保持根节点为黑色x->color = BLACK;
}

​​​​​​​总的来说，红黑树最坏情况下查找/插入/删除均为O(log n)，避免BST退化成链表的O(n)风险，旋转操作集中在局部子树，在插入删除方面相比于平衡二叉树性能好了许多。

---

小结

红黑树的逻辑还真是复杂，下次我会讨论哈希表，以及C++的STL库中两种set/map的使用，敬请期待。

如有补充纠正欢迎留言。