Scribd Logo
Upload

Welcome to Scribd!

  • 214 views

    ADT AVL Tree V3

    Uploaded by

    RishiGupta
    The document describes functions for operations on an AVL tree: i) Create-an-AVL-Tree-Root creates the root node of an empty AVL tree. ii) Insert-a-new-node inserts a new node, balances the tree by rotations if needed, and returns the potentially new root pointer. iii) Delete-a-node deletes a node, balances the tree by rotations, and returns the potentially new root pointer.

    Copyright:

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

    ADT AVL Tree V3

    Uploaded by

    RishiGupta
    214 views4 pages
    The document describes functions for operations on an AVL tree: i) Create-an-AVL-Tree-Root creates the root node of an empty AVL tree. ii) Insert-a-new-node inserts a new node, balances the tree by rotations if needed, and returns the potentially new root pointer. iii) Delete-a-node deletes a node, balances the tree by rotations, and returns the potentially new root pointer.

    Original Description:

    About AVL TREES

    Copyright

    © © All Rights Reserved

    Available Formats

    DOC, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes functions for operations on an AVL tree: i) Create-an-AVL-Tree-Root creates the root node of an empty AVL tree. ii) Insert-a-new-node inserts a new node, balances the tree by rotations if needed, and returns the potentially new root pointer. iii) Delete-a-node deletes a node, balances the tree by rotations, and returns the potentially new root pointer.

    Copyright:

    © All Rights Reserved
    Download as DOC, PDF, TXT or read online from Scribd
    Download as doc, pdf, or txt
    214 views4 pages

    ADT AVL Tree V3

    Uploaded by

    RishiGupta
    The document describes functions for operations on an AVL tree: i) Create-an-AVL-Tree-Root creates the root node of an empty AVL tree. ii) Insert-a-new-node inserts a new node, balances the tree by rotations if needed, and returns the potentially new root pointer. iii) Delete-a-node deletes a node, balances the tree by rotations, and returns the potentially new root pointer.

    Copyright:

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

    ADT AVL Tree

    Functions to be provided:
    i)

    An-AVL-Tree-Ptr := Create-an-AVL-Tree-Root (root-data-value);

    ii)

    An-AVL-Tree-Ptr := Insert-a-new-node (new-data-value, An-AVL-Tree-Ptr);

    iii)

    An-AVL-Tree-Ptr := Delete-a-node (node-data-value, An-AVL-Tree-Ptr);

    [1]. Create An AVL Tree Root function


    An-AVL-Tree-Ptr := Create-an-AVL-Tree-Root (root-data-value);
    {
    /*
    This functions creates (allocates space for) the root node of an AVL tree, initializes all the
    parts of the root node (like the data-value, L-son-ptr, R-son-ptr, H, BF, P-ptr) and returns
    the pointer to the just created AVL tree root;
    */
    Structure AVL-node
    {
    pointer AVL-node parent-ptr;
    int H, BF, data-value;
    pointer AVL-node L-son-ptr, R-son-ptr;
    }
    pointer AVL-node Root-ptr;
    Root-ptr := Allocate-space (AVL-node);
    Root-ptr.parent-ptr := null;
    Root-ptr.H := 0;
    Root-ptr.BF := 0;
    Root-ptr.data-value := root-data-value;
    Root-ptr.L-son-ptr := null;
    Root-ptr.R-son-ptr := null;
    return (root-ptr);
    } /* end of Create-an-AVL-Tree-Root

    [2]. Insert-a-Node function:


    An-AVL-Tree-Ptr := Insert-a-new-node (new-data-value, An-AVL-Tree-Ptr);
    {
    /*
    This function inserts a node into a given existing AVL tree; if the node already exists in
    the AVL tree, this function returns a null value; otherwise, it (i) inserts the new node, (ii)
    checks if any of its parents violate the AVL node property, (iii) then restores the balance,
    (iv) updates the H & BF values of all the affected nodes and (v) then returns the pointer
    to the root node of the re-balanced AVL tree (in some cases, this pointer can be different
    from the previously existing root pointer);
    */
    boolean node-is-found, violation-is-found = false;
    pointer AVL-node q1, q2, q3;
    (node-is-found, q1) := find (new-data-value, An-AVL-Tree-Ptr);
    if (node-is-found)
    then { print (new-data-value already exists; cannot insert node);
    return (null);
    }
    q2 := allocate-space (AVL-node);
    q2.data-value := new-data-value;
    q2.L-son-ptr := null;
    q2.R-son-ptr := null;
    q2.H := 0;
    q2.BF := 0;
    q2.parent-ptr := q1;
    if (q1.data-value > new-data-value)
    then q1.L-son-ptr := q2;
    else q1.R-son-ptr := q2;
    previous-node-BF := q2.BF;
    while (!violation-is-found) && (q1 != null) do
    {
    HL := q1.L-son-ptr.H
    HR := q1.R-son-ptr.H;
    q1.H := Max (HL, HR) + 1;
    q1.BF := HL HR;
    current-node-BF := q1.BF;

    if (current-node-BF == 2) OR (current-node-BF == -2)


    then violation-is-found := true;
    else { q1 := q1.parent-ptr;
    previous-node-BF := current-node-BF;
    }
    } /* end of while loop */
    if (!violation-is-found)
    then return (An-AVL-Tree-Ptr);
    if (violation-is-found)
    then {
    if (current-node-BF == 2) && (previous-node-BF == 1)
    then q3 := single-right-rotation (q1);
    else if (current-node-BF == -2) && (previous-node-BF == 11)
    then q3 := single-left-rotation (q1);
    else if (current-node-BF == 2) && (previous-node-BF == -1)
    then q3 := double-left-right-rotation (q1);
    else q3 := double-right-left-rotation (q1);
    An-AVL-Node-Ptr := update-H-BF-of-parent-nodes (q3);
    return (An-AVL-Tree-Ptr);
    }
    p := Single-Right-Rotation (n);
    {
    pointer AVL-node p;
    p := n.L-son-ptr;
    n.L-son-ptr := p.R-son-ptr;
    p.R-son-ptr.parent-ptr := n;
    p.R-son-ptr := n;
    p.parent-ptr := n.parent-ptr;
    if (p.parent-ptr.L-son-ptr == n)
    then p.parent-ptr.L-son-ptr := p;
    else p.parent-ptr.R-son-ptr := p;
    n.parent-ptr := p;
    n.H := Max (n.L-son-ptr.H, n.R-son-ptr.H) + 1;
    n.BF := n.L-son-ptr.H n.R-son-ptr.H;
    p.H := Max (p.L-son-ptr.H, p.R-son-ptr.H) + 1;

    p.BF := p.L-son-ptr.H p.R-son-ptr.H;


    return (p);
    }
    p := Single-Left-Rotation (n);
    {
    pointer AVL-node p;
    p := n.R-son-ptr;
    n.R-son-ptr := p.L-son-ptr;
    p.L-son-ptr.parent-ptr := n;
    p.L-son-ptr := n;
    p.parent-ptr := n.parent-ptr;
    if (p.parent-ptr.L-son-ptr == n)
    then p.parent-ptr.L-son-ptr := p;
    else p.parent-ptr.R-son-ptr := p;
    n.parent-ptr := p;
    n.H := Max (n.L-son-ptr.H, n.R-son-ptr.H) + 1;
    n.BF := n.L-son-ptr.H n.R-son-ptr.H;
    p.H := Max (p.L-son-ptr.H, p.R-son-ptr.H) + 1;
    p.BF := p.L-son-ptr.H p.R-son-ptr.H;
    return (p);
    }
    p := Double-Left-Right-Rotation (n);
    {
    pointer AVL-node p;
    p := Single-Left-Rotation (n.L-son-ptr);
    p := Single-Right-Rotation (n);
    return (p);
    }
    p := Double-Right-Left-Rotation (n);
    {
    pointer AVL-node p;
    p := Single-Right-Rotation (n.R-son-ptr);
    p := Single-Left-Rotation (n);
    return (p);
    }

    You might also like