计算机问题求解一论题2-15 -红黑树 2020年09月08日
计算机问题求解 – 论题2-15 - 红黑树 2020年09月08日
Red-Black Property 我们为什么需要红黑树这么一种特别的数据结构？ 1.Every node is either red or black. 2.The root is black. 3.Every leaf (NIL)is black. 4.If a node is red,then both its children are black. 5.For each node,all simple paths from the node to descendant leaves contain the same number of black nodes
Red-Black Property 我们为什么需要红黑树这么一种特别的数据结构？
6个结点的红黑树 20 60 poorest balancing 30 60 Black edge
6个结点的红黑树 40 60 80 30 50 20 40 30 80 60 50 20 30 20 80 60 40 50 poorest balancing Black edge
范例 3 26 41 14 2 21 30 47 10 16 19 23 28 38 NIL NIL NIL NIL 20 NIL NIL NIL NIL 39 NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL N NIL (a) 什么是黑高？黑高的定义是well define的吗？
范例
Black-Depth Convention All with the same largest black depth:2 40 0 60 80 30 60 40 60
Black-Depth Convention 40 30 50 80 20 20 40 50 30 60 40 20 30 50 60 80 60 80 All with the same largest black depth: 2