AVL TreeAVL Tree ExamplesSlide 3AVL tree insertion examplesAVL tree deletion examplesB-TreeSlide 7Slide 8Slide 9B-tree of degree tSlide 112-3-4 TreeTreapSplay tree (See the end of amortized analysis)Splay tree (cont.)Slide 16Slide 17AVL Tree•Definition: –binary search tree–For any node, the heights of left subtree and right subtree differ at most 1.–(if differ at most k, called BH(k) tree).•Theorem (Adel'son-Vel'skii and Landis 1962): –The height of an AVL tree with N internal nodes always lies between log (N +1 ) and 1..4404 log(N + 2) - 0.328AVL Tree ExamplesWorst case AVL treesFigures in these slides are copied from: http://www.eli.sdsu.edu/courses/fall96/cs660/notes/avl/avl.html#RTFToC2AVL Tree•Insertion:–As normal binary search tree insertion–Reconstruct tree by rotation if some nodes become unbalanced•Deletion:–as normal binary search tree deletion–The node deleted will be either a leaf or have just one subtree (this is true for all binary search tree deletion)–if the deleted node has one subtree, then that subtree contains only one node–Traverse up the tree from the deleted node checking the balance of each node, balance the node by rotation if unbalanced•Theorem: –An insertion into an AVL tree requires at most one rotation to rebalance a tree. A deletion may require log(N) rotations to rebalance the tree.AVL tree insertion examplesPerform single rotationInsert into subtree 3Insert into subtree 2 or 3Perform double rotationAVL tree deletion examplesDeletion from subtree 1Perform single rotationDeletion from subtree 1Perform double rotationB-Tree•Similar to Red-Black tree or others, balanced search tree•Different from other balanced search tree, nodes may have many children. So mainly used for Disk I/O.•A node x with n[x] keys –has n[x]+1 children, –the keys in x are stored in non-decreasing order, –the keys in children are delimited by the keys–all paths from the root to a leaf are of equal length, i.e. height-balancedAn example of B TreeCopyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.B-tree of degree t•Definition:–Root must have 1 key–Internal node has at least t-1 keys but at most 2t-1 keys, i.e. has at least t but at most 2t children.•Theorem: h≤logt(n+1)/2•Insertion and deletions:–More complicate but still log (n )–Split and merge operation.Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.2-3-4 Tree•A B-tree of degree t=2.–So every node has 2,3,4 children.•Recursive definition–Satisfying search tree property–nil is a 2-3-4 tree, –a leaf is a 2-3-4 tree, –an internal node has either 2, 3 or 4 children, –all paths from the root to a leaf are of equal length i.e. a 2-3-4-tree is height-balanced •Height log(n) in balance search tree of n nodes–Binary tree or non-binary, such as B-tree–Whether all n nodes are placed as leaves or also as internal nodes.•B+-Tree: –real application data nodes are leaves, internal nodes are keys through which the search can be traced to real data.Treap •Consider as Tree + Heap-organize the tree as binary search tree by keys–Assign random chosen priorities to nodes, adjust the tree to obey min-heap order property–i.e. Assume that all keys are distinct, so do priorities, for any node u,•if v is a left child of u, key[v]<key[u]•if v is a right child of u, key[v]>key[u]•If v is a child of u, priority[v]>priority[u]•As a result, the expected height is log(n), so are insertion and deletion.Splay tree (See the end of amortized analysis)•A binary search tree (not balanced)•Height may be larger than log n, even n-1.•However a sequence of n operations takes O(nlog n).•Assumptions: data values are distinct and form a totally order set•Operations:–Member(i,S)–Insert(i,S)–Delete(i,S)–Merge(S,S’)–Split(i,S)–All based on •splay(i,S), reorganize tree so that i to be root if iS, otherwise, the new root is either max{k S |k<i} or min{k S |k>i}Splay tree (cont.)•For examples, –merge(S,S’)•Call Splay(, S) and then make S’ the right child–Delete(i,S), call Splay(i,S), remove I, then merge(left(i), right(i)).–Similar for others.–Constant number of splays called.Splay tree (cont.)•Splay operation is based on basic rotate(x) operation (either left or right).•Three cases:–y is the parent of x and x has no grandparent•rotate(x)–x is the left (or right) child of y and y is the left (or right) child of z, •rotate(y) and then rotate(x)\–x is the left (or right) child of y and y is the right (or left) child of z, •rotate(x) and then rotate(x)Splay tree (cont.)•Credit invariant: Node x always has at least log (x) credits on deposit.–Where (S)=log (|S|) and (x)=(S(x))•Lemma:–Each operation splay(x,S) requires no more than 3((S)-(x))+1 credits to perform the operation and maintain the credit invariant.•Theorem:–A sequence of m operations involving n inserts takes time