深入学习红黑树
无
之前只是大致了解红黑树，是一种查询和插入都是log(n)的数据结构。
与之相似的数据结构，Redis 底层 zset 使用的跳表，也是查询和插入都是log(n)的数据结构。
两者大部分情况下性能接近，但是跳表实现更为简单。Redis作者也阐述了使用跳表的原因：
There are a few reasons:
1) They are not very memory intensive. It's up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.
2) A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.
3) They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.About the Append Only durability & speed, I don't think it is a good idea to optimize Redis at cost of more code and more complexity for a use case that IMHO should be rare for the Redis target (fsync() at every command). Almost no one is using this feature even with ACID SQL databases, as the performance hint is big anyway.About threads: our experience shows that Redis is mostly I/O bound. I'm using threads to serve things from Virtual Memory. The long term solution to exploit all the cores, assuming your link is so fast that you can saturate a single core, is running multiple instances of Redis (no locks, almost fully scalable linearly with number of cores), and using the "Redis Cluster" solution that I plan to develop in the future.
跳表有一个额外的特性是支持顺序访问（区间访问），每一个数据节点都有指向上下的指针。典型应用例子：排行榜，可以根据score排名，取出排名xx-xx名的元素。
想要红黑树实现这个额外的特性，我们也可以对其拓展为区间树，实现上会更麻烦。
网上不乏红黑树的定义：
1.节点是红色或黑色。
2.根是黑色。
3.所有叶子都是黑色（叶子是NIL节点）。
4.每个红色节点必须有两个黑色的子节点。（或者说从每个叶子到根的所有路径上不能有两个连续的红色节点。）（或者说不存在两个相邻的红色节点，相邻指两个 节点是父子关系。）（或者说红色节点的父节点和子节点均是黑色的。）
6.从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
这么多规则，可能确实也能背下来，但是看了网上很多红黑树的实现和原理，有很多不一样的地方，又确实都符合红黑树的定义。比如2-3树到红黑树，但是好像通常的红黑树，和2-3树实现的红黑树，又好像有所区别，2-3树实现的红黑树，黑色子节点只有一个红色子节点。
那么，到底什么是红黑树呢？
说到红黑树，不得不提一下，左倾红黑树（LLRB），右倾红黑树（RLRB），AA树。
左倾红黑树（LLRB）：一个节点如果有红色子节点，那么，它的红色子节点是向左倾斜的。
右倾红黑树（RLRB）：一个节点如果有红色子节点，那么，它的红色子节点是向右倾斜的。
以上两种红黑树，当节点的红色子节点，只有一个的时候，会分别在左和右，有两个的时候，没有区别。
AA树：是指红黑树中所有的红色子节点必须只能是右节点，左子节点一律不允许是红色子节点。
左倾和右倾红黑树，因为其子节点可以有两个红色子节点，所以对应的父节点，相当于有两个同级节点，对应的是4节点，所以对应的应该是2-3-4树。
而AA树，因为其黑色子节点，只能拥有一个红色子节点，故而对应的是一个3节点，所以对应的是2-3树。
故以上几种红黑树，虽然都符合定义，但实现起来，和其最终的形态都是有所差异。
网上的一些教程，并没有阐述红黑树的种类细分，只是在阐述定义，和实现其中一种红黑树，不同的教程实现的红黑树种类不同，故而可能会给读者带来困惑。
今天，自己实现一个2-3树对应的类似AA树，与一般AA树的区别，是我会使用左边的红色子节点。
准备coding之前，先画图
将一个顺序1-10插入的2-3树，转为红黑树，平级的左链接则为红链接，对应子元素为红色。
然后变换一些2-3树插入过程中需要的操作（所有插入均在叶子节点完成）：
一个2节点插入新元素，变成3节点：将新元素根据父节点大小，挂在左边或者右边，为红链接。如果是挂在右边，右边的红链接不符合定义，需要左旋。举个例子，如果最后两个元素从9和10，改成10和11，在2-3树直接插入，如果是红黑树，需要左旋，然后重新上色。
一个3节点插入新元素，变成临时的4节点：临时的4节点，我们可以增加临时的红链接表示，即中间值左右两边都是红链接。但是插入过程没那么简单，分以下几种情况：
如果新元素大于黑色节点，很简单，直接加一个右边的红链接就行。
如果新元素大于红色节点，小于黑色节点，则挂在红色节点的右边子节点，然后先左旋红节点，再右旋原来的黑节点，使新节点在中间，染黑，并把原先的两个节点染红。
如果新元素小于红色节点，则挂在红色节点的左边子节点，右旋原来的黑节点，然后红节点染黑，新节点和黑色节点染红。
然后继续接下来的步骤：
1.需要把中间值提给父节点（如果是2节点）合并：分以下情况
中间值小于父节点，即中间值在原先父节点的左子节点，这时候直接染红中间值。
中间值大于父节点，即中间值在原先父节点的右子节点，如果这时候直接染红中间值，会变成右连接，不符合定义，所以需要左旋一次，原先父节点变成中间值的左子节点，然后染红父节点，对应一个3节点。
2.需要把中间值提给父节点（如果是3节点）合并，父节点变成一个4节点，提取中间值向上传递，不断递归：这个过程在红黑树中需要判断
中间值为左子树，中间值小于父红节点：右旋一次黑节点（祖父节点），然后将中间值和祖父节点染红，往上提父节点。
中间值为左子树，中间值大于父红节点，但小于祖父节点：先将中间值两子树染黑，左旋一次父节点，将原先父节点染红，再右旋一次祖父节点，把祖父节点染红，中间值染黑，再把中间值提上去。
中间值为右子树，则中间值大于父节点和兄弟节点（红节点）：不用旋转，直接把中间值变红，两子树变黑，再把父节点网上传递即可。
然后接下来理清删除节点的思路
1.删除节点在3叶子节点，直接删除：红黑树中，如果删除节点为红节点，直接删除，如果为黑色节点，先右旋，红节点染黑，删除原先的黑节点。
2.删除节点为2叶子节点
父节点为2节点，没有兄弟节点，此情况不存在，被删除节点应该和父节点合并为3节点。
父节点为2节点，兄弟为3节点，则一定是3叶子节点（因为如果有子节点，插入时会向上传递，父节点会变成3-节点），则删除后，向兄弟节点借靠近被删除节点的元素，补到原先的为止，并且和父节点换位置以满足大小关系：对应到红黑树里，如果被删除的是左子节点，把对应元素删除，把兄弟节点右旋，然后再把父节点左旋，并都染黑。如果被删除是右子节点，对应元素删除，父节点右旋。
父节点为2节点，兄弟为2叶子节点，则删除后，兄弟节点和父节点合并为一个3节点：红黑树中，作为左子节点删除，删除后，父节点左旋，再把原先的父节点染黑；作为右子节点删除，删除后，把兄弟节点染红。
父节点为2节点，兄弟为2节点，并且有子节点，此情况不存在。因为兄弟节点为2节点且带子节点，即一个4节点，插入时候，多出来的值应该已经向上传递，父节点不可能为2节点。
父节点为3节点，删除元素后，父节点降元为2节点，拆分出一个元素与子节点合并为3节点：对应到红黑树，如父节点为红色，且删除节点在左侧，则删除后，左旋父节点；若删除节点在右侧，则父节点染黑，父节点的左节点染红，如果父节点为黑色，则删除后右旋父节点，把右旋后的父节点的父节点染黑，父节点左子节点染红。
- 删除的节点非叶子节点（父节点）
如果在2-3树中，还要区分2节点和3节点，分别做一下不同处理，递归找到比他小的左子树中的最大右元素。
在红黑树中，我们可以直接遍历左子树就行，作为父节点，左子树一定不为空，至少有一个红节点，找到最大的节点和父节点交换，然后删除原来的父节点。
思路清晰以后，我们先写一下基础类：
class RbTree
attr_accessor :root, :nil_node
def initialize
self.nil_node = RbTreeNode.new(nil, color: 'black')
self.root = nil_node
end
end
class RbTreeNode
attr_accessor :left, :right, :parent, :value, :color, :key
def initialize(key, color: 'black', value: nil)
self.value = value
self.key = key
self.color = color
end
end
左旋、右旋、交换节点的代码：
# source 作为被交换的父元素，parent 有可能为空
# target parent 一定不为空
# 交换后可能要处理一下root
def swap_node(source, target)
source_parent = source.parent
if source_parent
as_left = source_parent.left == source
end
source_left = source.left
source_right = source.right
source.parent = target.parent
source.left = target.left
source.left.parent = source if source.left
source.right = target.right
source.right.parent = source if source.right
target.parent = source_parent
target.left = source_left
target.left.parent = target if target.left
target.right = source_right
target.right.parent = target if target.right
if source_parent
if as_left
target.parent.left = target
else
target.parent.right = target
end
else
self.root = target
end
end
def left_rotate(node)
p_node = node.parent
right = node.right
node.right = right.left || nil_node
node.right.parent = node
right.left = node
right.parent = p_node
node.parent = right
if p_node
if p_node.left == node
p_node.left = right
else
p_node.right = right
end
else
self.root = right
end
end
def right_rotate(node)
p_node = node.parent
left = node.left
node.left = left.right || nil_node
node.left.parent = node
left.right = node
left.parent = p_node
node.parent = left
if p_node
if p_node.left == node
p_node.left = left
else
p_node.right = left
end
else
self.root = left
end
end
插入过程中，把中间值向上传递的过程：
# 向上传递中间值节点
def pass_up_node(source)
source.left.color = 'black'
source.right.color = 'black'
if source == root
source.color = 'black'
return
end
p_node = source.parent
# 父节点是2节点
if p_node.color == 'black' && p_node.left.color == 'black'
# source在左子树
if source.key < p_node.key
source.color = 'red'
# source在右子树
else
left_rotate(p_node)
source.color = 'black'
p_node.color = 'red'
end
# 父节点是3节点
else
if source == p_node.left
source.color = 'red'
p_node.parent.color = 'red'
p_node.color = 'black'
right_rotate(p_node.parent)
pass_up_node(p_node)
else
if p_node.color == 'black'
source.color = 'red'
pass_up_node(p_node)
else
p_node.color = 'red'
p_node.parent.color = 'red'
source.color = 'black'
left_rotate(p_node)
right_rotate(source.parent)
pass_up_node(source)
end
end
end
end
插入新值的过程：
def set(key, value)
key = "#{key.class}_#{key}"
new_node = RbTreeNode.new(key, value: value)
new_node.right = nil_node
new_node.left = nil_node
if root.key.nil?
self.root = new_node
else
p_node, pos = b_search(key)
if pos == 'equal'
p_node.value = value
return
end
# 插入到一个2节点
if p_node.left.key.nil? && p_node.color == 'black'
new_node.parent = p_node
p_node.send("#{pos}=", new_node)
if pos == 'right'
left_rotate(p_node)
p_node.color = 'red'
else
new_node.color = 'red'
end
# 插入到3节点
else
if p_node.color == 'red'
if pos == 'right'
new_node.parent = p_node
p_node.right = new_node
left_rotate(p_node)
right_rotate(p_node.parent.parent)
new_node.color = 'black'
new_node.left.color = 'red'
new_node.right.color = 'red'
pass_up_node(new_node)
else
new_node.parent = p_node
p_node.left = new_node
right_rotate(p_node.parent)
p_node.color = 'black'
p_node.left.color = 'red'
p_node.right.color = 'red'
pass_up_node(p_node)
end
else
new_node.parent = p_node
p_node.right = new_node
new_node.color = 'red'
pass_up_node(p_node)
end
end
end
end
alias_method :[]=, :set
def search(key)
key = "#{key.class}_#{key}"
node , pos = b_search(key)
if pos == 'equal'
node.value
else
nil
end
end
alias_method :[], :search
def b_search(key, node = root)
if node.key > key
if node.left.key
b_search(key, node.left)
else
return [node, 'left']
end
elsif node.key < key
if node.right.key
b_search(key, node.right)
else
return [node, 'right']
end
else
[node, 'equal']
end
end
最后加上benchmark，原生的哈希表，第三方用c写的红黑树的gem，以及自己写的红黑树进行对比，性能与c写的红黑树，勉强算是同一数量级，还不错！
rbt = RbTree.new
hash = {}
require 'rbtree'
rbt1 = RBTree.new
Benchmark.bm do |x|
puts '原生哈希写入'
x.report do
1000000.times do |i|
hash[i + 10000000000] = i
end
end
puts '原生哈希读取'
x.report do
1000000.times do |i|
hash[i + 10000000000]
end
end
puts 'c写的rbt写入'
x.report do
1000000.times do |i|
rbt1[i + 10000000000] = i
end
end
puts 'c写的rbt读取'
x.report do
1000000.times do |i|
rbt1[i + 10000000000]
end
end
puts '自己写的rbt写入'
x.report do
1000000.times do |i|
rbt[i + 10000000000] = i
end
end
puts '自己写的rbt读取'
x.report do
1000000.times do |i|
rbt[i + 10000000000]
end
end
end
发表于 2023.07.24
© 自由转载 - 非商用 - 非衍生 - 保持署名