红黑树的左旋java代码 红黑树csdn

有关红黑树的java程序，编译成功但运行不出结果。

java8不是用红黑树来管理hashmap，而是在hash值相同的情况下（且重复数量大于8），用红黑树来管理数据。 红黑树相当于排序数据。可以自动的使用二分法进行定位。性能较高。

一般情况下，hash值做的比较好的话基本上用不到红黑树。

相关问答

Q1: 红黑树-算法导论

这个周看算法导论，看到红黑树，看的我云里雾里绕啊。虽然最后看懂了，据我估计，要是过一个星期不看保证忘干净，因此决定写篇博客记录下红黑树。

红黑树是二叉树的一种，所以学习红黑树必须先搞懂二叉树。

如图，一颗二叉树是按照结点（二叉树结构）组成的。每个结点可以用链表结构标示。每个结点都应该有left right p ，他们分别指向左儿子，右儿子和父结点。每个结点还应该有个关键字key。如果某个儿子结点不存在，则相应位置就是nil。跟结点是树中唯一的父结点值是nil的节点。

设x为二叉树中的一个结点，如果y是x的左子树中的一个结点，则key[y]=key[x]。如果y是x的右子树中的一个结点，则key[x]=key[y]

我们有很多结点，如何将他组合成符合二叉树性质的二叉树呢？

我们一般通过下面两种方式遍历二叉树中的key

树根的关键字（key）在左子树和右子树的关键字之间输出就是 中序遍历算法

树根的关键字（key）在左子树和右子树的关键字之前输出就是 前序遍历算法

从图中我们能看出只要沿着各个结点的left指针查找下去，知道遇见nil 时候为止，就是最小值，最大值正好相反。

如图，3的前趋是2， 后继是6。

前趋后继的规律是什么呢?

前趋：如果结点x的左子树为非空，则x的前趋就是做子树中的最右结点。要是x的左子树为nil ，并且有前趋y（key是最最小值对应的x是没有前趋的），那么y是x的最低祖先，并且y的右儿子也是x的祖先。（x必须出现在y的右儿子的分支中，并且y是最低祖先）

后继：如果结点x的右子树为非空，则x的后继就是右子树中的最左结点。要是x的右子树为nil ，并且有后继y（key是最大值对应的x是没有后继的），那么y是x的最低祖先，并且y的左儿子也是x的祖先。（x必须出现在y的左儿子的分支中，并且y是最低祖先）

这里一定要搞明白，因为这里是红黑树删除的基础部分。

二叉树结点的删除分三种情况。

这里针对第三种情况的删除，我们不是删除z，而是删除的是z的后继y，把y的值赋值给z，这样不破坏树中的结构。变成了只是删除了一个叶子，这个叶子的特点是 左儿子是nil 。

红黑树是一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是RED或者Black。通过对任何一条从跟到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。

树中每个结点包含五个域：color，key ，left，right 和p。如果某结点没有一个子结点或者父结点，则该结点相应的指针为nil。

从图中我们能看出每个叶子节点都是nil。nil对象都是一样的。干嘛不用一个nil 代替呢。因此如下结构。

旋转应该是二叉树的性质，只是普通二叉树没必要旋转。红黑树需要旋转来平衡树结构。

结果如下。

右旋的过程只是相反而已。

左旋的作用是将右儿子变成父结点。

右旋的作用是将左儿子变成父结点。

这样变化有什么用处呢？

我们知道，红黑树就是二叉树，因此向二叉树中插入数据没有啥区别。只是不过，当我们插入结点的某些时候就破坏了红黑树性质。因此，我们需要对二叉树进行调整让其适合红黑树的特性。

下面我们应该分析什么情况下插入结点能破坏红黑树。

假如我们插入的结点是黑色的，肯定是破坏了二叉树的性质5。（除非是根节点不破坏。）

但是我们插入的结点是红色的，不一定破坏二叉树的五条性质，为了方便，我们还是将二叉树插入的结点染成红色的比较好。(情况变少)

当我们插入一个红色结点可能破坏那些性质呢？第一条和第三条肯定是不会被破坏的，恒成立的。第五条因为插入的结点是红色的肯定也是成立的。这里可能不成立的是第二条（跟结点是黑的，要是插入的结点就是根结点）和第四条（如果一个结点是红的，它的两个儿子是黑的，因为要是插入的结点的父结点是红的话，那么父父结点就不符合要求了）。

因此，红黑树的结构被破坏就两种情况，不是性质2就是性质4.

性质2好解决，将结点染成黑色的就行了。不做分析。

我们重点分析性质4破坏，我们如何修正。

我们知道性质4被破坏的条件是父节点是红色的。

如图

这里我们分情况讨论 s 的颜色。

第一种情况 ： s的结点是红色。

这个情况，我们从根到左边的黑色结点数是2 ，右边的黑色结点数是2。

那么我们如何将其变成从跟到叶子的所有路线的结点数是2还不破坏红黑树呢？

只有下面一种变化才能符合红黑树，这样从根向下就符合红黑树了。

将祖父结点（跟结点）变成红色，p 和s 结点都变成 黑节点。

从上面的结果图我们能看出来， 根父 的颜色不定，可能是红色的，也可能是黑色的，那么我们就应该让 根 当做被插入的新节点，遍历根父 的兄弟的结点的颜色情况情况。这其实就是递归了。

要是每个根父的兄弟结点都是红色的话，那么遍历到根就结束了。将根染成黑色即可。要是根父的兄弟不是红色，那么就应该进入到第二种情况了。

第二种情况：s结点是黑色的。

这种情况不管如何变化，让总结点数不变的情况下，单纯染色根本没有办法让所有结点符合红黑树特性。让从根到叶子的路径含有相同的黑色结点。 那么怎么办呢？

我们知道，二叉树可以旋转，旋转可以改变树的结构。

这里我们用根做旋转（左旋或者右旋），结果如下

我们看看旋转结果，结果1，根变成p儿子的一边黑色结点树没有变化。而x的一边黑色结点数量减少了1。那我们如何让x一边增加1呢？只有如下一种情况，将p染成黑色，根染成红色。

结果2是无法达到我们的要求的，因此我们需要抛弃掉这种情况，让s是黑的时候只能变成结果1。

结果1所有的情况下都满足红黑树，不需要进行递归了。

这里我们需要看看什么情况下，x结点是p结点的儿子而不是根结点的儿子。这里我们需要看左旋右旋逻辑图了。

因此这里我们总结下结果1 的条件

结果2 就是剩下的。那么要是结果2的情况，我们应该如何处理呢。

那么结果2 在右旋的结构图就很清晰了。如下。p的右儿子是插入的结点x。

这种情况如何解决呢？

因为x是p的右儿子，所以旋转只能是左旋转。我们以p为根节点旋转。

结果如下

这样就变成了结果1 准备右旋转的的情况了。

同理，情况2的左旋图就变成了结果1准备左旋图的情况了。

总结

这里上面的方法是算法导论给出的，下面的是自己实现的。

删除操作和二叉树的操作一样，同样的只不过是删除的时候，可能引起对红黑树性质的破坏。

这里把删除二叉树的总结搬过来

这里我们罗列下这三种情况各个删除结点的结构。

二叉树第一种情况：没有儿子的情况。

二叉树第二种情况：只有一个儿子。左儿子或者右儿子。有四种情况

二叉树第三种情况：最多有一个右儿子

我们看出来，第三种情况不是第一种情况，就是第二种情况。因此这里我们只需要研究第一种情况和第二种情况就行了。

当x是红色的时候

将x删除，我们发现红黑树的黑色结点的数量不会发生任何变化。红黑树结构正常

我们发现不管什么条件下，删除红色结点红黑树不会发生任何变化。

这里我们需要讨论下 p 和 s的颜色，我们知道p 和s 分别只有红色和黑色，并且p 和s 不能同时为红色。那么p 和s的组合情况只有三种了。

我们发现不管哪一种情况都删除x的那一支都缺少一个黑色结点。

组合1

组合一通过染色是不可能达到树的平衡的。（有人好说了，把p染成黑色，s染成红色不就行了？我刚开始也犯了这个错误，要是s的两个儿子是红色怎么办呢？红色是不参与节点数计算的。）

因此我们这里直能通过旋转来改变树的结构来看看能不能达到我们的要求。我们以p旋转看看结果如下。

这貌似也不行，因为SL 可能是红色的，违反性质4。因此我们可以看出来，p是红色的情况下，旋转一次想让红黑树平衡依赖S的两个结点的颜色。

要是p左旋，那么s的左孩子是黑色的就可以。要是p右旋，那么s的右孩子是黑色的就可以了。

因此这里讨论下s的两个孩子的颜色情况。

如果SL 和SR 都是红色怎么处理呢？

单纯的旋转根本不可能让红黑树成立。只能先改变颜色在旋转了。

颜色改变如下

要是SL 和SR都是黑色的情况下

结构图如下

这种结构图 SL SR 都是nil。这种情况下旋转一下 p就行了。

SR SL只有一个颜色是红色的。如果p的删除分支是左儿子。那么SL 是红色，只能以s先右旋转。这样就变成了 SL SR都是黑色，但是s是红色的情况。是SL ,SR变化成平衡树的中间过程

最后这种情况，和SL SR 都是黑色一样的处理。

组合2

这里我们单纯靠染色是不可能实现树平衡的。因为删除x的结点的一支的结点都是黑色的。没有可以改变的红色结点存在。怎么办呢？我们只能通过旋转将删除的节点的一支上面增加红色结点才行。这里有个s是红色的，我们需要让其到删除结点分支上。

旋转结果

这样组合2删除结点的分支上有红色结点了。到这里我们发现这个地方的树可能违反红黑树了。

违反1：根是红色的话，s是红色违反性质4.

违反2：p结点黑节点数量还是对不上。违反性质5

不过没关系，要是我们能通过染色让树平衡的话，不用再调整树的结构的话，那么组合2也就算是解决了。

貌似通过染色也解决不了这个树平衡的问题，不过违反的红黑树的地方可以减少，我们将s染成黑色，p染成红色。

这里我们发现只有 p删除结点的一支，黑色结点数量少一。正好是组合一的情况。按照组合一的情况做一次旋转就可以解决问题

组合三

这种情况是最复杂的了。我们知道S要是红色，这就是组合2的情况，要是p是红色，那么就是组合1了。那我们想办法怎么让s或者p变成红色的呢？我们先从叶子节点找红色结点，看能不能让s或者p变成红色的。肯定是可以的。不过有一定条件。这里需要依赖SL,SR的颜色了。

当SL,SR都是红色，这种变化只通过改变颜色就可以让s变成红色，变成组合2的情况。

当SL,SR 只有一个红色的时候，通过改变颜色是不能达到要求的。因此我们就需要做旋转来达到要求。

当SL SR 都是黑色。没有红色，p结点一下是不能解决这个问题的。那怎么办呢？这样只能依赖p的父类了。不过这里需要注意的是p本身不平衡，我们这里依赖p的父类的时候，p需要是平衡的。如何平衡p呢？

我们只需要将s变成红色就可以了。p就平衡了。

不过这里注意，p的这一整支的所有分支都是少黑色结点1 的。

这里我们注意到p只有一个儿子。这里我们需要把p当成删除结点x的一个儿子。这样就转换成了x带一个儿子的情况了。这种情况如何平衡树。下面讨论一个孩子的时候包含，暂时不在这里讲解。

先拿一种情况分析 x是p的左儿子，x有一个左儿子

分析L 如果L是黑色的话，肯定是nil。因此可以将这种只有一个儿子的情况转换成没有儿子的情况。也可以这么说，要是x有儿子，儿子的颜色一定不是黑色。而是红色。如图

Q2: java中哪些数据结构使用了红黑树

参考资料的网页上有比较的代码,你可以仔细看下~~~

java中HashMap,LinkedHashMap,TreeMap红黑树的左旋java代码，HashTable的区别

java为数据结构中的映射定义了一个接口java.util.Map;它有四个实现类,分别是HashMap Hashtable LinkedHashMap 和TreeMap

Map主要用于存储健值对红黑树的左旋java代码，根据键得到值，因此不允许键重复(重复了覆盖了),但允许值重复。

Hashmap 是一个最常用的Map,它根据键的HashCode 值存储数据,根据键可以直接获取它的值，具有很快的访问速度，遍历时，取得数据的顺序是完全随机的。HashMap最多只允许一条记录的键为Null;允许多条记录的值为 Null;HashMap不支持线程的同步，即任一时刻可以有多个线程同时写HashMap;可能会导致数据的不一致。如果需要同步，可以用 Collections的synchronizedMap方法使HashMap具有同步的能力，或者使用ConcurrentHashMap。

Hashtable与 HashMap类似,它继承自Dictionary类，不同的是:它不允许记录的键或者值为空;它支持线程的同步，即任一时刻只有一个线程能写Hashtable,因此也导致了 Hashtable在写入时会比较慢。

LinkedHashMap保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的.也可以在构造时用带参数，按照应用次数排序。在遍历的时候会比HashMap慢，不过有种情况例外，当HashMap容量很大，实际数据较少时，遍历起来可能会比LinkedHashMap慢，因为LinkedHashMap的遍历速度只和实际数据有关，和容量无关，而HashMap的遍历速度和他的容量有关。

TreeMap实现SortMap接口，能够把它保存的记录根据键排序,默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator 遍历TreeMap时，得到的记录是排过序的。

一般情况下，我们用的最多的是HashMap,HashMap里面存入的键值对在取出的时候是随机的,它根据键的HashCode值存储数据,根据键可以直接获取它的值，具有很快的访问速度。在Map 中插入、删除和定位元素，HashMap 是最好的选择。

TreeMap取出来的是排序后的键值对。但如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。

LinkedHashMap 是HashMap的一个子类，如果需要输出的顺序和输入的相同,那么用LinkedHashMap可以实现,它还可以按读取顺序来排列，像连接池中可以应用。

Q3: 红黑树——一个自平衡的二叉搜索树

普通的二叉搜索树在最坏的情况下，可能退化成一个链表。而又因为二叉搜索树的所有操作的性能（添加，删除，查找等），与二叉搜索树的高度有关。在最坏的情况下，二叉搜索树的高度和元素个数相同，此时二叉搜索树的效率降为了O(n)级别。

所以为了防止我们的二叉搜索树退化成一个链表，就产生了 平衡二叉树 。 平衡二叉树 可以保证它的左右两个子树的高度差不会超过1。平衡二叉树有很多实现，一个经典实现就是 红黑树 。

在红黑树中将树中的节点划分为两种状态，分别用黑色和红色来表示。

红黑树为了保证自己能够平衡子树，所以制订以下五个规则：

1、每个节点必须有颜色，要么黑色，要么红色，没有别的颜色。

2、根节点必须是黑色

3、所有的空节点(nil节点)都认为是黑色节点。

4、红色的节点不能连续，即一个红色的节点，它的父节点和子节点不能也是红色的，

5、无论从哪一个节点起始，到它每个叶子节点的路径中，黑色节点数量必须相同。

在对红黑树进行添加、删除等操作之后，必须使红黑树符合这5个规则。

那么问题来了，在添加删除操作之后，树中节点的数量都变了，是怎么保证整个树满足上述这些规则呢？

这里涉及到3种操作， 变色 、 左旋 和 右旋 。通过这个三种操作，在增删节点之后调整树的形状结构，使它满足上述5个规则。这也是红黑树能保持平衡的原因。

变色操作 我们在下文的添加、删除节点的实际操作中，再进行在描述。

先来说一下左右旋。

文字描述一下就是，2的右孩子节点4，变为了2的父节点，2由父节点变为4的左孩子。同时，4原来的左孩子变为2的右孩子。

右旋与左旋相反，即以某节点为支点进行顺时针旋转。同样，我们看下图，是以5为支点进行的右旋:

文字描述同样反过来，5的左孩子节点3，变为5的父节点，5由父节点变为3的右孩子。3原来的右孩子变为5的左孩子。

首先是在树中找到新节点正确的位置，寻找位置的过程与普通的二叉搜索树相同，只是将新插入的节点默认为 红色节点 。为什么默认为红色？因为如果你将新节点默认为黑色，则插入后肯定会打破原本符合规则的红黑树（上述第5条规则）。但是，如果你将新节点定为红色，则有可能不用任何操作就符合红黑树规则，如下图，当新插入的红色节点，它的父亲节点为黑色时候，此时已经满足红黑树规则了。所以用红色比黑色好。

如果很不巧，新插入的节点的父亲节点也为红色，因为红色节点不能连续，所以我们需要调整红黑树的结构使其满足规则。在调整的过程中我们会遇到3种需要处理的情况，我们来一一进行说明。

情况1：

插入新节点40， 此时它的父节点为红色，并且它的叔叔节点（即51）也为红色 。此时我们需要进行 变色 操作。 将该节点的父亲节点、叔叔节点都变为黑色，祖父节点变为红色 。

此时上图已经满足红黑树的规则。但有的时候我们经过了变色操作后，仍不满足红黑树的规则，会遇到下面的情况。

情况2：

如图，我们插入新的节点53，在按情况1的操作变色后，变成了这样:

最后我们说一下情况3的情景，如下图：

我们向树中插入新节点37，在按情况1的操作变色后，变成了这样：

情况3：

3种情况我们说明完了，但是你可能还会有这样的疑问，什么时候进行左旋，什么时候进行右旋；什么时候以父节点为支点旋转，什么时候又以祖父节点为支点旋转？

那么我们可以总结一下，当遇到连续的红色节点应该怎么办： 当前节点我们叫它X，如果X相对于父节点的左右位置和父节点相对于祖父节点的左右位置相同，此时，就以祖父节点为支点，进行反向旋转。例如：X为父节点的左孩子，X的父节点同样也是其祖父节点的左孩子，此时以祖父节点为支点进行右旋；

如果X相对于父节点的左右位置和父节点相对于祖父节点的左右位置不同，则以X的父节点为支点，进行旋转，旋转方向与X相对于父节点左右位置相反。例如：X为其父节点的左孩子，X的父节点为祖父节点的右孩子，此时以X的父节点为支点进行一次右旋。

在红黑树中删除节点，肯定要涉及到要删的这个节点是红色的还是黑色的。删除红色比较简单，我们先说一下删除红色节点。

删除节点要考虑这个节点所处的位置，所以我们罗列一下红色的节点所有可能的位置情况。

你可能会发现为什么少了一种情况？它不能只有左子树或者只有右子树吗?我们可以看下图:

很明显，这四种情况都不符合红黑树的规则，所以根本不会出现这种情况。

而对于既有左子树也有右子树的情况。 我们可以先和普通的二叉搜索树的删除操作一样，将它与前驱或者后继交换一下 。它就又变成第一种情况——成为了一个叶子节点。所以我们只需考虑当它是叶子节点的情况。

接下来我们看一下当要删除的节点是黑色的时候应该怎么办。

同样我们列一下节点位置可能的情况：

第三种情况和删除红色节点时的处理方法一样，可以转换成第一种或第二种情况，所以我们只关心前两种情况。

当要删除的黑色节点只有一个子树时：

最后我们看一下最难处理的一种情况。

要删除的黑色节点是叶子节点时：

情况1：待删除黑色节点20，它的兄弟节点为红色。

操作方法为：将远侄子节点变黑，兄弟节点与父亲节点互换颜色，最后以父节点为支点进行 左旋 。(为什么是左旋？因为待删除的20是左孩子，我们要将左子树长度拉长，将它沉下来，使它变成多余的节点好删除它，如果它是右孩子，则进行右旋)

操作后如下图就完成了。

情况3：待删除黑色节点20，它的兄弟节点为黑色，但它没有红色的远侄子节点(即nil点，记住，nil点算黑色)，只有红色的近侄子节点。

操作后如下图:

此时有了红色的远侄子，就满足了情况2，再按情况2进行一次操作就完成了。

情况4：待删除黑色节点20，它的兄弟节点为黑色，远侄子、近侄子节点都没有。(即两个nil节点，nil节点算黑色)

我们将上图红黑树按流程演示一下:

第一步按情况4操作，将55变红。并将父节点50看做当前节点，继续操作。

此时有关红黑树的知识就说完了。

以上所有内容都为自己查阅资料学习理解之后手敲的。尽量得采用通俗易懂的描述和解释让读者更明白。27张图都是自己亲自画的，花费了四天才写完，如果觉得写的还可以，麻烦点亮喜欢支持一下，如果还是不懂，可以下方留言QQ等联系方式，我亲自告诉你。

Q4: 在linux操作系统内核实现里经常使用的红黑树

在linux操作系统内核实现里经常使用的红黑树如下红黑树的左旋java代码：

二叉树红黑树的左旋java代码，按中序遍历后为一递增数组红黑树的左旋java代码，自平衡意味着树的高度有一个上限，对于红黑树，其为2log(n+1)，所以时间复杂度为最差为Olog(n)。

赋予二叉搜索树自平衡特性的方法有多种，红黑树通过一下4条约束实现自平衡:

Every node is either red or black.

All NIL nodes (figure 1) are considered black.

A red node does not have a red child.

Every path from a given node to any of its descendant NIL nodes goes through the same number of black nodes.

其中根节点为黑色。

红黑树的搜索与二叉搜索树无异，但是插入和删除可能会违背上述四条原则。需要用到左旋右旋操作。左旋右旋上图，可以看到左旋右旋本身不改变二叉搜索树的特性，旋转后必要时改变节点的颜色可消除插入或者删除带来的红冲突和黑冲突，有时红黑树的重新平衡需要迭代进行。

红黑树比较适合的应用场景:

需要动态插入、删除、查找的场景，包括但不限于：

某些数据库的增删改查，比如select * from xxx where 这类条件检索。

linux内核中进程通过红黑树组织管理，便于快速插入、删除、查找进程的task_struct。

linux内存中内存的管理：分配和回收。用红黑树组织已经分配的内存块，当应用程序调用free释放内存的时候，可以根据内存地址在红黑树中快速找到目标内存块。

hashmap中(key,value)增、删、改查的实现；java 8就采用红黑树的左旋java代码了RBTree替代链表。

Ext3文件系统，通过红黑树组织目录项。

关于红黑树的左旋java代码和红黑树csdn的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。