失眠网 > 【算法】红黑树插入数据（变色左旋右旋）（二）

【算法】红黑树插入数据（变色左旋右旋）（二）

时间：2021-10-24 11:15:00

本人菜鸡一只，正在更新红黑树系列的文章。

该系列已经全部更完，有5篇文章：

【算法】红黑树（二叉树）概念与查询（一）：/lsr40/article/details/85230703

【算法】红黑树插入数据（变色，左旋、右旋）（二）：/lsr40/article/details/85245027

【算法】红黑树插入数据的情况与实现（三）：/lsr40/article/details/85266069

【算法】红黑树删除数据（寻找继承人）（四）：/lsr40/article/details/85322371

【算法】红黑树删除数据（最后一步，平衡红黑树）（五）：/lsr40/article/details/86711889

如果想要在查询的时候能够使用到红黑树的查询优化的时候，必须把数据先加载到红黑树中，加载到红黑树中其实就是put，就是一个构建红黑树的过程！

学习怎么构建红黑树之前，我们必须掌握几个基本的知识！

1、红黑树在插入数据的时候，会先遍历数据应该插入到哪个位置，插入的位置肯定在底部，不可能在中间突然插入一个值。

2、插入的数据一定是红色的（因为要遵守红黑树的第五条规则，如果有一条分支增加了一个黑色节点，就会打破该规则）

3、插入之后，为了满足规则4，就需要用到换色与左旋、右旋的操作了

换色，其实就是红变黑，黑变红，只需要让某个对象的属性改变就可以了，没什么好说的。

重要的是什么是旋转，为什么要旋转，什么时候选择左旋，什么时候旋转右旋？

1、旋转分两种：

-1.左旋

大家看如下三张图，对于x做左旋

原始的样子：

正在变换：

变换结束：

-2.右旋

大家看如下三张图，对于y做右旋

原始的样子：

正在变换：

变换结束：

所以，我们发现左旋和右旋是一个相对的操作。

关于红黑树旋转的代码，其实很简单，我大概说一下如何实现，其实每个节点有这么几个属性：

1、父节点的指向

2、子节点的指向（有两个，一个左子节点，一个右子节点）

3、该节点的颜色

4、该节点存储的value（当然如果是map，那就是该节点的key和value都要存，然后按照key的大小来插入新节点）

所以当我们做旋转的时候，只需要把该节点的父节点指向该节点的子节点，然后把子节点的一条腿接到该节点上。

详情看TreeMap的源码：

左旋转我加了中文注释，大家可以对照，我上面画的左旋转的图去理解旋转的过程，java如何实现

/** From CLR *///从TreeMap类中的2221行开始private void rotateLeft(Entry<K,V> p) {//这里的p就是图中绿色的xif (p != null) {//r就是图中的yEntry<K,V> r = p.right;//x.right变成y.leftp.right = r.left;//如果y的左腿不为空if (r.left != null)//设置y.left的父节点为x（必须双向设置）r.left.parent = p;//x的父节点，变成了y的父节点r.parent = p.parent;//如果x的父节点为空，证明x就是根节点if (p.parent == null)//那么y就变成了根节点root = r;//如果x是父亲的左子节点，x的父亲的左子节点就变成了yelse if (p.parent.left == p)p.parent.left = r;else//否则x就是父亲的右子节点，x的父亲的右子节点就变成了yp.parent.right = r;//x变成了y的左子节点r.left = p;//x的父亲变成了yp.parent = r;}}/** From CLR */private void rotateRight(Entry<K,V> p) {if (p != null) {Entry<K,V> l = p.left;p.left = l.right;if (l.right != null) l.right.parent = p;l.parent = p.parent;if (p.parent == null)root = l;else if (p.parent.right == p)p.parent.right = l;else p.parent.left = l;l.right = p;p.parent = l;}}

当然，到现在我们还不知道到底为什么要旋转？