Function result of rotating tree twice

tree rotate counter-clockwisetree

Format:

result of rotating tree twice

Input:

list tree -

Output:

node - None

Properties that reference this function:

result of rotating (node (v, (node (l, ll, (node (lr, lrl, lrr)))), right)) twice = node (v, (node (lr, (node (l, ll, lrl)), lrr)), right) (AVL tree rotate counter-clockwise)

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 (root_val, left, right)
    • the element at index left of stack tree = node (l_val, l_left, l_right)
    • new_val < root_val
    • new_val > l_val

    then result of inserting new_val to tree tree = result of rotating (result of rotating (output of the bst_insert function where input tree is tree, value is new_val and index is ri) twice) clockwise

    (link)

  • if the following are true:

    • find root index in tree = ri
    • the element at index ri of stack tree = node (root_val, left, right)
    • the element at index left of stack tree = node (l_val, l_left, g)
    • the element at index g of stack tree = node (g_val, g_left, g_right)

    then result of rotating tree twice = result of storing (node (root_val, g, right)) at index ri of stack (result of storing (node (g_val, left, g_right)) at index g of stack (result of storing (node (l_val, l_left, g_left)) at index left of stack 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 (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)) twice

    (link)


Comments

Please log in to add comments