面试写红黑树_面试题红黑树

为什么这么多关于红黑树的面试题呢？ 　　作为大学数据结构课程中并不是重点的红黑树，以及编程上不怎么接触的数据结构（除了知道红黑树通常是有序 map 的实现方式），是怎么样一步步成为常见面试题的考察知识点的？ 　　红黑树是一种非常常见又相对复杂的数据结构，要理解其性质、平衡调整等操作，需要对数据结构的基本概念有深入的理解。理解了红黑树，也同时了解了：多叉树。AVL树、23树、234树。数据结构和算法。计算机科学的基础知识等。 　　所以，通过考察红黑树，面试官可以知道基本数据结构掌握程度、算法复杂度分析能力、计算机底层原理掌握情况、逻辑思维和问题解决能力。 　　一般来说，不会要求直接手写一个红黑树，但是了解红黑树的结构，有助于理解一些底层实现。红黑树虽然相对复杂一些，但是也不是达到无法理解的程度。 　　这篇文章将通过图解的方式剖析红黑树的底层实现，相信读完这篇文章，你将了解到红黑树的底层原理，包括红黑树的五个性质、旋转操作、插入操作和删除操作、应用场景等。 　　引言 　　相信学习过编程的都或多或多或少的听说过“红黑树”，在了解红黑树之前，需要明白它是一个二叉树，那么在哪些场景/地方使用过红黑树呢？java的hash map。Linux系统的CFS公平调度算法。多路复用器 epoll。定时器。nginx 等。 　　上面这些都是使用红黑树的经典场景。红黑树是一个非常常用的数据结构，它有两种用法： 　　（1）当作Key-Value对，用于查找；通过Key去查找Value。Key是红黑树中构建出来的一个二叉树；比如，当向二叉树里插入一个节点时，红黑树通过比较Key来确定插入的位置。 　　（2）红黑树是一个二叉排序树，它的中序遍历是顺序的，可以用来作为顺序执行，适合范围查询。

红黑树结构 　　典型的Key-Value数据结构，举个例子：github上的一个流量统计功能（Traffic）。

key-value的应用 　　这两个表中，可以把Site（从哪个网站跳转过来的）作为Key，Views（访问的次数）作为Value；同样的，可以将Content（项目中的哪个资源）作为Key，Views（访问的次数）作为Value。这就是典型的Key-Value结构，针对这样的一个结构可以构建出一个红黑树进行存储。当再次访问相同的资源的时候，可以通过查询红黑树中对应的节点，然后对访问次数（Value）进行加一，从而达到统计的效果。 　　一、红黑树的定义 　　1.1、理论知识 　　红黑树本质上是一个二叉树。

二叉树 　　红黑树在二叉树的基础上具备如下的性质：每个结点是红的或者黑的。根结点是黑的。每个叶子结点是黑的。如果一个结点是红的，则它的两个儿子都是黑的。对每个结点，从该结点到其子孙结点的所有路径上的 包含相同数目的黑结点 。 　　满足以上性质的二叉树就是红黑树。其中第五条性质就决定了红黑树的平衡，它不像AVL树那样严格要求两边子树的高度差是1，而是要求黑色节点的高度一致即可。 　　从第四条和第五条的性质中，我们可以总结出一个数学结论：红黑树的根节点到叶子节点的最短路径与红黑树的根节点到叶子节点的最长路径之比是
。

最短路径和最长路径之比 　　为了检查是否真正理解了红黑树的性质，这里提供如下的判断题，请判断哪个是红黑树，哪个不是：

判断哪个是红黑树？从黑色节点的高度判断，14（黑）–> 8（红）–> NIL（黑），黑高为2；14（黑）–> 8（红）–> 10（黑）NIL（黑），黑高是3。显然不符合红黑树性质中 对每个结点从该结点到其子孙结点的所有路径上的包含相同数目的黑结点 的性质。所有这个不是红黑树。根节点是黑色，黑高都是3，没有连续的红色节点。这个满足红黑树的所有性质，是红黑树。从黑色节点的高度判断，14（黑）–> 8（红）–> NIL（黑），黑高为2；14（黑）–> 8（红）–> 10（黑）NIL（黑），黑高是3。显然不符合红黑树性质中 对每个结点从该结点到其子孙结点的所有路径上的包含相同数目的黑结点 的性质。所有这个不是红黑树。根节点是红色的，所有它也不是红黑树。 　　1.2、代码实现 　　了解了理论，就需要代码上进行实现。定义红黑树节点结构体包含以下内容：定义一个颜色标识符。定义左子树和右子树的指针。定义执行父节点的指针。这个是为了做性质调整需要。定义Key和Value。 　　将颜色定义的变量放在结构体的最后一个可以起到节省内存的目的。 　　定义红黑树的头节点结构体包含以下内容：指向红黑树开始位置的根节点root。 根据红黑树的性质，所有的叶子节点都是黑色的，可以把所有的叶子节点都指向同一个点，并且隐藏（也就是NIL节点）。如果需要，还可以定义指向value最小、最大的节点从而提高效率。 　　使用自定义的NIL节点而不是使用NULL的原因是这个NIL节点必须具备红黑树的所有性质。它是为了红黑树的各种操作易于判断，如果使用NULL，我们就无法操作它。 　　这样，红黑树的定义就完成了。当阅读一份项目源码时，如果看到一个结构体包含颜色定义、左节点、右节点、父节点时，可以大概率确定它是红黑树了。 　　1.3、代码优化 　　上面的红黑树定义是否存在一些问题呢？最大的问题是这个红黑树的定义不可复用，它的业务和红黑树的实现是黏在一起的，可迁移性低。 　　为了提高通用性和灵活性，可以将红黑树的定义做成模板化，将红黑的性质封装在一起。 　　举个例子，线程有ready（就绪）、wait（等待）、sleep（休眠）、exit（退出）等状态；假设有N个线程，它们状态各不相同，每个状态可以使用红黑树进行存储，那么就可以定义成这样： 　　也就是一个结构体可以包含多颗红黑树。 　　二、红黑树的旋转 　　当红黑树的性质被破环时，需要触发旋转，进行调整。旋转是为了不影响其他的性质，然后更好的变色。 　　旋转有两种方式：左旋和右旋。这两种旋转是一种互逆的过程。 　　旋转的目的：保持红黑树的平衡。

旋转原理 　　左旋（Left Rotation）：左旋操作是将一个节点的右子节点变为其父节点，同时将右子节点的左子节点变为该节点的右子节点。让当前节点的右子节点成为新的根节点。将新根节点的左子节点（如果存在）移动为原来节点的右子节点。将原来节点成为新根节点的左子节点。这样，左旋操作完成后，原来节点的右子节点会上升为新的根节点，而原来节点会变为新根节点的左子节点。 　　右旋（Right Rotation）：右旋操作是将一个节点的左子节点变为其父节点，同时将左子节点的右子节点变为该节点的左子节点。让当前节点的左子节点成为新的根节点。将新根节点的右子节点（如果存在）移动为原来节点的左子节点。将原来节点成为新根节点的右子节点。右旋操作会导致原来节点的左子节点上升为新的根节点，而原来节点会变为新根节点的右子节点。 　　左旋和右旋的过程，改变了哪些东西呢？左旋需要改变三个方向共六个指针的指向，以上图为例：改变X的右指针。改变Y的左指针。改变X父结点的指针。 　　这三个指针是双向的，所以是六个指针（比如X的右指针指向Y，Y的父指针指向X）。即X的右指针改为指向Y的左结点，Y的左指针改为指向X，X的父结点指针改为指向Y。 　　右旋与左旋同理，它们是一个互逆的过程。 　　以根结点示例：

左旋和右旋互逆 　　小结：红黑树插入或删除节点，最多需要旋转的次数是树的高度。 　　三、红黑树插入节点 　　红黑树本质上是一个二叉树，所以它的插入过程和二叉树的插入过程相似。从根节点开始，比当前节点大的走右子树，比当前节点小的走左子树。比如如下的插入12这个节点： 　　红黑树的插入路径 　　当插入结点时，可以推断出以下情况（比如插入的结点是z）： 　　（1）z肯定是红色； 　　（2）z的父节点是红色； 　　（3）z的祖父结点肯定是黑色； 　　（4）z的叔结点颜色不确定。 　　所以，判断条件主要在叔父节点上。最简单的示例如下： 　　叔父节点是黑色，右旋 　　叔父节点是红色，变色 　　更复杂的例子，先以 父结点是祖父结点的左子树的情况（假设插入的节点是z）： 　　（1）叔节点是红色；这种情况最简单，这个状态下树本身的重量是平衡的，不需要旋转，直接将父节点和叔节点变黑色，祖父节点变红色。 　　叔节点是红色，变色 　　（2）叔结点是黑色的，而且当前结点是右孩子。可以看到祖父节点的左边节点比较多而右边比较少，将当前指针保存的节点变为保存父节点，然后从当前节点执行左旋操作，让当前节点变成左子树。这是一个中间状态，还需要下一步操作才能平衡。

执行左旋操作 　　（3）叔结点是黑色的，而且当前结点是左孩子 。可以看到祖父节点的左边节点比较多而右边比较少，所以需要祖父节点执行右旋操作，并进行变色；最终达到平衡。

祖父节点右旋 　　插入节点的过程主要就是这三种状态，理解了父结点是祖父结点的左子树的情况，那么理解父结点是祖父结点的右子树的情况就容易多了。 　　父结点是祖父结点的右子树的情况与父结点是祖父结点的左子树的情况是相似的，这里就不赘述了。 　　四、红黑树删除节点 　　红黑树的删除分如下几种情况： 　　（1）没有左右子树。直接删除，比如：

没有左右子树，直接删除 　　（2）有左子树或者右子树。修改父节点的子树指向当前节点的左子树或者右子树，然后删除当前节点。比如：

有右子树没有左子树时 　　（3）有左子树且有右子树，需要找到覆盖节点、 删除节点、轴心节点。比如下面的示例， 10是覆盖节点、11是删除节点，12是轴心节点：

有左子树且有右子树情况 　　（4）先讨论当前结点是父结点的左子树的情况。 　　1）当前结点的兄弟结点是红色的。删除当前节点，改变父节点为红色，同时改变兄弟节点为黑色，再进行右旋调整。

当前结点是父结点的左子树的情况且兄弟结点是红色的 　　2）当前结点的兄弟结点是黑色的，而且兄弟结点的两个孩子结点都是黑色的。删除当前节点，修改兄弟节点和叔父节点为红色。

当前结点的兄弟结点是黑色的，而且兄弟结点的两个孩子结点都是黑色的 　　3） 当前结点的兄弟结点是黑色的，而且兄弟结点的左孩子是红色的，右孩子是黑色的当前结点是父结点的左子树的情况。 　　4） 当前结点的兄弟结点是黑色的，而且兄弟结点的右孩子是红色的。

3情况和4情况的示例

2情况和3情况的示例 　　（5）当前结点是父结点的右子树的情况。这种情况和【当前结点是父结点的左子树的情况】同理。 　　五、红黑树的查找 　　红黑树首先是一颗二叉搜索树，也就是每个节点的左子树中的值都小于它自身的值，而右子树中的值都大于它的值，这样可以通过比较大小来逐步缩小查找范围。 　　查找操作在红黑树中与普通二叉搜索树类似。从根节点开始，递归地比较要查找的值与当前节点的值。如果要查找的值比当前节点值小，就继续在左子树中查找；如果要查找的值比当前节点值大，就继续在右子树中查找；如果相等，则找到了目标节点。 　　六、完整代码 　　代码已上传github和gitee。 　　github：LongTengFly/RedBlackTree: This is a red black tree component implemented in c language (github.com) 　　总结 　　红黑树需要理解的难点：性质、旋转、插入、删除。红黑树是一种二叉树，中序遍历绝对有序。当红黑树的性质被破环时，需要触发旋转，进行调整。旋转有两种方式：左旋和右旋。红黑数平衡主要是平衡黑高，即任一结点到其子叶子结点的黑色结点数量相同。红黑树的插入和删除会影响红黑树的性质，需要做调整。