接前面

红黑树的插入——层层历历在目想分析一下红黑树是不是红一层黑一层的。直觉告诉我红的少很多。

红黑树转2-3-4树——雨后春笋

里面0到49五十个数顺序插入构造的红黑树里只有5个红色结点。

《算法技术手册》

影印版，全英文的。从那里第一次了解了红黑树，里面说如果编码成功的话，会看到红一层黑一层的。英文是什么不记得了，也可能是我理解错了。里面学到了好多东西。

排序——万亿数量级

文章里的中值排序和点数排序都是从这本书里看到的。

流量第一的图

这张图也特意是黑一层红一层的。

反向构造

使用最佳二叉排序树里的方法构造。

a=[55,38,80,25,46,76,88,17,33,50,72]
B=f(sorted(a))
def breadth_fisrt_level_traversal(node):if node is None: returntemp = []temp.append(node)while temp:q=temp.pop(0)#栈先进后出print(f"({q.d})", end=" ")if q.l:temp.append(q.l)if q.r:temp.append(q.r)    
breadth_fisrt_level_traversal(B)
(50) (33) (76) (25) (46) (72) (88) (17) (38) (55) (80) 

从上面的层序输出看，它不是最佳二叉排序树。

定制代码

python">class rbtnode:'''红黑树的结点类型'''def __init__(self, val):self.val = valself.left = Noneself.right = None#self.parent = Noneself.color = "BLACK"
class rbt:def __init__(self, l):self.root = rbtnode(l[0])#第一个做根for d in l[1:]: self.i(d)#后面依次插入def search(self, n, p, d):'''search d in bstArgument:n:current nodep:parent noded:dataReturn:False/True: bool is d in bstn:current nodep:parent node'''if not n: return False, n, pif d == n.val: return True, n, pif d < n.val:return self.search(n.left, n, d)else:return self.search(n.right, n, d)def i(self, d):'''insert data d '''f, _, p = self.search(self.root, self.root, d)if not f:#d isn't in the Binary Treenew = rbtnode(d)if p.color == "BLACK":new.color = "RED"if d > p.val:p.right = newelse:p.left = new

打印输出

>>> a=[55,38,80,25,46,76,88,17,33,50,72]
>>> bst=rbt(a)
>>> bst.breadth_fisrt_level_traversal(bst.root)
(55, BLACK) (38, RED) (80, RED) (25, BLACK) (46, BLACK) (76, BLACK) (88, BLACK) (17, RED) (33, RED) (50, RED) (72, RED) 

红一层黑一层

if p.color == "BLACK":new.color = "RED"

默认都是黑的，插入时父亲黑的情况改成红色。

真实面目

就在我电脑内存里面。看打印的结果跟上面的图是一样的。

加一减一插入

跟前面一篇文章一样。再插入 [56,37,81,24,47,74,89,16,34,49,73]看看会是什么样子？

>>> for k in [56,37,81,24,47,74,89,16,34,49,73]:bst.i(k)>>> bst.breadth_fisrt_level_traversal(bst.root)
(55, BLACK) (38, RED) (80, RED) (25, BLACK) (46, BLACK) (76, BLACK) (88, BLACK) (17, RED) (33, RED) (50, RED) (72, RED) (81, RED) (89, RED) (16, BLACK) (24, BLACK) (37, BLACK) (47, BLACK) (56, BLACK) (74, BLACK) (34, RED) (49, RED) (73, RED) 

也许没有人跟我这样做。不过画出来的图是红一层黑一层的好看，而且它还满足排序二叉树的要求。

化作春泥更护花

红色应该有多少呢？

实验

进行一百次一千次的测试，每次构造一千、一万个随机数据的红黑树。

计数代码

在层序打印里改造。$rednode$是计数的全局变量，把打印改成红色就计数。

python">	rednode = 0def count_red(self, node):if node is None: returntemp = []temp.append(node)global rednodewhile temp:q=temp.pop(0)if q.color == "red":rednode += 1if q.left:temp.append(q.left)if q.right:temp.append(q.right)

测试代码

python">import random
def test():a = random.sample(range(100000),1000)rb = RBT()for v in a:rb.INSERT(v)rb.count_red(rb.root)

少于一半

测试次数都是一千次。结点总量是样本的采样数量，比如“a = random.sample(range(100000),10000)”的结点总量是一万。
两次测试间要重启Run Module,让rednode重新计数。

结点总量	红结点占比
十	0.5179
百	0.48702
千	0.486191
万	0.4865256

====================== RESTART: E:\python\redblacktree.py ======================
>>> for _ in range(1000):test()
>>> rednode
5179
>>> 5179/(10*1000)
0.5179
>>> 
====================== RESTART: E:\python\redblacktree.py ======================
>>> for _ in range(1000):test()
>>> rednode
48702
>>> 48702/(100*1000)
0.48702
>>>
====================== RESTART: E:\python\redblacktree.py ======================
>>> for _ in range(1000):test()
>>> rednode
486191
>>> 486191/(1000*1000)
0.486191
>>>  
====================== RESTART: E:\python\redblacktree.py ======================
>>> for _ in range(1000):test()
>>> rednode
4865256
>>> 4865256/(10000*1000)
0.4865256
>>> 

也许书上是对的。

黑一层红一层

也应该是黑一层红一层，黑的多一点放到前面，而且根是黑色的。真的吗？

打印看看

以下是十次测试，结点数为十的情况，后面的数字是递增的红结点数量。

(60472, black) (5310, black) (64291, black) (113, black) (25891, red) (64170, black) (71600, black) (18571, black) (26362, black) (19453, red) 2
(70107, black) (60114, red) (92505, red) (28054, black) (61038, black) (91161, black) (93008, black) (37145, red) (75132, red) (97106, red) 7
(56512, black) (11459, red) (65320, red) (10400, black) (47284, black) (57514, black) (87049, black) (51745, red) (78152, red) (88423, red) 12
(63366, black) (34922, red) (94080, black) (13361, black) (58847, black) (90974, red) (95665, red) (8136, red) (29963, red) (51217, red) 18
(37487, black) (23219, red) (57105, red) (17811, black) (31715, black) (53763, black) (77264, black) (27364, red) (55293, red) (80516, red) 23
(82827, black) (69761, red) (90332, black) (19696, black) (76237, black) (87388, red) (96580, red) (2551, red) (39740, red) (77477, red) 29
(46517, black) (10928, red) (81122, red) (2240, black) (28953, black) (55190, black) (81813, black) (28901, red) (37139, red) (86003, red) 34
(60956, black) (39834, red) (82912, black) (13236, black) (53337, black) (74831, red) (88367, red) (10667, red) (23218, red) (41492, red) 40
(63483, black) (34219, red) (75273, black) (29213, black) (56584, black) (86680, red) (14370, red) (32272, red) (49871, red) (60342, red) 46
(78954, black) (31103, red) (94441, black) (21947, black) (51170, black) (92850, red) (99061, red) (17355, red) (50960, red) (70104, red) 52

看看图片的例子是（6/11=0.54545454545454545454545454545455）普适性还差一点。

后话

删除操作后也是这样吗？