Description

When a new node is inserted into the tree, an attempt is made to to balance (re-order) the nodes around it to limit the depth of the tree. (See the description elsewhere in the documentation.)

Notes

• The pseudo code shows little error checking. See the code for the actual error checking.
• The functions return False if an error occurred and True if no error occurred.
• All nodes have a parent node except the root node. It is set to "None".
• The left subtree contains nodes less than the subtree's root node.
• The right subtree contains nodes greater than the subtree's root node.
• Duplicate nodes are not allowed
• Nodes
  • curnode = current working node
  • parnode = parent node of the current working node
  • pparnode = grand parent node of the current working node

Code

# ----------------------------------------------------------------------------------
# insert a new node into the tree
# ----------------------------------------------------------------------------------
function insert(newnode)                         # pass in the new node
}
   if tree.root == None                          # if there is no tree root node 
   {                                             # defined, insert the new node
      tree.root = newnode
      return True
   {
   return _insert(newnode,root.node)             # find a place to insert the new node
}

# ----------------------------------------------------------------------------------
# insert a new node - helper function
# recursively search for a place to insert the new node
# insert the new node and then try to balance it
# ----------------------------------------------------------------------------------
function _insert(newnode,curnode)                # pass in the new node and the
{                                                # current (working) node
   if newnode.data < tree.root.data
   |  if curnode.left == None                    # can we insert the new node?
   |     newnode.parent = curnode
   |     curnode.left   = newnode
   |     if balance_flag_set { return _balance(curnode) }
   |     return True
   |  else
   |     return _insert(newnode,curnode.left)    # got down the left link
   elif newnode.data > tree.root.data  
   |  if curnode.right == None                   # can we insert the new node?
   |     newnode.parent = curnode
   |     curnode.right  = newnode
   |     if balance_flag_set { return _balance(curnode) }
   |     return True
   |  else
   |     return _insert(newnode,curnode.right)   # go down the right link
   else
      print('Oops: the new node already exists in tree')
      return False
}

# ----------------------------------------------------------------------------------
# balance - helper function
# ----------------------------------------------------------------------------------
function _balance(curnode)                       # pass in the current node
{
   # ---- test current (working) node

   if curnode == None       { return False }     # is there a current node? 
   if curnode == tree.root  { return True }      # don't mess with the tree's root node

   # ---- test current node's parent node

   parnode = curnode.parent

   if parnode == tree.root { return True }       # don't mess with the tree's root node
   if parnode.left != curnode and parnode.right != curnode 
      print('Oops, parnode is not the parent of curnode')
      return False

   # --- test the current node's grand parent node

   pparnode = parnode.parent

   if pparnode.left != parnode and pparnode.right != parnode 
      print('Oops, pparent node is not the parent of parnode')
      return False

   # --- balance the current node?

   if curnode.data < parnode.data
      if curnode.right != None { return True }
   elif curnode.data > paranode.data
      if curnode.left != None { return True }
   else
      print('Oops, a duplicate node in the tree')
      return False

   if pparnode.left == parnode
      pparnode.left = curnode
   else
      pparnode.right = curnode

   curnode.parent = pparnode

   if parnode.left == curnode
      parnode.left = None
   else
      parnode.right = None

   parnode.parent = curnode

   return True
}