只要是一棵树, 就得看看如何生长, 如果树不平衡, 在进行查找操作的时候, 就可能出现性能低下. 什么是平衡呢, 在排序的时候已经简单的用图表示过, 可以加权或者将小树附加到大树上.
平衡二叉树的思路也是如此. 那么什么是平衡呢, 所谓平衡, 就是指所有空节点到根节点的距离应该是相同的.
看了一晚上终于明白了红黑树的道理, 其实算法这一节没有叫红黑树的原因我也明白了, 红其实就是一个标记, 只要被标记了红, 这个链接的两端就起到平衡的作用, 相当于一个天平的两端, 实时平衡其两头挂载的内容.
不过这博客可真难写, 还是用自己的语言来描述一下吧.
2-3树
为了引出红黑树, 算法先介绍了2-3树, 还有3结点和4结点, 我觉得, 这里的核心其实引入了平衡的概念, 就是如何将节点拆分成二叉树以保持平衡.
这本书之前提到过二叉树在数组上的投影, 但是这里没有提, 我觉得用这个来理解最方便.
什么是平衡, 所谓平衡, 就是各个底部的数字到最上边根节点的距离相等. 换种我的理解方式, 也就是树的两侧的元素的数量几乎相等.
假如现在数组里放着456三个数字, 想象成一个尺子上刻着159三个数字, 要把这个尺子拿起来保持两端平衡, 肯定是用手提住中点的位置, 此时就是这样的:
手提着这里
|
---------------
1 5 9
现在想象尺子是柔软的, 将5往上提, 就变成了一个下挂两个4和6节点的5节点, 也就是一棵二叉树.
现在如果再放入一个4,会发生什么情况呢, 按照原来二叉树的放法, 4小于5, 去找左侧, 4大于1, 找右侧,右侧没有, 就放到1的右侧, 此时的投影是:
应该手提着这里
|
---------------
1 4 5 9
这个时候如果还是拿起这根软尺子要保持平衡, 要拿哪个地方呢? 很显然, 如果不指定一定要拿到哪个元素的话, 手需要拿在4和5中间的位置, 才能保证两侧的元素数量相等, 也就是平衡了.
问题是我们的手必须要提着一个结点, 每个数字就是一个节点, 按照就近原则的话, 其实提4或者5都是可以的, 如果提起来4(也就是把4当做根节点), 按照二叉树的排布, 应该是这样的:
|
4
/ \
1 5
\
9
如果提着5, 那么二叉树是这样的:
|
5
/ \
4 9
/
1
可以看到, 无论提起4和5, 整体的平衡性是一样的, 都是非常靠近中点的. 那么我们可以把4-5叫做一个平衡点组(我自己起的名字, 也就是说4和5共同构成了一个树的平衡点), 无论用手拎起4还是5, 都没有问题.
那么如何标识这个平衡点组呢, 就用一根红线将二者连起来, 这就是红链接. 算法书上定义了被红链接指向的节点颜色设置为红, 但其实对于红链接两端被链接的点来说, 其实二者共同构成了一个平衡点.
在有了平衡点组的时候, 实际上就可以重新取得平衡:
|
4---5
/ \
1 9
当然这个只是理想的图, 具体到底拎起哪一端呢, 教材的例子是不允许有红色右链接存在, 那么我们就可以得到固定的表示方法, 也就是永远拎起平衡点组右侧的结点, 变成如下:
|
5
/ \
4 9
/
1
然后就可以发现如下几点:
- 有没有必要存在两个相连的红链接? 答案是没有必要性, 两个相邻的红链接意味着平衡点组有3个结点, 这其实相当于一个三个数字的尺子, 没有必要用红链接, 直接从当中一拎起来, 还是平衡的,
所以直接改成黑色链接也就是普通链接就可以了. - 既然拎一个红链接的左边和拎右边都可以保持平衡, 现在我们是强行规定必须拎右边, 如果已经有了一个拎起左边节点的树, 现在要改成拎右边, 该如何操作呢?
还是用例子来说明: 现在有如下的一个最简单的树, 这个数将5-9看做一个平衡点的话, 左侧有一个元素(3), 右侧有2个元素(7和10), 拎起来哪一端应该都不会影响平衡性:| 5 / \ 3 9 / \ 7 10很显然, 我们现在要做的就是从拎起5改成拎起9, 如果直接拎起来, 显然不行, 这样9下挂了3个节点, 这个时候可以发现, 7代表的树, 一定是小于9而且大于5的部分, 所以只要把7挂到5的右侧就可以了
改成拎起9之后的情况如下:| 9 / \ 5 10 / \ 3 7此时由于5-9之间依然是红链接, 没有改变颜色, 所以可以继续将5-9看做一个平衡点, 此时平衡点左侧有两个元素, 3和7, 右侧有一个元素, 10, 依然是2-1, 这也是左右元素数量不等的时候我们提起的最靠近中点,
而且也符合不允许有右侧红链接的操作了.
这里还有一些小细节, 比如最上边这根线的颜色, 很显然应该是黑色, 否则就是两个连续的红链接, 可以修改成黑链接, 相当于把中间的点给提起来(我把这个叫做换色操作, 换色还有一个特点就是要把新拎起来的点上边的链接换成红色,
这是因为换色相当于新插入了一层结点, 比如本来拎5或者9, 现在来了一个6, 既然要拎起来6, 相当于新插入了6, 打破了原来的平衡点组. 换色同时还将红链接向上传递, 得以继续处理, 很有意思.).
这就可以一层一层向上传导, 先平衡最下边的树, 再平衡上一层, 以此类推.刚才完成的这个操作, 就是左旋, 所谓左旋, 就是把红链接从右边转到左边, 类似的也有右旋, 把红链接从左侧转到右侧, 根据我们的分析, 一个平衡点组里拎起谁都行, 那自然左旋和右旋不会影响平衡.
既然一棵树左旋和右旋不会影响平衡, 递归的话, 任何红链接左旋和右旋都不会影响平衡.
此外空链接, 也当成黑色.
插入操作原理
将红链接考虑为一个平衡点组之后, 可以发现旋转和换色, 都是针对红链接的操作, 与黑链接完全没有关系. 而针对红链接的操作, 无论是旋转还是换色, 都不影响新的拎起来的点的平衡性.
既然如此, 插入操作的核心就是, 不管插入到哪里, 始终把插入的元素和父节点之间当成一条红链接, 插入完进行处理就可以了, 如果需要旋转就旋转, 需要拎起来连续红链接(换色操作), 就拎. 反正处理完, 依然不影响平衡性,
这就是插入操作的本质.
这个时候再去看算法书上的向根节点插入新键, 向3-节点中插入新键, 就完全能够理解了, 都是处理红链接而已, 而处理手段不过是旋转和换色, 只要处理完成, 就依然不会影响平衡性.
树在这个过程所谓生长, 其实只是因为人为的认为红链接不计算入元素的长度位置. 但其本质还是二叉树, 红链接只是标记出来了可以进行平衡的位置, 进而执行平衡操作.
根节点始终是黑色, 这个要注意, 否则就会出问题, 所以在每次操作之后都要将其设置成为黑色.
最后这个就变成了一个递归的情况, 过程如下:
- 像普通二叉树一样找到需要插入的位置
- 插入新结点, 将新结点与父节点的链接设置为红链接
- 从父节点开始往回一直到根节点, 对每个节点按照顺序执行下列步骤:
- 右红左黑, 左旋转(处理单独右侧红链接)
- 左红, 左子节点也是红色, 右旋(处理相邻红链接)
- 左右都红, 换色
为什么按顺序执行这三种情况, 这是因为找到当前元素的插入点的时候, 由于整棵树不会存在连续的红节点和右红链接, 新节点X插入之后始终是红链接, 只会有如下几种情况:
一 二 三 四 五 | | | | | C C C C C / \ / \ / \ / \ / \ X D X D A X A X A X- 情况一: 原来的节点都是黑链接, 左侧插进来X红链接, x指向null 是黑链接, 无需进行任何处理, 也不满足上边ABC三条判断的任何一个
- 情况二: 原本的C是红链接, 左侧插进来X红链接, 不满足ABC任何一条, 但是有相邻的红链接, 这个就会在递归到父节点的时候进行处理
- 情况三: 原来的节点都是黑链接, 右侧插入X红链接, 属于A情况, 右红左黑, 左旋之后, 成为情况1, 完成平衡
- 情况四: A红C黑, 插入完之后是两侧都红, 需要换色, 是情况C
- 情况五: A黑C红, 插入完之后右红左黑, 需要左旋, 左旋之后是情况二, 递归给父节点处理
通过分析可以看到, 情况五->左旋->情况二, 情况三->左旋->情况一, 情况四->换色, 所以五种情况只有情况三四五需要处理, 而左旋之后必定没有红色右链接, 所以满足条件先左旋. 不左旋说明剩下右红左红, 右黑左黑,
右黑左红三种情况, 除了右黑左黑无需处理之外, 只有两种情况, 要么全红, 要么是子节点导致连续红链接, 再判断连续红链接需要右旋, 如果不需要左旋也不需要右旋, 那就只剩下两红要处理, 或者压根无需处理了.
Java实现 – 节点
首先是结点的, 依然采用内部类 Node. 然后用布尔值true代表红色, false代表黑色, 并且在结点中存放父节点指向其的链接的颜色:
public class RedBlackLiteBST<Key extends Comparable<Key>, Value> {
private static final boolean RED = true;
private static final boolean BLACK = false;
//特殊的根节点, 要单独指定
private Node root;
//存放总的元素数量
private int n;
private class Node {
//每个结点存放一个键值对
private Key key;
private Value val;
//左右链接
private Node left, right;
//保存父节点指到自己的链接颜色
private boolean color;
public Node(Key key, Value val, boolean color) {
this.key = key;
this.val = val;
this.color = color;
}
}
}
规定空链接是黑色, 所以还需要辅助方法来判断颜色, 将空节点也判断为黑色:
private boolean isRed(Node x) {
if (x == null) return false;
return x.color == RED;
}
Java实现 – 旋转与换色
然后是两个操作, 左旋和右旋:
//这个传入的h, 是指向红链接左端的指针, 方法返回一个指向旋转后的新节点的引用
private Node rotateLeft(Node h) {
assert (h != null) && isRed(h.right);
// x 等于红链接右侧的节点
Node x = h.right;
//然后将x的左连接挂到h的右连接上去
h.right = x.left;
//将h挂到x的左连接上
x.left = h;
//将x设置成h的颜色
x.color = h.color;
//将h设置成红色, 表示x->h是红链接
h.color = RED;
//返回对x的引用
return x;
}
//右旋和左旋只要交换left和right就可以了
private Node rotateRight(Node h) {
assert (h != null) && isRed(h.left);
Node x = h.left;
h.left = x.right;
x.right = h;
x.color = h.color;
h.color = RED;
return x;
}
有了旋转方法之后, 只要获取一个节点, 然后让节点 = rotateLeft(Node x) 就可以获得旋转后的子树的根节点.
换色操作首先要搞清楚针对哪个节点进行操作, 在之前的实现中, 当发现左红,左子节点也是红的时候, 就针对当前节点进行右旋, 旋转完之后, 三个相连的红结点当中的结点就是新的父节点, 针对这个节点进行换色:
private void flipColors(Node h) {
//判断是否满足换色条件, 即左红右红
assert !isRed(h) && isRed(h.left) && isRed(h.right);
//强制改变自己的颜色为红色
h.color = RED;
//设置两个子节点为黑色
h.left.color = BLACK;
h.right.color = BLACK;
}
Java实现 – 插入
插入的原理已经分析完了, 插入的部分和普通二叉树没有区别, 都是找到要插入的位置. 但是要注意新节点的颜色一定是红色, 插入完成之后, 就要从父节点开始进行递归处理.
//对外暴露的API, 强制设置根节点为黑色, 然后会递归的返回整理过的红黑树的根节点
public void put(Key key, Value val) {
root = insert(root, key, val);
root.color = BLACK;
assert check();
}
private Node insert(Node h, Key key, Value val) {
//直到找到空结点, 返回一个新的固定为红色的节点
if (h == null) {
n++;
return new Node(key, val, RED);
}
//这是插入的代码, 不断递归寻找, 更新或者插入新节点
int cmp = key.compareTo(h.key);
if (cmp < 0) h.left = insert(h.left, key, val);
else if (cmp > 0) h.right = insert(h.right, key, val);
else h.val = val;
//成功插入的时候, 此时当前的h就是新节点的父节点, 然后一层一层开始处理, 逻辑就是之前插入原理的内容.
//每次都返回处理过的节点引用
if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
if (isRed(h.left) && isRed(h.right)) flipColors(h);
return h;
}
这个代码看上去不复杂, 不过真的, 这种递归方式还得好好理解一下. 尤其是返回一个新节点作为链接的递归, 真的是套路太深了.
Java实现 – 删除
红黑树的删除, 用一句话说, 道理我都懂, 但是代码写不出来.
虽然标题是实现, 但是我现在还实现不了, 看着也有点晕, 二叉树先总结到这里, 平衡性的插入还是很有意思的.
找了篇文章先留着, 哪天脑子清楚了再来看: https://www.cnblogs.com/nullllun/p/8214599.html#autoid-3-2-0
