找往期文章包括但不限于本期文章中不懂的知识点：
个人主页：我要学编程(ಥ_ಥ)-CSDN博客
所属专栏：数据结构（Java版）
数据结构之AVL树-CSDN博客 通过上篇文章的学习，我们知道了AVL树的一些情况，同时也实现了AVL树的插入与验证，但同时也知道了AVL树在查找方面性能非常高，但是在频繁的插入和删除时的效率就比较低了。因此我们今天来学习一种相对效率较高的数据结构——红黑树。
目录
红黑树概念
红黑树的性质
红黑树节点的定义
红黑树的插入
红黑树的验证
AVL树和红黑树的比较
红黑树概念
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。如下图所示：
注意：这里的 NIL 是空节点的意思，但是在红黑树中空节点是我们平常所说的叶子节点，并且这个节点的颜色为黑色。
红黑树的性质
1、每个结点不是红色就是黑色；
2、根节点是黑色的；
3、如果一个节点是红色的，则它的两个孩子结点是黑色的，也就是说 没有2个连续的红色节点；
4、对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点数；
5、每个叶子结点都是黑色的（此处的叶子结点指的是空结点)；
由上述性质，便可推出：其中最长路径中节点个数不会超过最短路径节点个数的两倍。如下验证：
红黑树节点的定义
static class TreeNode {public int val;public COLOR color; // 颜色public TreeNode left; // 左孩子public TreeNode right; // 右孩子public TreeNode parent; // 父亲public TreeNode(int val) {this.val = val;this.color = COLOR.RED; // 默认是红色的节点}}之所以把红黑树的节点默认定义为红色，是因为在插入元素时，如果节点为黑色，就会改变从根结点不同路径到叶子结点之间的黑色节点的个数，修改十分困难，而节点为红色，只是可能会违反不能出现两个连续是红色节点的情况，修改起来比较容易。
红黑树的插入
枚举颜色：
public enum COLOR {RED,BLACK;
}
根结点：
public TreeNode root;思路：和二叉搜索树一样，先得找到合适的位置进行插入节点的操作。
// 判断根结点是不是为 nullif (root == null) {root = new TreeNode(val);root.color = COLOR.BLACK; // 根结点要改为黑色return true;}// 开始寻找要插入节点的位置TreeNode cur = root;TreeNode parent = null;while (cur!= null) {parent = cur;if (cur.val < val) {cur = cur.right;} else if (cur.val > val) {cur = cur.left;} else {return false; // 不能插入相同的元素}}// parent 是要插入的前一个位置（判断是哪棵树）TreeNode node = new TreeNode(val);if (val < parent.val) {parent.left = node;}else {parent.right = node;}node.parent = parent;cur = node;插入操作完成之后，就得判断当前红黑树是否违反了其性质：不能出现连续的红色节点。
// 判断是否需要调整if (parent.color == COLOR.BLACK) {// 父亲节点为黑色，则没有改变性质，无需调整return true;}接下来就是需要调整的， 根据叔叔节点是否存在和颜色划分了大概两种情况：
因为 grandfather节点原先的颜色是黑色，当调整为红色之后，可能会出现：有连续的红色节点的情况，因此还得继续往上判断，直至parent为null即可。
从这里我们可以发现：其实叔叔节点为黑色和叔叔节点不存在的处理方式是一样的。
当然，上面两种只是主要的情况，还有 parent 和 uncle 所处的位置不同，以及cur 所处的位置不同步，会细分出很多种情况。
检查修改代码实现：
// 判断是否需要调整if (parent.color == COLOR.BLACK) {// 父亲节点为黑色，则没有改变性质，无需调整return true;}// 父亲节点为红色，则与性质发生冲突，需要调整while (parent!= null && parent.color == COLOR.RED) {// 判断叔叔节点的颜色是啥，根据这个来判断调整方式TreeNode grandfather = parent.parent;// 根据叔叔节点和父亲节点位置来划分不同的情况if (parent == grandfather.left) {// 再判断叔叔节点是否存在，根据叔叔节点的情况来处理TreeNode uncle = grandfather.right;if (uncle!= null && uncle.color == COLOR.RED) {// 修改叔叔节点、父亲节点和祖父节点的颜色，然后继续判断grandfather.color = COLOR.RED;uncle.color = COLOR.BLACK;parent.color = COLOR.BLACK;cur = grandfather;parent = cur.parent;} else { // uncle 为 null 或者 uncle 为黑色// 判断 cur 的位置在 parent 的哪边if (cur == parent.left) {// uncle 为 null 和不为 null 直接右旋祖父节点，然后再修改颜色rotateRight(grandfather);grandfather.color = COLOR.RED;parent.color = COLOR.BLACK;} else { // cur == parent.right// 左旋parent，再交换rotateLeft(parent);TreeNode tmp = parent;parent = cur;cur = tmp;// 经过上面的处理，变成了cur为parent的left的情况rotateRight(grandfather);grandfather.color = COLOR.RED;parent.color = COLOR.BLACK;}}} else { // parent == grandfather.right// 再判断叔叔节点是否存在，根据叔叔节点的情况来处理TreeNode uncle = grandfather.left;if (uncle!= null && uncle.color == COLOR.RED) {// 修改叔叔节点、父亲节点和祖父节点的颜色，然后继续判断grandfather.color = COLOR.RED;uncle.color = COLOR.BLACK;parent.color = COLOR.BLACK;cur = grandfather;parent = cur.parent;} else { // uncle 为 null 或者 uncle 为黑色// 判断 cur 的位置在 parent 的哪边if (cur == parent.right) {rotateLeft(grandfather);grandfather.color = COLOR.RED;parent.color = COLOR.BLACK;} else { // cur == parent.left// 先变为cur == parent.right的情况rotateRight(parent);TreeNode tmp = parent;parent = cur;cur = tmp;// 再进行上面的处理rotateLeft(grandfather);grandfather.color = COLOR.RED;parent.color = COLOR.BLACK;}}}}root.color = COLOR.BLACK; // 把根结点修改为黑色return true;左单旋代码实现：（思路可见AVL树的博客文章）
private void rotateLeft(TreeNode parent) {TreeNode subR = parent.right;TreeNode subRL = subR.left;TreeNode parentP = parent.parent;// 修改四个指针的指向parent.parent = subR;parent.right = subRL;if (subRL != null) {subRL.parent = parent;}subR.left = parent;// 修改本级根结点和上级树的指向if (root == parent) {root = subR;root.parent = null;} else {subR.parent = parentP;if (parentP.left == parent) {parentP.left = subR;} else {parentP.right = subR;}}}右单旋代码实现：（思路可见AVL树博客文章）
private void rotateRight(TreeNode parent) {TreeNode subL = parent.left;TreeNode subLR = subL.right;TreeNode parentP = parent.parent;// 修改四个指针的指向parent.parent = subL;parent.left = subLR;if (subLR != null) {subLR.parent = parent;}subL.right = parent;// 修改本级根结点和上级树的指向if (parent == root) {root = subL;root.parent = null;} else {subL.parent = parentP;if (parentP.left == parent) {parentP.left = subL;} else {parentP.right = subL;}}}
处理的思路：
1、先判断父亲节点和叔叔节点在哪边；
2、再根据叔叔节点是否存在以及颜色来分别处理：
2.1、叔叔节点存在且为红色，就是修改颜色再继续检查；
2.2、叔叔节点不存在（NIL也是黑色）或者叔叔节点为红色，就是进行旋转处理（旋转需要判断cur具体是在哪边，从而进行不同的旋转）；
红黑树构建完成之后，就得开始验证这棵二叉树是不是一棵红黑树。
红黑树的验证
我们是利用红黑树的性质来进行验证的。
1、是一棵二叉搜索树。因此采取中序遍历的方式输出，看是不是一棵二叉搜索树；
代码实现：
// 中序遍历：检查是否为有序序列public void inorder(TreeNode root) {if(root == null) {return;}inorder(root.left);System.out.print(root.val+" ");inorder(root.right);}2、根结点一定得是黑色的；
3、不能出现两个连续的红色节点；
思路：遍历树的所有结点，判断这个节点的颜色是不是和其父亲节点一样都是红色。如果是，则返回false，否则一直判断下去，直至全部遍历完成，返回true。
代码实现：
private boolean isContinuousRedNodes(TreeNode root) {if (root == null) {return true;}// 该节点为红色if (root.color == COLOR.RED) {// 其父亲节点也为红色if (root.parent != null && root.parent.color == COLOR.RED) {System.out.println("违反了性质：连续出现了两个红色的节点");// return false; 这个可有可无}}// 递归判断左子树和右子树return isContinuousRedNodes(root.left) && isContinuousRedNodes(root.right);}4、从根结点到不同路径上的叶子节点之间的黑色节点个数要相同。
思路：先记录任意一条从根结点到叶子结点之间的黑色节点的个数。然后再遍历树的路径判断是否一致。如果不一致，就返回false，一致就一直判断，直至返回true。
代码实现：
// 求某条路径上的所有黑色节点个数private int getBlckCount(TreeNode root) {TreeNode cur = root;int count = 0;while (cur != null) {if (cur.color == COLOR.BLACK) {count++;}cur = cur.left;}return count;}private boolean sameBlackNodes(TreeNode root, int pathBlack, int sameBlackCount) {if (root == null) {return true;}if (root.color == COLOR.BLACK) {pathBlack++;}// 到叶子节点了，就得进行比较if (root.left == null && root.right == null) {if (pathBlack != sameBlackCount) {System.out.println("违反了性质：每条路径上黑色的节点个数是不一样的！");// return false; 可有可无} }return sameBlackNodes(root.left, pathBlack, sameBlackCount)&& sameBlackNodes(root.right, pathBlack, sameBlackCount);}剩余代码：
public boolean isRBTree(TreeNode root) {// 就是看是否满足红黑树的性质// 1、根结点是不是黑色if (root.color != COLOR.BLACK) {System.out.println("违反了性质：根节点必须是黑色的！");}int sameBlackCount = getBlckCount(root);// 是不是存在两个连续的红色节点 && 是不是不同；路径上有相同的黑色节点个数return isContinuousRedNodes(root) && sameBlackNodes(root, 0, sameBlackCount);}测试代码：
public class Test {public static void main(String[] args) {//int[] array = {16, 3, 7, 11, 9, 26, 18, 14, 15};int[] array = {4, 2, 6, 1, 3, 5, 15, 7, 16,14};RBTree rbTree = new RBTree();for (int i = 0; i < array.length; i++) {rbTree.insert(array[i]);}System.out.println(rbTree.isRBTree(rbTree.root));rbTree.inorder(rbTree.root);}
}
AVL树和红黑树的比较
红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(log N)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比 AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。 就像在 Java集合框架中的：TreeMap、TreeSet底层使用的就是红黑树。
好啦！本期 数据结构之红黑树 的学习之旅就到此结束啦！我们下一期再一起学习吧！
时Windows PyCharm无法模拟键盘输入)
