Scribd Logo
Upload

Welcome to Scribd!

  • 19 views

    AVL Tree

    Uploaded by

    aliahmadfareed ch
    The AVL tree is a self-balancing binary search tree where the difference between the heights of left and right subtrees is less than or equal to one. It stays balanced through rotations when insertions or deletions would cause the tree to become unbalanced. There are four types of rotations - RR, LL, LR, and RL - that are performed to rebalance the tree based on the balance factor of nodes.

    Copyright:

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

    AVL Tree

    Uploaded by

    aliahmadfareed ch
    19 views3 pages
    The AVL tree is a self-balancing binary search tree where the difference between the heights of left and right subtrees is less than or equal to one. It stays balanced through rotations when insertions or deletions would cause the tree to become unbalanced. There are four types of rotations - RR, LL, LR, and RL - that are performed to rebalance the tree based on the balance factor of nodes.

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The AVL tree is a self-balancing binary search tree where the difference between the heights of left and right subtrees is less than or equal to one. It stays balanced through rotations when insertions or deletions would cause the tree to become unbalanced. There are four types of rotations - RR, LL, LR, and RL - that are performed to rebalance the tree based on the balance factor of nodes.

    Copyright:

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

    AVL Tree

    Uploaded by

    aliahmadfareed ch
    The AVL tree is a self-balancing binary search tree where the difference between the heights of left and right subtrees is less than or equal to one. It stays balanced through rotations when insertions or deletions would cause the tree to become unbalanced. There are four types of rotations - RR, LL, LR, and RL - that are performed to rebalance the tree based on the balance factor of nodes.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 3

    AVL Tree(By Adelson, Velskii, and Landi)

    AVL tree is a binary search tree in which the difference of heights of left and
    right subtrees of any node is less than or equal to one.

    • Tree is said to be balanced if balance factor of each node is in between -1 to


    1, otherwise, the tree will be unbalanced and need to be balanced.

    Balance Factor (k) = height (left(k)) - height (right(k))

    • After adjustment the binary search tree, balanced factor must be equal to
    one of them (- 1 , 0 , 1 ).
    • Concept of AVL only works on binary search tree.

    AVL Rotations
    We perform rotation in AVL tree only in case if Balance Factor is other than
    ( -1 , 0 , 1 ).

    1. RR Rotation
    When binary search tree(BST) becomes unbalanced, due to a node is inserted
    into the right subtree of the right subtree of A, then we perform RR rotation.
    • RR rotation is an anticlockwise rotation, which is applied on the edge
    below a node having balance factor -2.
    2. LL Rotation
    When binary search tree(BST) becomes unbalanced, due to a node is inserted
    into the left subtree of the left subtree of C,then we perform LL rotation.

    • LL rotation is clockwise rotation, which is applied on the edge below a


    node having balance factor 2.

    3. LR Rotation
    • LR rotation = RR rotation + LL rotation.
    • First RR rotation is performed on subtree.
    • Then LL rotation is performed on full tree.
    By full tree we mean the first node from the path of inserted node whose
    balance factor is other than -1, 0, or 1.
    4. RL Rotation
    • R L rotation= LL rotation + RR rotation.
    • First LL rotation is performed on subtree.
    • Then RR rotation is performed on full tree.
    By full tree we mean the first node from the path of inserted node whose
    balance factor is other than -1, 0, or 1.

    You might also like