算法设计与分析-10红黑树

《算法设计与分析-10红黑树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法设计与分析谭守标安徽大学电子学院2007.9第九章红黑树红黑树的概念和性质红黑树的旋转操作（过程及分析）红黑树的插入操作（过程及分析）红黑树的删除操作（过程及分析）程序演示及说明二叉查找树的概念和性质二叉查找树：（1）一个结点x的域：key，left，right和p。（2）二叉查找树的性质：设x为二叉查找树中的一个结点。如果y是x的左子树中的一个结点，则key[y]≤key[x]；如果y是x的右子树中的一个结点，则key[y]≥key[x]。中序遍历算法因为某子树根的关键字在被印出时是介于其左子树中的关键字和其右子树中的

2、关键字之间，所以称为中序遍历算法.INORDER-TREE-WALK(x)1ifx≠NIL2thenINORDER-TREE-WALK(left[x])3printkey[x]4INORDER-TREE-WALK(right[x])中序遍历算法见如下的二叉查找树:将根节点指针设为上面程序的参数,则最终的输出结果为有序排列的一组数:235578二叉查找树的查找算法查找关键字为k的节点：根据二叉查找树的性质，从根节点开始查找，对碰到的每个节点x，比较k和key[x]，若k=key[x]，返回x；若k

3、子树；否则继续查找x的右子树.TREE-SEARCH(x,k)1ifx=NILork=key[x]2thenreturnx3ifk

4、找树的查找算法给定一个二叉查找树中的节点,有时候要求出在中序遍历下的前趋或后继。节点的前趋：如果所有的关键字均不同，某节点x的前趋即具有小于key[x]中的关键字中最大者的那个节点。节点的后继：某节点x的后继即具有大于key[x]中的关键字中最小者的那个节点。根据二叉树的结构我们可一不用做比较就可以找到某节点的前趋或后继。下面的过程对二叉查找树中的某节点x返回其后继(如果存在的话)，或NIL(如果x有树中最大的关键字的话)。节点的后继TREE-SUCCESSOR(x)1ifright[x]≠NIL2thenreturnTRE

5、E-MINIMUM(right[x])3yp[x]4whiley≠NILandx=right[y]5doxy6yp[y]7returny节点的后继TREE-SUCCESSOR的代码中包含两种情况.如果节点x的右子树非空,则x的后继即是右子树中的最左点,在第2行中通过调用TREE-MINIMUM(right[x])可以找到这个节点.另一方面,如果节点x的右子树为空且x有后继y.则y是x的最低的一个祖先节点,且y的左儿子也是x的祖先.节点的前趋(TREE-PREDECESSOR)：与上述方式对称二叉查找树的查找算法时间性能分析：

6、时间性能?如何改进？二叉查找树的插入和删除操作除完成简单的插入或删除操作外，还需要什么操作？后面结合红黑树操作一起介绍。一、红黑树的概念和性质红黑树：一种“平衡的”二叉查找树。一个结点的域增加一位存储结点的color，具体可以是RED或BLACK。(1)红黑树的性质：①每个结点或是红的，或是黑的；②每个叶结点（NIL）是黑的；③如果一个结点是红的，则它的两个子女都是黑的；④从某一结点到达其子孙叶结点的每一条简单路径上包含相同个数的黑结点。(2)黑高度：用bh(x)表示。从某一结点x出发（不包括该结点）到达一个叶结点的任意一条

7、路径上的黑结点的个数称为该结点的黑高度。红黑树的黑高度定义为其根结点的黑高度。(3)一个引理：一个含有n个内结点的红黑树的高度至多为2log2（n+1）。证明：先证明以结点x为根的子树中至少包含2bh（x）-1个内结点。用假设归纳法证明。①当x的高度为0时，则x必为一个叶结点（NIL），bh(x)=0，内结点个数为2bh(x)-1=20-1=0，假设成立；②当x的高度为正值时，x是一个内结点且有两个子女(?)。每个子女根据自身颜色是红或黑有黑高度bh(x)或bh(x)-1。根据假设，每个子女至少含内结点数为2bh(x)-1-

8、1。则以x为根结点的子树至少含内结点为（2bh（x）-1-1）+（2bh（x）-1-1）+1=2bh（x）-1。假设成立，得证。再根据性质③可知，高度为h的红黑树的黑高度至少为h/2，故有n≥2h/2-1，得h≤2log2（n+1）。引理证毕。二、红黑树的旋转操作对红黑树进行插入和删除操作