数据结构算法 --- 红黑树，这可能是我看过红黑树讲的最好的文章。

2.平衡二叉树

二叉搜索树解决了许多问题，比如可以快速的查找最大值和最小值，可以快速找到排名第几位的值，快速搜索和排序等等。但普通的二叉搜索树有可能出现极不平衡的情况（斜树），这样我们的时间复杂度就有可能退化成 O(N) 的情况。比如我们现在插入的数据是 [1,2,3,4,5,6,7] 转换为二叉树如下：

由于普通的二叉搜索树会出现极不平衡的情况，那么我们就必须得想想办法了，这个时候平衡二叉树就能帮到我们了。什么是平衡二叉树？平衡二叉搜索树（Self-balancing binary search tree）又被称为 AVL 树（有别于 AVL 算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。

平衡二叉树有一个很重要的性质：左右两个子树的高度差的绝对值不超过 1。那么解决方案就是如果二叉树的左右高度超过 1 ，我们就把当前树调整为一棵平衡二叉树。这就涉及到左旋、右旋、先右旋再左旋、先左旋再右旋。

2.1 右旋：

TreeNode<K, V> *R_Rotation(TreeNode<K, V> *pNode) {TreeNode<K, V> *left = pNode->left;TreeNode<K, V> *right = left->right;left->right = pNode;pNode->left = right;// 重新调整高度 pNode->height = max(getHeight(pNode->left), getHeight(pNode->right)) + 1;left->height = max(getHeight(left->left), getHeight(left->right)) + 1;return left;}

2.2 左旋：

TreeNode<K, V> *L_Rotation(TreeNode<K, V> *pNode) {TreeNode<K, V> *right = pNode->right;TreeNode<K, V> *left = right->left;right->left = pNode;pNode->right = left;// 重新调整高度 pNode->height = max(getHeight(pNode->left), getHeight(pNode->right)) +

《Android学习笔记总结+最新移动架构视频+大厂安卓面试真题+项目实战源码讲义》
浏览器打开：qq.cn.hn/FTe 免费领取

1;right->height = max(getHeight(right->left), getHeight(right->right)) + 1;return right;}

2.3 先右旋再左旋：

TreeNode<K, V> *R_L_Rotation(TreeNode<K, V> *pNode) {pNode->right = R_Rotation(pNode->right);return L_Rotation(pNode);}

2.4 先左旋再右旋：

TreeNode<K, V> *L_R_Rotation(TreeNode<K, V> *pNode) {pNode->left = L_Rotation(pNode->left);return R_Rotation(pNode);}

3.红黑树

红黑树用法就比较广了，比如 JDK 1.8 的 HashMap，TreeMap，C++ 中的 map 和 multimap 等等。红黑树学习起来还是有一点难度的，这时如果我们心中有 B 树就有助于理解它，如果没有 B 树也没有关系。

红黑树的特性:（1）每个节点或者是黑色，或者是红色。（2）根节点是黑色。（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL 或 NULL)的叶子节点！]（4）如果一个节点是红色的，则它的子节点必须是黑色的。（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

假设我们现在要插入一个新的节点，如过插入的这个新的节点为黑色，那么必然会违反性质(5)，所以我们把新插入的点定义为红色的。但是如果插入的新节点为红色，就可能会违反性质(4) ，因此我们需要对其进行调整，使得整棵树依然满足红黑树的性质，也就是双红修正。接下来我们只要分情况分析就可以了：

1. 如果没有出现双红现象，父亲是黑色的不需要修正；

2. 叔叔是红色的 ，将叔叔和父亲染黑，然后爷爷染红；

3. 叔叔是黑色的，父亲是爷爷的左节点，且当前节点是其父节点的右孩子，将“父节点”作为“新的当前节点”，以“新的当前节点”为支点进行左旋。然后将“父节点”设为“黑色”，将“祖父节点”设为“红色”，以“祖父节点”为支点进行右旋；

4. 叔叔是黑色的，父亲是爷爷的左节点，且当前节点是其父节点的左孩子，将“父节点”设为“黑色”，将“祖父节点”设为“红色”，以“祖父节点”为支点进行右旋；

5. 叔叔是黑色的，父亲是爷爷的右节点，且当前节点是其父节点的左孩子，将“父节点”作为“新的当前节点”，以“新的当前节点”为支点进行右旋。然后将“父节点”设为“黑色”，将“祖父节点”设为“红色”，以“祖父节点”为支点进行左旋；

6. 叔叔是黑色的，父亲是爷爷的右节点，且当前节点是其父节点的右孩子，将“父节点”设为“黑色”，将“祖父节点”设为“红色”，以“祖父节点”为支点进行左旋；

上面的双红修正现象看似比较复杂，但实际上只有三种情况，一种是没有双红现象，另一种是父亲和叔叔都是红色的，最后一种是叔叔是黑色的。我们来画个实例看下：

void solveDoubleRed(TreeNode *pNode) {while (pNode->parent && pNode->parent->color == red) {// 情况 1TreeNode *uncle = brother(parent(pNode));

if (getColor(uncle) == red) {// 情况 2// 设置双亲和叔叔为黑色 setColor(parent(pNode), black);setColor(uncle, black);// 指针回溯至爷爷 pNode = parent(parent(pNode));} else {// 父亲是爷爷的左儿子 if (parent(parent(pNode))->left = parent(pNode)) { // 情况 3 和 4// 自己是父亲的右儿子 if (parent(pNode)->right == pNode) {pNode = parent(pNode);L_Rotation(pNode);}// 把我自己这边的红色节点挪到隔壁树上，但仍然不能违反性质 4 和 5setColor(parent(pNode), black);setColor(parent(parent(pNode)), red);R_Rotation(parent(parent(pNode)));} else { // 情况 5 和 6// 自己是父亲的左儿子 if (parent(pNode)->left == pNode) {pNode = parent(pNode);R_Rotation(pNode);}// 把我自己这边的红色节点挪到隔壁树上，但仍然不能违反性质 4 和 5setColor(parent(pNode), black);setColor(parent(parent(pNode)), red);L_Rotation(parent(parent(pNode)));}}}

// 根结点为黑色 root->color = black;}