Splay Trees and B-TreesReadingsSelf adjusting TreesSplay TreesPowerPoint PresentationZig-Zig and Zig-ZagSlide 7Zig at depth 1 (root)Zig at depth 1Zig-Zag operationZig-Zig operationDecreasing depth - "autobalance"Splay Tree Insert and DeleteExample InsertWith Self-AdjustmentSlide 16Example DeletionAnalysis of Splay TreesBeyond Binary Search Trees: Multi-Way TreesSlide 20B-Tree DetailsProperties of B-TreesSlide 23Slide 24Searching in B-treesSlide 26Inserting into B-TreesSlide 28Slide 29Example of Insertions into a B+ tree with M=3, L=2Deleting From B-TreesRun Time Analysis of B-Tree OperationsSlide 33Summary of Search TreesSplay Trees and B-TreesCSE 373 Data StructuresLecture 912/26/03 Splay Trees and B-Trees - Lecture 92Readings•Reading ›Sections 4.5-4.712/26/03 Splay Trees and B-Trees - Lecture 93Self adjusting Trees•Ordinary binary search trees have no balance conditions›what you get from insertion order is it•Balanced trees like AVL trees enforce a balance condition when nodes change›tree is always balanced after an insert or delete•Self-adjusting trees get reorganized over time as nodes are accessed›Tree adjusts after insert, delete, or find12/26/03 Splay Trees and B-Trees - Lecture 94Splay Trees•Splay trees are tree structures that:›Are not perfectly balanced all the time›Data most recently accessed is near the root. (principle of locality; 80-20 “rule”)•The procedure:›After node X is accessed, perform “splaying” operations to bring X to the root of the tree.›Do this in a way that leaves the tree more balanced as a whole12/26/03 Splay Trees and B-Trees - Lecture 95• Let X be a non-root node with  2 ancestors.• P is its parent node.• G is its grandparent node.PGXGPXGPXGPXSplay Tree Terminology12/26/03 Splay Trees and B-Trees - Lecture 96Zig-Zig and Zig-Zag4G 51 Pzig-zagGP 5X 2zig-zigXParent and grandparentin same direction.Parent and grandparentin different directions.12/26/03 Splay Trees and B-Trees - Lecture 971. Helpful if nodes contain a parent pointer.2. When X is accessed, apply one of six rotation routines.• Single Rotations (X has a P (the root) but no G)ZigFromLeft, ZigFromRight• Double Rotations (X has both a P and a G)ZigZigFromLeft, ZigZigFromRightZigZagFromLeft, ZigZagFromRightSplay Tree Operationsparentrightleftelement12/26/03 Splay Trees and B-Trees - Lecture 98Zig at depth 1 (root)•“Zig” is just a single rotation, as in an AVL tree•Let R be the node that was accessed (e.g. using Find)•ZigFromLeft moves R to the top faster access next timeZigFromLeftroot12/26/03 Splay Trees and B-Trees - Lecture 99Zig at depth 1•Suppose Q is now accessed using Find•ZigFromRight moves Q back to the topZigFromRightroot12/26/03 Splay Trees and B-Trees - Lecture 910Zig-Zag operation•“Zig-Zag” consists of two rotations of the opposite direction (assume R is the node that was accessed)(ZigFromRight)(ZigFromLeft)ZigZagFromLeft12/26/03 Splay Trees and B-Trees - Lecture 911Zig-Zig operation•“Zig-Zig” consists of two single rotations of the same direction (R is the node that was accessed) (ZigFromLeft)(ZigFromLeft)ZigZigFromLeft12/26/03 Splay Trees and B-Trees - Lecture 912Decreasing depth - "autobalance"Find(T) Find(R)12/26/03 Splay Trees and B-Trees - Lecture 913Splay Tree Insert and Delete•Insert x›Insert x as normal then splay x to root.•Delete x›Splay x to root and remove it. (note: the node does not have to be a leaf or single child node like in BST delete.) Two trees remain, right subtree and left subtree.›Splay the max in the left subtree to the root›Attach the right subtree to the new root of the left subtree.12/26/03 Splay Trees and B-Trees - Lecture 914Example Insert•Inserting in order 1,2,3,…,8•Without self-adjustment12345678O(n2) time for n Insert12/26/03 Splay Trees and B-Trees - Lecture 915With Self-Adjustment121 21ZigFromRight21 3ZigFromRight21312312/26/03 Splay Trees and B-Trees - Lecture 916With Self-AdjustmentZigFromRight213442134Each Insert takes O(1) time therefore O(n) time for n Insert!!12/26/03 Splay Trees and B-Trees - Lecture 917Example Deletion101552013829610155201382 96splay1015520132 96remove1015520132 96Splay (zig)attach(Zig-Zag)12/26/03 Splay Trees and B-Trees - Lecture 918Analysis of Splay Trees•Splay trees tend to be balanced›M operations takes time O(M log N) for M > N operations on N items. (proof is difficult)›Amortized O(log n) time.•Splay trees have good “locality” properties›Recently accessed items are near the root of the tree.›Items near an accessed one are pulled toward the root.12/26/03 Splay Trees and B-Trees - Lecture 919•Example: B-tree of order 3 has 2 or 3 children per node•Search for 8Beyond Binary Search Trees: Multi-Way Trees13:-6:113 46 7 811 1213 1417 1817:-12/26/03 Splay Trees and B-Trees - Lecture 920B-Trees are multi-way search trees commonly used in database systems or other applications where data is stored externally on disks and keeping the tree shallow is important.A B-Tree of order M has the following properties: 1. The root is either a leaf or has between 2 and M children. 2. All nonleaf nodes (except the root) have between M/2 and M children. 3. All leaves are at the same depth. All data records are stored at the leaves.Internal nodes have “keys” guiding to the leaves.Leaves store between L/2 and L data records,where L can be equal to M (default) or can be different.B-Trees12/26/03 Splay Trees and B-Trees - Lecture 921B-Tree DetailsEach (non-leaf) internal node of a B-tree has:›Between M/2 and M children.›up to M-1 keys k1  k2  kM-1Keys are ordered so that:k1  k2  kM-1kM-1. . .. . . ki-1kik112/26/03 Splay Trees and B-Trees - Lecture 922Properties of B-TreesChildren of each internal node are "between" the items in that node.Suppose subtree Ti is the ith child of the node:all keys in Ti must be between keys ki-1 and kii.e. ki-1 Tikiki-1 is the smallest key in TiAll keys in first subtree T1k1All keys in last subtree TMkM-1k1TTii. . .. . . kki-1kkiiTTMTT11kkM-1. . . . . .12/26/03 Splay Trees and B-Trees - Lecture 923DS.B.13B-Tree Nonleaf NodeP[1] K[1] . . . K[i-1] P[i-1] K[i] . . . K[q-1] P[q]y zx < K[1]K[i-1]y<K[i] K[q-1]  z• The Ks are keys• The Ps are pointers to subtrees.x | 4 | | 8 | x<4 4x<8 8 x12/26/03 Splay Trees and B-Trees - Lecture