Please enable JavaScript.

Coggle requires JavaScript to display documents.

MM8 - Coggle Diagram

- - - - structures that preserves the good proprieties of the binary search tree but avoids the worst-case efficiency
      - instance-simplification
        
        self-balancing: turns unbalanced trees into balanced ones
        
        AVL Trees
        
        Red-Black Trees
        
        Splay Trees
        
        rotations: function that restores the balance
      - representation-chance
        
        allows more than one element per node
        
        different cases differ only on the number of nodes allowed in a single one
        
        2-3 Trees
        
        2-3-4 Trees
        
        B-trees
      - AVL trees
        
        balance factor: difference between the heights of the left and right subtrees of a node is either 0, +1 or -1
        The height of an empty tree is defined as -1
        
        rotation: transformation on a subtree rooted at a node with balance +2 or -2 after an insertion
        If there are more than one node than one node like that, the transformation is made on the one closest to the inserted leaf
        
        types of rotation
        
        R-rotation (Right)
        
        L-rotation (Left)
        
        LR-rotation (L + R rotations)
        
        RL-rotation (R + L rotations)
        
        efficiency
        
        like the binary search tree, it depends on the height
        
        h = height
        n = number of nodes
        
        log(n) <= h < 1.4405.log(n+2) - 1.3277
        
        worst case of searching and insertion: theta(log(n))
        
        deletion is more difficult than searching and inserting but its efficiency is also logarithmic
        
        drawback: frequent rotations and the need to maintain balance
      - 2-3 trees
        
        2-node
        
        one key K
        
        two children
        
        left < K
        
        right > K
        
        3-node
        
        two keys K1 and K2 (K1 < K2)
        
        three children
        
        left < K1
        
        K1 < middle < K2
        
        right > K2
        
        all the leaves have the same level / height
        
        searching
        
        given a key K to find
        
        if it's 2-node: search as a binary tree
        
        if it's a 3-node:
        compare to the root's keys
        decide in which subtree to continue searching
        
        inserting
        
        the insertion will happen in a leaf
        
        search for K
        
        if the leaf is a 2-node:
        insert as the second key in the appropriate position
        
        if the leaf is a 3-node:
        split the leaf in two (the smallest element on the left, the larger on the right)
        the middle element is "promoted" to the parent
        
        efficiency
        
        h = height
        n = number of nodes
        
        a tree with the smallest number of keys is all 2-noded:
        n >= 1 + 2 + 3 + ... + 2^h = 2^(h+1) -1
        h <= log_2(n+1) - 1
        
        a tree with the largest number of keys is all 3-noded:
        n <= 2.1 + 2.3 + 2.9 + ... + 2.3^h = 2(1 + 3 + 9 + ... + 3^h) = 3^(h+1) - 1
        h >= log_3(n+1) - 1
        
        log_3(n+1) - 1 <= h <= log_2(n+1) - 1
        
        searching, inserting and deleting of the worst and avarage case:
        theta(log(n))