Unit 3

Splay Tree

• Self adjusting binary search tree
• Intuition: Recently-accessed elements will be up near the root of the tree, lowering access time.
• Unused elements stay low in the tree.
• to type of rotations
  1. Zig -> Right rotate (rotate left element to parent)
  2. Zag -> Left rotate( rotate right element to parent)
• Splaying types
  • Bottom up
  • Top Down
• Bottom up splaying
  • start by passing the tree (T) and the node which is going to be splayed (n).

        while(n.parent != NULL){
            if(n.parent == T.root)
                if(n == n.parent.left)
                    RIGHT_ROTATE(T,n.parent)
                else
                    LEFT_ROTATE(T,n.parent)
            else
                two rotations
        }
    

• If the search is unsuccessful, i.e., we reach the null node, we splay at the last non-null node reached during the search and return a pointer to null.
• 
  Insertion
  
  • Normal BST Insertion, but once you insert splay the inserted node to the top
• 
  Deletion
  
  • Top Down
    • Search for Node to be deleted, if found splay the node to be deleted to the top and then delete it
    • Now you will have two trees left with you
    • on the left tree, find the largest element and splay it to the top
    • Attach the right subtree to the left of the left tree's newly splayed root
  • Bottom up
    • Delete the node by making it the leaf by either replacing with inorder predecessor or successor
    • Splay parent of the deleted node to the root
      Amortized Cost
      
• 3 (r(t)- r(x)) +1 = 0(log( s(t)/ s(x) ).
• // TODO

Potential Function
\(\(\sum_{1}^{n}log(n) = O(nlogn)\)\)
Advantages
- Splay tree is the fastest type of binary search tree, which is used in a variety of practical applications such as GCC compilers. - Improve searching by moving frequently accessed nodes closer to the root node

2-3-4 Tree

• Perfectly balanced, all the leaves are at the same level
• better utilize the behaviour of devices that read and write large chunks of data
• Insertion
  • Never insert on the internal levels even if they have room to accommodate
  • if number of elements in a node are already full, i.e. and we have to insert, take the median element (Middle one) and promote it to parent and make the left ones its left child and right ones its right child

B+ tree of degree m PROPERTIES 1. A node can have a maximum of m children. (i.e. 3) 2. A node can contain a maximum of m - 1 keys. (i.e. 2) 3. A node should have a minimum of ⌈m/2⌉ children. (i.e. 2) 4. A node (except root node) should contain a minimum of ⌈m/2⌉ - 1 keys. (i.e. 1)

Delete Operation - Leaf - At least 2 keys, delete it - Internal Node - Left child has 2 keys - replace with predecessor - Right child has two children - Replace with successor and delete it - Both children have 1 key - Merge - Not an internal Node - Child has 1 key and sibling has 2 keys, move/rotate sibling element into the parent and parent element into the element you are deleting - If both child nodes are siblings with 1 key each, merge the two children and the parent element.

Trie

• can quickly look up prefixes of keys, enumerate all entries with a given prefix, etc.

Compressed Trie - Collapse and merge the nodes for all the elements with 1 child - All nodes should have compulsorily 2 children or more

Leftist Heap - null path length, child links, value - skewed towards the left - The benefit is the efficient merge operations with O(log n) time for merging - npl of left child should always be greater than npl of right - if npl of right subtree > left subtree npl, swap the two subtrees

Skew Heap - Skew heap is extremely similar with leftist heap in terms of merge operation. - The swap here is unconditional, we always swap - choose min and make it root, swap the children - for it's left node now, continue by comparing the other skew heap and current node's left child

Binomial Tree - Union -> combine two binomial heaps 1,1,2,3,5d