Function find root index in tree

find root index in tree

Format:

find root index in tree

Input:

Output:

Conditional properties that reference this function:

• if find referece to node i in tree tree = False, then find root index in tree = i (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, l_right)
  • new_val < root_val
  • new_val < l_val

  then result of inserting new_val to tree tree = result of rotating (output of the bst_insert function where input tree is tree, value is new_val and index is ri) 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, 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, l_right)

  then result of rotating tree clockwise = result of storing (node (l_val, l_left, ri)) at index left of stack (result of storing (node (root_val, l_right, right)) at index ri of stack tree)

  (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

  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)

Comments

Please log in to add comments