Function output of the bst_insert function where input tree is tree, value is value and index is index

tree insert tree

Format:

output of the bst_insert function where input tree is tree, value is value and index is index

Input:

Output:

Conditional properties that reference this function:

• if the following are true:
  • val < a
  • the element at index i of stack tree = node (a, left, right)

  then output of the bst_insert function where input tree is tree, value is val and index is i = output of the bst_insert function where input tree is tree, value is val and index is left

  (link)
• if the following are true:
  • val > a
  • the element at index i of stack tree = node (a, left, right)

  then output of the bst_insert function where input tree is tree, value is val and index is i = output of the bst_insert function where input tree is tree, value is val and index is right

  (link)
• if the following are true:
  • val < a
  • the element at index i of stack tree = node (a, (-1), right)

  then output of the bst_insert function where input tree is tree, value is val and index is i = result of storing (node (a, (length of stack tree), right)) at index i of stack (result of appending (node (val, (-1), (-1))) to tree)

  (link)
• if the following are true:
  • val > a
  • the element at index i of stack tree = node (a, left, (-1))

  then output of the bst_insert function where input tree is tree, value is val and index is i = result of storing (node (a, left, (length of stack tree))) at index i of stack (result of appending (node (val, (-1), (-1))) to 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, 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)

Comments

Please log in to add comments