不知道大家有没有看今天的那个面试官被害视频，我那神奇的同事不知道那个脑回路突然被打通了，在办公室问了一句：是不是面试官问了一下红黑树，把面试的人给问毛了啊，都问，我不会这个还问，然后暴起下手呀！！然后办公室掀起了一阵讨论热潮



树，这个大学时代数据结构与算法的重点之一，当时真的也是头疼了好久，但是其实现在想想，害，没啥变化，依旧头疼，看下面这张图，树包含的内容





而树的内容又以二叉树作为重点，先来复习一下基础知识



BST树:



二叉搜索树(Binary Search Tree，简写BST)，又称为二叉排序树，属于树的一种，通过二叉树将数据组织起来，树的每个节点都包含了健值key、数据值data、左子节点指针、右子节点指针。其中健值key是最核心的部分，它的值决定了树的组织形状;数据值data是该节点对应的数据，有些场景可以忽略，举个例子，key为身份证号而data为人名，通过身份证号找人名;左子节点指针指向左子节点;右子节点指针指向右子节点。



特点:

左右子树也分别是二叉搜索树。

左子树的所有节点key值都小于它的根节点的key值。右子树的所有节点key值都大于他的根节点的key值。二叉搜索树可以为一棵空树。

一般来说，树中的每个节点的 key值都不相等，但根据需要也可以将相同的key值插入树中



AVL树:



AVL树，也称平衡二叉搜索树，AVL是其发明者姓名简写。AVL树属于树的一种，而且它也是一棵二叉搜索树，不同的是他通过一定机制能保证二叉搜索树的平衡，平衡的二叉搜索树的查询效率更高。



特点:

AVL树是一棵二叉搜索树。

AVL树的左右子节点也是AVL树。

AVL树拥有二叉搜索树的所有基本特点。

每个节点的左右子节点的高度之差的绝对值最多为1，即平衡因子为范围为[-1,1]。



还有一个就是今天我们讨论的重点：红黑树，我们就来看一下



红黑(Red-black)树



是一种自平衡二叉查找树，1972年由Rudolf Bayer发明，它与AVL树类似，都在插入和删除操作时能通过旋转操作保持二叉查找树的平衡，以便能获得高效的查找性能。它可以在O(logn)时间内做查找，插入和删除等操作。红黑树是2-3-4树的一种等同，但有些红黑树设定只能左边是红树，这种情况就是2-3树的一种等同了。对于AVL树来说，红黑树牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。



特点:



节点是红色或黑色。根节点是黑色。

每个叶节点(NIL节点)是黑色的。

每个红色节点的两个子节点都为黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

最长路径不超过最短路径的2倍





上图就是一颗简单的红黑树。其中Nil为叶子结点，并且它是黑色的。(H和M的黑色叶子节点没画出来)



介绍到此，为了后面讲解不至于混淆，我们还需要来约定下红黑树一些结点的叫法，如图2所示。





我们把正在处理(遍历)的结点叫做当前结点，如图2中的D，它的父亲叫做父结点，它的父亲的另外一个子结点叫做兄弟结点，父亲的父亲叫做祖父结点。



3.基本操作



前面讲到红黑树能自平衡，它靠的是什么？三种操作：左旋、右旋和变色。



• 左旋：逆时针旋转，父节点被自己的右孩子取代，而自己成为自己的左孩子（注：左旋只影响旋转结点和其右子树的结构，把右子树的结点往左子树挪了。）





• 右旋：顺时针旋转，父节点被左孩子取代，而自己成为自己的右孩子（注：右旋只影响旋转结点和其左子树的结构，把左子树的结点往右子树挪了。）





• 变色：结点的颜色由红变黑或由黑变红。



所以不难看出，无论什么旋转操作都是局部的改变了树的的节点，但要保持红黑树的性质，结点不能乱挪，还得靠变色了。怎么变？具体情景有不同变法，来看一下













至此，变色的任务完成，按照步骤，满足规则，一步步进行，错过一步可能就理解不了了





好了，理论的东西，到这里基本就讲解完了，红黑树难吗？说实话我个人觉得，这破玩意太为难人了



4.红黑树的部分实现



红-黑树的节点实现



红-黑树是对二叉搜索树的改进，所以其节点与二叉搜索树是差不多的，只不过在它基础上增加了一个boolean型变量来表示节点的颜色，具体看RBNode类： 



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



boolean color; //颜色    



T key; //关键字(键值)    



RBNode<T> left; //左子节点    



RBNode<T> right; //右子节点    



RBNode<T> parent; //父节点        



public RBNode(T key, boolean color, RBNode<T> parent, RBNode<T> left, RBNode<T> right) {  



this.key = key;       



this.color = color;       



this.parent = parent;        



this.left = left;        



this.right = right;    



}       



public T getKey() {       



return key;   



}       



public String toString() {       



return "" + key + (this.color == RED? "R" : "B");   



}



}

左旋的具体实现



上面对左旋的概念已经有了感性的认识了，这里就不再赘述了，我们从下面的代码中结合上面的示意图，探讨一下左旋的具体实现： /*************对红黑树节点x进行左旋操作 ******************//* * 左旋示意图：对节点x进行左旋 



* 左旋做了三件事：



*  1. 将y的左子节点赋给x的右子节点,并将x赋给y左子节点的父节点(y左子节点非空时) 



*   2. 将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右) 



*    3. 将y的左子节点设为x，将x的父节点设为y 



*    */



private void leftRotate(RBNode<T> x) {   



//1. 将y的左子节点赋给x的右子节点，并将x赋给y左子节点的父节点(y左子节点非空时)    RBNode<T> y = x.right;    



x.right = y.left;        



if(y.left != null)        



y.left.parent = x;        



//2. 将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右)   



y.parent = x.parent;       



if(x.parent == null) {        



this.root = y; 



//如果x的父节点为空，则将y设为父节点    



} else {       



if(x == x.parent.left) 



//如果x是左子节点            



x.parent.left = y; 



//则也将y设为左子节点        



else            



x.parent.right = y;



//否则将y设为右子节点   



}        



//3. 将y的左子节点设为x，将x的父节点设为y   



y.left = x;    



x.parent = y;        



}

右旋具体实现



上面对右旋的概念已经有了感性的认识了，这里也不再赘述了，我们从下面的代码中结合上面的示意图，探讨一下右旋的具体实现： /*************对红黑树节点y进行右旋操作 ******************//* * 左旋示意图：对节点y进行右旋 



* 右旋做了三件事： 



*  1. 将x的右子节点赋给y的左子节点,并将y赋给x右子节点的父节点(x右子节点非空时) 



*   2. 将y的父节点p(非空时)赋给x的父节点，同时更新p的子节点为x(左或右) 



*    3. 将x的右子节点设为y，将y的父节点设为x 



*    */



private void rightRotate(RBNode<T> y) {  



//1. 将y的左子节点赋给x的右子节点，并将x赋给y左子节点的父节点(y左子节点非空时)    RBNode<T> x = y.left;   



y.left = x.right;       



if(x.right != null)        



x.right.parent = y;        



//2. 将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右)    



x.parent = y.parent;       



if(y.parent == null) {       



this.root = x; 



//如果x的父节点为空，则将y设为父节点 



} else {      



if(y == y.parent.right) //如果x是左子节点          



y.parent.right = x; //则也将y设为左子节点      



else          



y.parent.left = x;//否则将y设为右子节点   



}       



//3. 将y的左子节点设为x，将x的父节点设为y   



x.right = y;  



y.parent = x;     



} 

5.功能



这里我就简单的介绍一下，篇幅原因（我不会承认是我饿了，想去吃宵夜了，嘿嘿嘿），后面我会进行详细的介绍



5.1查找



因为红黑树是一颗二叉平衡树，并且查找不会破坏树的平衡，所以查找跟二叉平衡树的查找无异，为了让大家更好理解，看下面这张 二叉树查找流程图





非常简单，但简单不代表它效率不好。正由于红黑树总保持黑色完美平衡，所以它的查找最坏时间复杂度为O(2lgN)，也即整棵树刚好红黑相隔的时候。能有这么好的查找效率得益于红黑树自平衡的特性，而这背后的付出，红黑树的插入操作功不可没～



5.2 插入



插入操作包括两部分工作：



一查找插入的位置 即找到要插入的父节点；二插入后自平衡。



查找插入的父结点很简单，跟查找操作区别不大，还是以一张流程图总结一下





特别注意：

如果在面试的时候有人问你插入结点是应该是什么颜色呢？答案是红色。理由很简单，红色在父结点（如果存在）为黑色结点时，红黑树的黑色平衡没被破坏，不需要做自平衡操作。但如果插入结点是黑色，那么插入位置所在的子树黑色结点总是多1，必须做自平衡。



还有一个删除，实在是太饿了，不行了，不能随随便便应付大家，听我下回分解，哈哈哈哈，咱下次详细的讲解红黑树的应用



文章首发公众号：Java架构师联盟