落红不是无情物
接前面
红黑树的插入——层层历历在目想分析一下红黑树是不是红一层黑一层的。直觉告诉我红的少很多。
红黑树转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: return
temp = []
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)
从上面的层序输出看，它不是最佳二叉排序树。
定制代码
class rbtnode:
'''红黑树的结点类型'''
def __init__(self, val):
self.val = val
self.left = None
self.right = None
#self.parent = None
self.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 bst
Argument:
n:current node
p:parent node
d:data
Return:
False/True: bool is d in bst
n:current node
p:parent node
'''
if not n: return False, n, p
if d == n.val: return True, n, p
if 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 Tree
new = rbtnode(d)
if p.color == "BLACK":
new.color = "RED"
if d > p.val:
p.right = new
else:
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)
也许没有人跟我这样做。不过画出来的图是红一层黑一层的好看，而且它还满足排序二叉树的要求。
化作春泥更护花
红色应该有多少呢？
实验
进行一百次一千次的测试，每次构造一千、一万个随机数据的红黑树。
计数代码
在层序打印里改造。 r e d n o d e rednode rednode是计数的全局变量，把打印改成红色就计数。
rednode = 0
def count_red(self, node):
if node is None: return
temp = []
temp.append(node)
global rednode
while temp:
q=temp.pop(0)
if q.color == "red":
rednode += 1
if q.left:temp.append(q.left)
if q.right:temp.append(q.right)
测试代码
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）普适性还差一点。
后话
删除操作后也是这样吗？
标签：红黑层,temp,self,厘清,black,red,BLACK,RED From： https://blog.csdn.net/denghai_csdn/article/details/143586078