Please enable JavaScript.

Coggle requires JavaScript to display documents.

Balanced Search Trees - Coggle Diagram

- - - - An unbalanced binary search tree is transformed into a balanced one. Because of this, such trees are called self-balancing. Specific implementations of this idea differ by their definition of balance. An AVL tree requires the difference between the heights of the left and right subtrees of every node never exceed 1. A red-black tree tolerates the height of one subtree being twice as large as the other subtree of the same node. If an insertion or deletion of a new node creates a tree with a violated balance requirement, the tree is restructured by one of a family of special transformations called rotations that restore the balance required.
        
        AVL tree
        
        A binary search tree in which the balance factor ofevery node, which is defined as the difference between the heights of the node’sleft and right subtrees, is either 0 or +1 or −1. (The height of the empty tree isdefined as −1. The balance factor can also be computed as the differencebetween the numbers of levels rather than the height difference of the node’s leftand right subtrees.)
        
        Rotations
        
        A rotation in an AVL tree is a local transformation of its subtree rooted at a node whose balance has become either +2 or −2. The rotations are not trivial transformations, though fortunately they can be done in constant time. Not only should they guarantee that a resulting tree is balanced, but they should also preserve the basic requirements of a binary search tree.
        
        single right rotation, or R-rotation
        
        1 more item...
        
        single left rotation, or L-rotation
        
        1 more item...
        
        double left-right rotation (LRrotation)
        
        1 more item...
        
        double right-left rotation (RL-rotation)
        
        1 more item...
    - - Allow more thanone element in a node of a search tree. Specific cases of such trees are 2-3trees, 2-3-4 trees, and more general and important B-trees. They differ in thenumber of elements admissible in a single node of a search tree, but all areperfectly balanced.