Java——红黑树

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Java——红黑树，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5843字，纯文字阅读大概需要9分钟。

内容图文

红黑树

1. 定义

首先来理解红黑树可以用来解决什么问题：普通的二叉搜索树在作为数据存储工具的时候，具有可以快速找到一个给定关键字的数据项，并且可以快速地插入和删除数据项等优点。其中，二叉搜索树只有当插入的数据是随机数据，插入可快速进行。但当插入的数值是有序的时候，二叉树就会变成非平衡的二叉树，那么它的快速查找、插入、删除指定数据项的能力就消失了。红黑树就可以解决非平衡树的问题，他可以被理解为是一种增加了某些特点的二叉搜索树。
维基百科中对红黑树的定义为：红黑树（英语：Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。

2. 红黑树性质

一个红黑树具有以下五个性质：
1：节点是红色或黑色。
2：根是黑色。
3：所有叶子都是黑色（叶子是NIL节点）。NIL元素是指每个叶节点都有两个空的，颜色为黑的NIL元素，需要他的时候就可以把它看成两个黑色的元素，不需要的时候可以忽视他
4：每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
5：从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

3. 红黑树的基本操作

红黑树的基本操作和其他树形结构一样，一般都包括查找、插入、删除等操作，但红黑树额外还有旋转以及改变节点颜色等操作。这是因为向红黑树中插入或者删除节点后，红黑树就发生了变化，就会导致树无法满足红黑树的5个性质，那么这个时候就需要通过旋转（左旋、右旋）或者改变节点的颜色使得这棵树能够重新满足红黑树的5个性质。即，红黑树主要靠旋转以及变色操作实现其自平衡的功能。

1. 旋转及变色操作

   左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。
   右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。
   变色：结点的颜色由红变黑或由黑变红。

2. 红黑树查找
   因为红黑树是一颗二叉平衡树，并且查找不会破坏树的平衡，所以查找跟二叉平衡树的查找无异，查找具有以下几个步骤：

   1.从根结点开始查找，把根结点设置为当前结点；
   2.若当前结点为空，返回null；
   3.若当前结点不为空，用当前结点的key跟查找key作比较；
   4.若当前结点key等于查找key，那么该key就是查找目标，返回当前结点；
   5.若当前结点key大于查找key，把当前结点的左子结点设置为当前结点，重复步骤2；
   6.若当前结点key小于查找key，把当前结点的右子结点设置为当前结点，重复步骤2；

3. 插入
   插入操作的步骤如下：

第一步: 将红黑树当作一颗二叉查找树，将节点插入。插入元素的原则：插入元素后不改变其二叉搜索树的性质，以及不改变红黑树的五条性质。 红黑树本身就是一颗二叉查找树，将节点插入后，该树仍然是一颗二叉查找树。也就意味着，树的键值仍然是有序的。此外，无论是左旋还是右旋，若旋转之前这棵树是二叉查找树，旋转之后它一定还是二叉查找树。这也就意味着，任何的旋转和重新着色操作，都不会改变它仍然是一颗二叉查找树的事实。插入元素后，树仍然是一个红黑树，所以插入元素后还得满足红黑树的五条性质。所以我们就得想办法将树进行旋转以及重新着色，使这颗树重新成为红黑树！

第二步：将插入的节点着色为"红色"。这样做可以降低将其转换为红黑树的难度： 若插入的节点是黑色节点，那就违反了性质5，则需要对树进行大规模调整；若插入的节点是红色节点，不会违背红黑树的性质5（但是有可能会违背性质4），这种情况更好调整，所以我们将插入的节点着色为“红色”。

第三步: 通过一系列的旋转或着色等操作，使之重新成为一颗红黑树。（主要是让插入元素后的树满足红黑树的性质4）。

下面是可能遇到的插入的几种状况：
1.当插入的节点是根节点时，直接将其颜色变黑即可；
2.当要插入的节点的父节点是黑色的时候，这个时候插入一个红色的节点并没有对这五个性质产生破坏。所以直接插入不用再进行额外的调整操作；
3.如果要插入的节点的父节点是红色且父节点是祖父节点的左支的时候，这个要分两种情况，一种是叔叔节点为黑色节点的情况，一种是叔叔节点为红色节点的情况。当叔叔为黑色节点时，也分为两种情况，一种是要插入的节点是父节点的左支，另一种是要插入的节点是父亲的右支。
a.当要插入的节点是父节点的左支的情况：这个时候违反了性质4，我们可以通过对祖父节点进行右旋同时将祖父节点和父节点的颜色进行互换，经过这样的调整可以符合性质4并且不对其他性质产生破坏。
b.当插入的节点是父节点的右支的时候：我们可以先对父节点进行左旋，如果我们把原先的父节点看做是新的要插入的节点，把原先要插入的节点看做是新的父节点，那就变成了当要插入的节点在父节点的左支的情况，然后就按照当要插入的节点在父节点的左支的情况进行旋转；
4.如果要插入的节点的父节点是红色且父节点是祖父节点的右支的时候，这个时候的情况跟情况3所表述的情况是一个镜像，将情况3的左和右互换一下就可以了。
5.如果要插入的节点的父节点是红色并且叔叔节点也为红色，这个时候，只需将父亲节点和叔叔节点涂黑，将祖父节点变成红色。

4. 删除

首先我们回顾以下普通二叉树的删除操作：
1.如果删除的是叶节点，可以直接删除；
2.如果被删除的元素有一个子节点，可以将子节点直接移到被删除元素的位置；
3.如果有两个子节点，这时候就可以把被删除元素的右支的最小节点（被删除元素右支的最左边的节点）和被删除元素互换，我们把被删除元素右支的最左边的节点称之为后继节点（后继元素），然后在根据情况1或者情况2进行操作。

下面所称的被删除元素，皆是指已经互换之后的被删除元素。加入颜色之后，被删除元素和后继元素互换只是值互换，并不互换颜色。

下面开始讲一下红黑树删除的规则：
1.当被删除元素为红时，对五条性质没有什么影响，直接删除。
2.当被删除元素为黑且为根节点时，直接删除。
3.当被删除元素为黑，且有一个右子节点为红时，将右子节点涂黑放到被删除元素的位置。
4.当被删除元素为黑，且兄弟节点为黑，兄弟节点两个孩子也为黑，父节点为红，此时，交换兄弟节点与父节点的颜色。
5.当被删除元素为黑、并且为父节点的左支，且兄弟颜色为黑，兄弟的右支为红色，这个时候需要交换兄弟与父亲的颜色，并把父亲涂黑、兄弟的右支涂黑，并以父节点为中心左转。
6.当被删除元素为黑、并且为父节点的左支，且兄弟颜色为黑，兄弟的左支为红色，这个时候需要先把兄弟与兄弟的左子节点颜色互换，进行右转，然后就变成了规则5一样了，在按照规则5进行旋转。
7.当被删除元素为黑且为父元素的右支时，跟情况5情况6 互为镜像。
8.被删除元素为黑且兄弟节点为黑，兄弟节点的孩子为黑，父亲为黑，这个时候需要将兄弟节点变为红，再把父亲看做那个被删除的元素（只是看做，实际上不删除），看看父亲符和哪一条删除规则，进行处理变化。
9.当被删除的元素为黑，且为父元素的左支，兄弟节点为红色的时候，需要交换兄弟节点与父亲结点的颜色，以父亲结点进行左旋，就变成了情况4，在按照情况四进行操作即可。

https://blog.csdn.net/sun_tttt/article/details/65445754
《Java数据结构和算法（第二版）》

内容总结

以上是互联网集市为您收集整理的Java——红黑树全部内容，希望文章能够帮你解决Java——红黑树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端