算法导论 第十章 RB树.pptVIP

Red-Black Trees（红黑树） 主要内容 Binary search tree二叉查找树/二叉排序树 它可以是一棵空树或者具有如下特性的非空树： 若左子树不为空，则左子树上所有结点的值或关键字均小于等于根结点的值或关键字 若右子树不为空，则右子树上所有结点的值或关键字均大于等于根结点的值或关键字 左、右子树本身又各是一棵二排序叉树 Binary search tree二叉查找树/二叉排序树 中序遍历有序 中序遍历 INORDER-TREE-WALK(x) 1 if x ≠ NIL 2 then INORDER-TREE-WALK(left[x]) 3 print key[x] 4 INORDER-TREE-WALK(right[x]) Binary search tree二叉查找树/二叉排序树 如果x是一棵包含n个节点的子树的根，中序遍历算法来输出二叉查找树中所有元素的时间复杂度为θ(n) 二叉查找树的中序遍历结果不能推断出二叉查找树的结构 Binary search tree二叉查找树/二叉排序树 search查找算法 Binary search tree二叉查找树/二叉排序树 TREE-SEARCH (x, k) 1 if x= NIL or k = key[x] 2 then return x 3 if k key[x] 4 then return TREE-SEARCH(left[x], k) 5 else return TREE-SEARCH(right[x], k) Binary search tree二叉查找树/二叉排序树 ITERATIVE-TREE-SEARCH(x, k) 1 while x ≠ NIL and k ≠ key[x] 2 do if k key[x] 3 then x ← left[x] 4 else x ← right[x] 5 return x Binary search tree二叉查找树/二叉排序树 Minimum最小值 Binary search tree二叉查找树/二叉排序树 Successor and predecessor前驱和后继 Binary search tree二叉查找树/二叉排序树 Introduction of the RB tree 红黑树是一种自平衡二叉查找树，典型的用途是实现关联数组。它是在1972年由鲁道夫·贝尔发明的，他称之为“对称二叉B树”，它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。 复杂，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除，这里的n是树中元素的数目 Definition of RB tree A red-black tree is a binary search tree if it satisfies the following red-black properties Every node is either red or black The root is black Every leaf (NIL) is black If a node is red, then both its children are black For each node, all paths from the node to descendant leaves contain the same number of black nodes Introduction of the RB tree The structure of the node Example of a RB tree Every node is either red or black Example of a RB tree The root is black Example of a RB tree Every leaf (NIL) is black Example of a RB tree If a node is red, then both its children are black Example of a RB tree All simple paths from any node x to a descendant leaf have the same number of black nodes= bh(x)