《算法导论第十章rb树ppt课件》由会员分享，可在线阅读，更多相关《算法导论第十章rb树ppt课件（49页珍藏版）》请在金锄头文库上搜索。
1、.Red-BlackTrees红黑树)一孛裙探稳寇/会“王5安Binarysearchtree二叉查找树“*NotionsoftheRBTree红黑树的概念*0perationsoftheRBTree红黑树的操作inayseaChtree二叉查找树/二叉排序树。它可以是一棵空树或者具有如下特性的非空树:。若左子树不为空,则左子树上所有结点的值或关键字均小于等于根结点的值或关键守s若右子树不为空,动右子树上所有结点的值或关键字均大于等于根结点的值或关键守。左、右子树本身又各是一棵二排序叉树霾Binarysearchtree二叉查找树/二叉排序树。中序逼历有序。中序遍历INORDER-TREE-W
2、ALK(加)1ifX士NIL2“thenINORDER-TREE-WAILKL/切)3printkey切4INORDER-TREE-WALK(gptX)霾Binarysearchtree二叉查找树/二叉排序树。如果x是一椋包含7个节点的子树的根,中序遍历算法来输出二叉查找树中所有元素的时间复杂度为介小。二叉查找树的中序遍历结果不能推断出二叉查找树的结笋霾Binarysearchtree二叉查找树/二叉排序树。Ssearch杏找算法(输入待查找的关键字X(2)若树不为空,则若给定值等于根结点,查找成功,返回根结点的指针(3)若给定值小于根结点,则在根结点左子树继续查找(4若给定值k大于根结点,则
3、在根结点右子树继续查找(5)重复以上(2)(3)(4)操作,直到找到或为空结束查找关键字13D75-丿6-丿7-二73患Binarysearchtree二叉查找树/二叉排序树TREE-SEARCH(x1if心NILorK=kel刀2thenreturnX3ifKkeyN4“thenreturnTREE-SEARCH(/eft,月5elsereturnTREE-SEARCH(gtLx,月霾Binarysearchtree二叉查找树/二叉排序树ITERATIVE-TREE-SEARCH(X石1whilexNILandK#Ke/切2“doifKkel州3thenx一/ef刀4elsex一0gpf川5returnX霾Binarysearchtree二叉查找树/二叉排序树。Minimum最小值TREE-MINIMUM(91while/ef切王NIL2“dox一/efi川3returnX患Binarysearchtree二叉查找树/二叉排序树。Successorandpredecessor前驱和后继TREE-SUCCESSOR(91ifpgpt切王NIL2thenreturnTREE-MINIMUM(xgpt)3一pXI4while/子NILandX=/gpf月5doX一人6土一月7return仁
