Scribd Logo
Upload

Welcome to Scribd!

  • 30 views

    AVL Tree Example

    Uploaded by

    sudhan
    AVL trees are self-balancing binary search trees that assign a balance factor to each node to determine if the tree is balanced. If a node has a balance factor of +2 or -2, it is rotated to rebalance the tree using one of four rotation cases. The document then provides an example of inserting values into an AVL tree, calculating balance factors after each insertion, and performing rotations to rebalance the tree when needed to maintain the balance factor of all nodes being between -1 and +1.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    AVL Tree Example

    Uploaded by

    sudhan
    30 views17 pages
    AVL trees are self-balancing binary search trees that assign a balance factor to each node to determine if the tree is balanced. If a node has a balance factor of +2 or -2, it is rotated to rebalance the tree using one of four rotation cases. The document then provides an example of inserting values into an AVL tree, calculating balance factors after each insertion, and performing rotations to rebalance the tree when needed to maintain the balance factor of all nodes being between -1 and +1.

    Original Title

    AVLTreeExample.pdf

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    AVL trees are self-balancing binary search trees that assign a balance factor to each node to determine if the tree is balanced. If a node has a balance factor of +2 or -2, it is rotated to rebalance the tree using one of four rotation cases. The document then provides an example of inserting values into an AVL tree, calculating balance factors after each insertion, and performing rotations to rebalance the tree when needed to maintain the balance factor of all nodes being between -1 and +1.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    30 views17 pages

    AVL Tree Example

    Uploaded by

    sudhan
    AVL trees are self-balancing binary search trees that assign a balance factor to each node to determine if the tree is balanced. If a node has a balance factor of +2 or -2, it is rotated to rebalance the tree using one of four rotation cases. The document then provides an example of inserting values into an AVL tree, calculating balance factors after each insertion, and performing rotations to rebalance the tree when needed to maintain the balance factor of all nodes being between -1 and +1.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 17

    AVL Tree Example

    AVL trees are self-balancing binary search trees.


    Each node of an AVL tree is assigned a balance factor as follows:

    • -1 if the depth of the node’s left subtree is 1 more than the depth of the right
    node’s left sub tree
    • +1 if the depth of the node’s left sub tree is 1 more than the depth of the
    right node’s left subtree
    • 0 if both of the node’s subtrees has the same depths
    • -2 if the depth of the node’s left subtree is 2 more than the depth of the right
    node’s left sub tree
    • +2 if the depth of the node’s left sub tree is 2 more than the depth of the
    right node’s left subtree
    • If the balance factor becomes -2 or +2, the tree must be rebalanced.

    Next: Rotations -->


    If the balance factor of a node in an AVL tree is +2 or -2, the node is rotated to re-
    balance the tree using one of the four cases shown in the following picture:

    The 4 cases of AVL tree rebalancing using rotations. Picture


    created by Marc Tanti, licensed for reuse under the GNU
    Free Documentation License, Version 1.2

    Next: example -->


    Initial AVL tree with balance factors: Balance ok

    0 57

    0 26 +1 72

    -1 25 0 38 0 63 -1 94

    0 3 0 37 0 47 0 78

    Next step: insert 1 -->


    Insert 1 and recalculate balance factors Balance not ok
    (Balance factor of
    -1 57 -2 is not allowed)

    -1 26 +1 72

    -2 25 0 38 0 63 -1 94

    -1 3 0 37 0 47 0 78

    0 1

    Next step: Find rebalancing case -->


    Find rebalancing case Balance not ok

    -1 57

    -1 26 +1 72

    Left Left Case


    -2 25 0 38 0 63 -1 94
    Pivot

    -1 3 0 37 0 47 0 78

    0 1

    Next step: apply Left Left rebalancing -->


    Rebalance and recalculate balance factors Balance ok

    0 57

    0 26 +1 72

    0 3 0 38 0 63 -1 94

    0 1 0 25 0 37 0 47 0 78

    Next step: insert 30 -->


    Insert 30 and recalculate balance factors Balance ok

    -1 57

    +1 26 +1 72

    0 3 -1 38 0 63 -1 94

    0 1 0 25 -1 37 0 47 0 78

    0 30

    Next step: Insert 32 -->


    Insert 32 and recalculate balance factors Balance not ok

    -2 57

    +2 26 +1 72

    0 3 -2 38 0 63 -1 94

    0 1 0 25 -2 37 0 47 0 78

    +1 30

    0 32

    Next step: Find rebalancing case -->


    Find rebalancing case Balance not ok

    -2 57

    +2 26 +1 72

    0 3 -2 38 0 63 -1 94

    0 1 0 25 -2 37 0 47 0 78

    +1 30
    Left Right Case
    0 32

    Next step: Rebalance (Step 1) -->


    Rebalance (Step 1) Balance not ok

    -2 57

    +2 26 +1 72

    0 3 -2 38 0 63 -1 94

    0 1 0 25 -2 37 0 78
    0 47

    -1 32

    0 30

    Next step: Rebalance (Step 2) -->


    Rebalance (Step 2) and recalculate balance factors Balance ok

    -1 57

    +1 26 +1 72

    0 3 -1 38 0 63 -1 94

    0 1 0 25 0 32 0 47 0 78

    0 30 0 37

    Next step: Insert 35 -->


    Insert 35 and recalculate balance factors Balance not ok

    -2 57

    +2 26 +1 72

    0 3 -2 38 0 63 -1 94

    0 1 0 25 +1 32 0 47 0 78

    0 30 -1 37

    0 35

    Next step: Find rebalancing case -->


    Insert 35 Balance not ok

    -2 57

    +2 26 Start from first spot (from +1 72


    bottom of tree) where
    balance factor is incorrect.

    0 3 -2 38 0 63 -1 94

    0 1 0 25 +1 32 0 47 0 78

    0 30 -1 37
    Left Right Case

    0 35

    Next step: Rebalance (Step 1) -->


    Rebalance (Step 1) Balance not ok

    -2 57

    +2 26 +1 72

    0 3 -2 38 0 63 -1 94

    0 1 0 25 -2 37 0 47 0 78

    0 32

    0 30 0 35

    Next step: Rebalance (Step 2) -->


    Rebalance (Step 2) Balance ok

    -1 57

    +1 26 +1 72

    0 3 0 37 0 63 -1 94

    0 1 0 25 0 32 +1 38 0 78

    0 30 0 35 0 47

    Next step: Finished! -->


    Finished! Balance ok

    -1 57

    +1 26 +1 72

    0 3 0 37 0 63 -1 94

    0 1 0 25 0 32 +1 38 0 78

    0 30 0 35 0 47

    Exercise: insert 36

    You might also like