Please enable JavaScript.

Coggle requires JavaScript to display documents.

Balanced Search Trees - Coggle Diagram

- - - - all are perfectly balanced
- - - - Insertion and Search
        
        Searching in an AVL tree requires, on average, almost the same number of comparisons as searching in a sorted array by binary search.
      - Delete
        
        More difficult, but same efficiency as insertion and search
- - - - requirements
        
        the difference between the heights of the left and right subtrees of every node never exceed 1
      - DEFINITION
        
        Is a binary search tree in which the balance factor of every node, which is defined as the difference between the heights of the node’s left and right subtrees, is either 0 or +1 or −1
    - - requirements
        
        the height of one subtree being twice as large as the
        other subtree of the same node
  - - - This rotation is performed after a new key is inserted into the left subtree of the left child of a tree whose root had the balance of +1 before the insertion.
    - - Is the mirror image of the
        single R-rotation
      - Performed after a new key is inserted into the right
        subtree of the right child of a tree whose root had the balance of −1 before the insertion.
    - - combination of two rotations
      - perform the L-rotation
        of the left subtree of root r
        
        then perform R-rotation of the new tree rooted at
        r
      - It is performed after a new key is inserted into the right subtree of the left child of a tree whose root had the balance of +1 before the insertion.