Balanced Binary Search Tree

|
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
 7 views
of 38

Please download to get full document.

View again

Description
Balanced Binary Search Tree. 황승원 Fall 2010 CSE, POSTECH. height is O(log n) , where n is the number of elements in the tree AVL (Adelson-Velsky and Landis) trees red-black trees get, put, and remove take O(log n) time. Balanced Binary Search Trees. Indexed AVL trees
Share
Transcript
Balanced Binary Search Tree 황승원Fall 2010CSE, POSTECHheight is O(log n), where n is the number of elements in the treeAVL (Adelson-Velsky and Landis) treesred-black treesget, put, and remove take O(log n) timeBalanced Binary Search Trees Indexed AVL treesIndexed red-black treesIndexed operations alsotakeO(log n) timeBalanced Binary Search Trees weight balanced binary search trees2-3 & 2-3-4 treesAA treesB-treesBBST etc.Balanced Search Trees AVL TreeDefinition
  • Binary tree.
  • If T is a nonempty binary tree with TL and TR as its left and right subtrees, then T is an AVL tree iff
  • TL and TR are AVL trees, and
  • |hL – hR|  1 where hL and hR are the heights of TL and TR, respectively
  • This is an AVL tree.Balance Factors-111-10100-10000The height of an AVL tree that has n nodes is at most 1.44 log2 (n+2).Nh=Nh-1 + Nh-2+1 – reminds you anything?Fn=Fn-1 + Fn-2Nh=Fh+2-1 whenHeight-11011740-10104538300-100060351205025AVL Search Treeput(9)-110011740-101-104538300-10000603519205025put(29)-11011740-10104538300-1000-2603512050-1RR imbalance => new node is in right subtree of right subtree of blue node (node with bf = -2)25029put(29)-11011740-10104538300000060351255002029RR rotation.RRLLRLLRAVL RotationsImbalance Types
  • After an insertion, when the balance factor of node A is –2 or 2, the node A is one of the following four imbalance types
  • LL: new node is in the left subtree of the left subtree of A
  • LR: new node is in the right subtree of the left subtree of A
  • RR: new node is in the right subtree of the right subtree of A
  • RL: new node is in the left subtree of the right subtree of A
  • RotationDefinition
  • To switch children and parents among two or three adjacent nodes to restore balance of a tree.
  • A rotation may change the depth of some nodes, but does not change their relative ordering.
  • AVL Rotations
  • To balance an unbalanced AVL tree (after an insertion), we may need to perform one of the following rotations: LL, RR, LR, RL
  • An LL RotationAn LR RotationRR and RL?
  • Symmetric!
  • -11011740001-1383045000-101520356002529Inserting into an AVL Search TreeInsert(29)
  • Where is 29 going to be inserted into?
  • After the insertion, is the tree still an AVL search tree? (i.e., still balanced?)
  • -11011740001-1383045000015203560-2-125029Inserting into an AVL Search TreeInsert(29)
  • What are the balance factors for 20, 25, 29?
  • RR imbalance  new node is in the right subtree of right subtree of node 20 (node with bf = -2)
  • -11011740001-13830450000015253560002029After RR Rotation
  • What would the left subtree of 30 look like after an RR rotation?
  • After the RR rotation, is the resulting tree an AVL search tree now?
  • Deletion from an AVL Search Tree
  • Deletion of a node may also produce an imbalance
  • Imbalance incurred by deletion is classified intothe types R0, R1, R-1, L0, L1, and L-1
  • Rotation is also needed for rebalancing
  • Read the observations after deleting a node from an AVL search tree
  • Read Section 11.2.6 for Deletion from an AVL search tree
  • An R0 RotationAn R1 RotationAn R-1 RotationComplexity of Dictionary Operations:Search, Insert, and DeleteData StructureWorst CaseExpectedHash TableO(n)O(1)Binary SearchTreeO(n)O(logn)BalancedBinary SearchTreeO(logn)O(logn)
  • n is the number of elements in dictionary.
  • Complexity of Other OperationsAscend, Search(rank), and Delete(rank)Data Structureascendget and removeHash TableO(D+nlogn)O(D+nlogn)O(n)Indexed BSTO(n)IndexedBalanced BSTO(n)O(log n)
  • D is the number of buckets.
  • Colored Nodes DefinitionBinary search tree.Each node is colored red or black.Root and all external nodes are black.No root-to-external-node path has two consecutive red nodes.All root-to-external-node paths have the same number of black nodesRed Black Trees107404538306035120525Example Red Black TreeProperties
  • The height of a red black tree that has n (internal) nodes is between log2(n+1) and 2log2(n+1).
  • Lemma 16.2
  • r : rank of root
  • Insert
  • New pair is placed in a new node, which is inserted into the red-black tree.
  • New node color options.
  • Black node => one root-to-external-node path has an extra black node (black pointer).
  • Hard to remedy.
  • Red node => one root-to-external-node path may have two consecutive red nodes (pointers).
  • May be remedied by color flips and/or a rotation.
  • gpppdpcabClassification Of 2 Red Nodes/Pointers
  • XYz
  • X => relationship between gp and pp.
  • pp left child of gp => X = L.
  • Y => relationship between pp and p.
  • p right child of pp => Y = R.
  • z = b (black) if d = null or a black node.
  • z = r (red) if d is a red node.
  • LLbXYr
  • Color flip.
  • gpgpppppddppccabab
  • Continue rebalancing if changing gp to red causes problems
  • LLb
  • Rotate.
  • gpyzppxzydpxabcdcab
  • Done!
  • Same as LL rotation of AVL tree.
  • LRb
  • Rotate.
  • gpyzppxzxdabcdapybc
  • Done!
  • Same as LR rotation of AVL tree.
  • RRb and RLb are symmetric.
  • Red-black Tree Animation
  • http://www.ece.uc.edu/~franco/C321/html/RedBlack/redblack.html
  • java.util.TreeMap => red black tree
  • Coming Up Next
  • READING: Ch 16.1~2
  • NEXT: Graphs (Ch 17.1~7)
  • Related Search
    We Need Your Support
    Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

    Thanks to everyone for your continued support.

    No, Thanks