Function result of balancing the tree tree

tree balance tree

Format:

result of balancing the tree tree

Input:

list tree -

Output:

node - None

Properties that reference this function:

result of removing value from tree tree = result of balancing the tree (pop value from tree tree) (tree deletion)
result of AVL insert of tree tree and value value = result of balancing the tree (result of inserting value to tree tree) (AVL tree insert)

Conditional properties that reference this function:

  • if the following are true:

    • find root index in tree = ri
    • the element at index ri of stack tree = node (rvalue, left, right)
    • Height of a tree tree and index left = Height of a tree tree and index right

    then result of balancing the tree tree = tree

    (link)

  • if the following are true:

    • find root index in tree = ri
    • the element at index ri of stack tree = node (rvalue, left, right)
    • Height of a tree tree and index left > (Height of a tree tree and index right) + 1
    • the element at index left of stack tree = node (lvalue, lleft, lright)
    • Height of a tree tree and index lleft > Height of a tree tree and index lright

    then result of balancing the tree tree = result of rotating tree clockwise

    (link)

  • if the following are true:

    • find root index in tree = ri
    • the element at index ri of stack tree = node (rvalue, left, right)
    • Height of a tree tree and index left > (Height of a tree tree and index right) + 1
    • the element at index left of stack tree = node (lvalue, lleft, lright)
    • Height of a tree tree and index lleft < Height of a tree tree and index lright

    then result of balancing the tree tree = result of rotating (result of rotating tree twice) clockwise

    (link)

  • if the following are true:

    • height of tree (node (lv, ll, lr)) > (height of tree right) + 1
    • height of tree ll > height of tree lr

    then result of balancing the tree (node (v, (node (lv, ll, lr)), right)) = result of rotating (node (v, (node (lv, ll, lr)), right)) clockwise

    (link)

  • if the following are true:

    • height of tree (node (lv, ll, lr)) > (height of tree right) + 1
    • height of tree ll < height of tree lr

    then result of balancing the tree (node (v, (node (lv, ll, lr)), right)) = result of rotating (node (v, (node (lv, ll, lr)), right)) twice

    (link)


Comments

Please log in to add comments