红黑树 一种重要的平衡二叉搜索树实现方法 陶先平
红黑树 一种重要的平衡二叉搜索树实现方法 陶先平
平衡二叉搜索树 我们有没有简单的方法得到一棵相对“平衡的”二叉搜索树？ 何谓“相对”平衡 简单到什么程度？
平衡二叉搜索树 我们有没有简单的方法得到一棵相对“平衡的”二叉搜索树？ 何谓“相对”平衡 简单到什么程度？
红黑树的基本性质 ·Binary Search Tree Each node of the tree now contains the attributes color,key,left, right,and p. 1.Every node is either red or black. 2.The root is black. red-black trees ensure that no such path is more than twice as 3.Every leaf (NIL)is black. long as any other,so that the tree is approximately balanced 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
红黑树的基本性质 • Binary Search Tree • Each node of the tree now contains the attributes color, key, left, right, and p. red-black trees ensure that no such path is more than twice as long as any other, so that the tree is approximately balanced
Example 7 130 0 60 m ⑦1D5如m10)如血m西 135130 13如m血 如 6 A6 四m T.nl 26 17 41 14 21 30 47 10 16 19 23 28 38 20 35 39 3 (c)
Example
black-height of a node We call the number of black nodes on any simple path from,but not including,a node x down to a leaf the black-height of the node, denoted bh(x) Black-height is well defined! 39 NIL NIL D NIL a
black-height of a node • We call the number of black nodes on any simple path from, but not including, a node x down to a leaf the black-height of the node, denoted bh(x) Black-height is well defined!