算法设计与分析logn search

1、Introduction toAlgorithm Design and Analysis8 logn searchYu HuangInstitute of Computer SoftwareNanjing UniversityIn the last class Selection warm upo Max and mino Second largest Selection Rank k (median)o Expected linear timeo Worst-case linear time Adversary argumento Lower boundLectures on Algorit

2、hm Design & Analysis (LADA) 20132014/10/92logn search Essential of the searching problemo How to organize the data to enable efficient searcho logn search Each search cut off half of the search space How to organize the data to enable logn search logn search techniqueso Binary search over sorted

3、 sequenceso Balanced Binary Search Tree (BST)Lectures on Algorithm Design & Analysis (LADA) 20142014/10/93Binary Search by Example Binary search for “24”o Divide the search spaceo Cut off half the space after each searchLectures on Algorithm Design & Analysis (LADA) 20142014/10/94The sequenc

4、e is aly sorted1st3rd2ndPseudo code inp.129 Baase0135620212430404550Balanced Binary Search Tree Binary search tree (BST)o Definitions and basic operations Definition of Red-Black Tree (RBT)o Black height RBT operationso Insertion into a red-black tree etion from a red-black treeLectures on Algorithm

5、 Design & Analysis (LADA) 20142014/10/96Binary Search Tree Revisited40Good balngQ(logn)Poor balng30Q(n)2060208030508060In a properly drawn40tree, pushing forwardto get the ordered list.50 Each node has a key, belonging to a linear ordered set An inorder traversal produces a sorted list of the ke

6、ysNode GroupNode groupAs in 2-tree, the number of external node is one more than that of internal node501570701025608060802040657590755 principal subtrees30Lectures on Algorithm Design & Analysis (LADA) 20142014/10/9750151025204030The node group to be rotatedRoot of the group is changed.Balng by

7、 Rotation50251540102030The middle principal subtree changes parentLectures on Algorithm Design & Analysis (LADA) 20142014/10/98Red-Black Tree: the Definition If T is a binary tree in which each node has a color, red or black, and all external nodes are black, then T is a red-black tree if and on

8、ly if:o Color constraint No red node has a red childo Black height constraint The black length of all external paths from a given node u is the same (the black height of u)Lectures on Algorithm Design & Analysis (LADA) 20142014/10/99o The root is black. Almost-red-black tree(ARB tree) Balng isun

9、der controlo Root is red, satisfying the other constraints.Recursive Definition of RBT(A red-black tree of black height h is denoted as RBh) Definition:o An external node is an RB0 tree, and the node is black.No ARB0o A binary tree is an ARBh (h³1) tree if: Its root is red, and Its left and rig

10、ht subtrees are each an RBh-1 tree.o A binary tree is an RBh (h³1) tree if: Its root is black, and Its left and right subtrees are each either an RBh-1 tree or anARBh tree.Lectures on Algorithm Design & Analysis (LADA) 20142014/10/916(3)(4)ARB1(1)(2)RB1RBi and ARBiRB0Red-Black Tree with 6 N

11、odes402060305080poorest balng:30height(normal) is 42060Black edge204060305080508040402030506080Black-depth ConventionAll with the same largest black depth: 2306020406040508020305080ARB TreesProperties of Red-Black Tree The black height of any RBh tree or ARBh tree is well-defind and is h. Let T be a

12、n RBh tree, then:o T has at least 2h-1 internal black nodes.o T has at most 4h-1 internal nodes.o The depth of any black node is at most twice its black depth. Let A be an ARBh tree, then:o A has at least 2h-2 internal black nodes.o A has at most (4h)/2-1 internal nodes.o The depth of any black node

13、 is at most twice its black depth.Well-Defined Black Height That “the black height of any RBh tree or ARBh tree is welldefind” means the black length of all external paths fromthe root is the same. Proof: induction on h Base case: h=0, that is RB0 (there is no ARB0) In ARBh+1, its two subtrees are b

14、oth RBh. Since the root is red, the black length of all external paths from the root is h, thats the same as its two subtrees. In RBh+1:o Case 1: two subtrees are RBhso Case 2: two subtrees are ARBh+1so Case 3: one subtree is an RBh(black height=h), and the another is an ARBh+1(black height=h+1)Boun

15、d on Depth of Node in RBTree Let T be a red-black tree with n internal nodes. Then no node has depth greater than 2log(n+1), which means that the height of T in the usual sense is at most 2log(n+1).o Proof:o Let h be the black height of T. The number of internal nodes, n, is at least the number of i

16、nternal black nodes, which is at least 2h-1, so h£log(n+1). The node with greatest depth is some external node. All external nodes are with black depth h. So, the depth is at most 2h.Influences of Insertionto an RBT Black height constraint:o No violation if inserting a red node.Color constraint

17、:40203050608040Inserting 70203050607080Critical clusters(external nodes excluded), which originated by color violation, with 3 or 4 red nodesLectures on Algorithm Design & Analysis (LADA) 20142014/10/917Repairing 4-node Critical ClusterLectures on Algorithm Design & Analysis (LADA) 20142014/

18、10/91940203050No new critical cluster occurs, inserting finished.607080Color flip:Root of the critical cluster exchanges color with its subtrees40602030507080Repairing 4-node Critical Cluster40406080203050708590New critical cluster with 3 nodes.Color flip doesnt work, Why?20305060Critical cluster2 m

19、ore insertions70808590Patterns of 3-node Critical ClusterLectures on Algorithm Design & Analysis (LADA) 20142014/10/920A LMRB LMRLLLRRLRRLLLRRLRRCLMRLLLRRLRRDLMRLLLRRLRRShown as properly drawnRepairing 3-Node Critical ClusterLectures on Algorithm Design & Analysis (LADA) 20142014/10/922Root

20、of the critical cluster is changed to M, and the parentship is adjusted accordinglyLMRAll into one patternLLLRRLRRThe incurred critical cluster is of pattern A402030506080708590class RBtreeElement root; RBtree leftSubtree; RBtree rightSubtree;int color; /* red, black */static class InsReturnpublic R

21、Btree newTree;Color patternpublic int status /* ok, rbr, brb, rrb, brr */Implementing Insertion: ClassImplementing Insertion:ProcedureRBtree rbtInsert (RBtree oldRBtree, Element newNode)Lectures on Algorithm Design & Analysis (LADA) 20142014/10/924s = rbtIns(oldREtree, newNode);ee.color black) e

22、.color = black;ewTree;InsReturn an If (ans.newTr ans.newTrereturn ans.nthe wrapperInsReturn rbtIns(RBtree oldRBtree, Element newNode) InsReturn ans, ansLeft, ansRight;if (oldRBtree = nil) then <Inserting simply>elseif (newNode.key <oldRBtree.root.key)ansLeft = rbtIns (oldRBtree.leftSubtree,

23、 newNode); ans = repairLeft(oldRBtree, ansLeft);elseansRight = rbtIns(oldRBtree.rightSubtree, newNode); ans = repairRight(oldRBtree, ansRight);return ansthe recursive functionCorrectness of Insertion If the parameter oldRBtree of rbtIns is an RBh tree or an ARBh+1 tree(which is true for the recursiv

24、e calls on rbtIns), then the newTree and status fields returned are one of the following combinations:o Status=ok, and newTree is an RBh or an ARBh+1 tree,o Status=rbr, and newTree is an RBh,o Status=brb, and newTree is an ARBh+1 tree,o Status=rrb, and newTree.color=red, newTree.leftSubtree is anARB

25、h+1 tree and newTree.rightSubtree is an RBh tree,o Status=brr, and newTree.color=red, newTree.rightSubtree is anARBh+1 tree and newTree.leftSubtree is an RBh tree For those cases with red root, the color will be changed to black, with other constraints satisfied by repairing subroutines.Deletion: Lo

26、gicalu: to be deleted logicallyp is parent of sand StructuralLectures on Algorithm Design & Analysis (LADA) 20142014/10/92540203050p6080708590right subtree of S, to replace Ss: tree successor of u, to beSdeleted structurally, with information moved into up4070203050808590After deletionDeletion f

27、rom RBT - ExamplesOriginal tree402030506080708590u,p406085203050708090406080u,p502030507085u,p906080203040708590Lectures on Algorithm Design & Analysis (LADA) 20142014/10/926Deletion in RBT406080203050708590To be deletedone deletionThe black height of pis not well-defined !p407080Lectures on Alg

28、orithm Design & Analysis (LADA) 20142014/10/927203050black depth=18590black depth=2Procedure of Red-Black Deletion1. Do a standard BST search to locate the node to be logically deleted, call it u2. If the right child of u is an external node, identify u as the node to be structurally deleted.3.

29、If the right child of u is an internal node, find the tree successor of u , call it s, copy the key and information from s to u. (color of u not changed) Identify s as the node to be deleted structurally.4. Carry out the structural deletion and repair any imbalance of black height.Lectures on Algori

30、thm Design & Analysis (LADA) 20142014/10/928Imbalance of Black HeightLectures on Algorithm Design & Analysis (LADA) 20142014/10/932deleting 8085deleting 40507090203080deleting 857080deleting 60908590Black height has to be restored402030506080708590Analysis of Black Imbalance The imbalance oc

31、curs when:o A black node is deleted structurally, ando Its right subtree is black (external) The result is:o An RBh-1 occupies the position of an RBh as required by its parent, coloring it as a “gray” node. Solution:o Find a red node and turn it black as locally as possible.o The gray color might propagate up the tree.Propagation of Gray NodeThe pattern forpgslrpwhich propagation is neededgsMap of the viciofg, the gray nodeGr