• Tree:
  • A connected graph with no circuits
• Binary Search Tree:
  • A binary tree in which each node contains a larger value than all the values in its left subtree and a smaller value that all the values in its right subtree
• Balanced Binary Search Tree:
  • A roughly symmetrical BST
  • One common definition is that there is a difference of at most one level of depth among the various leaves

Using a Linked Structure

Traversals

A preorder traversal of this BST will print the values in the nodes in the following order: 23, 15, 8, 12, 25, 24

A postorder traversal of this BST will print the values in the nodes in the following order: 12, 8, 15, 24, 25, 23

A Recursive Algorithm

• The Easy Case(s):
  • The Node is empty
  • The Node contains the target
• Refinement:
  • Search either the left or right child

    search(current, target)
    {
      if (current == null)               print("Not present!")
      else if (current's data == target) print("Found!")
      else if (current's data >target) search(current's left, target)
      else                               search(current's right, target)
    }
  

A Non-Recursive Algorithm

    search(current, target
    {
      while ( (current != null) && (current's data != target) )
      {

          if (current's data > target) current = current's left
	  else                           current = current's right
      }

      if (current's data == target) print("Found!")
      else                          print("Not present!")
    }
  

• An Example:
  • 
• Sorting with Inorder Traversal:
  • An inorder traversal visits the nodes in the following order: 8, 12, 15, 23, 24, 25

• The Easy Case:
  • If the tree is empty, make root the new node
• Refining the Other Cases:
  • If the tree is not empty and the new node is less than the existing node, insert the new node into the left subtree
  • If the tree is not empty and the new node is greater than the existing node, insert the new node into the right subtree
• An Example:
  • 
  • A 21 would be inserted as the right child of the node containing the 18
  • A 26 would be inserted as the left child of the node containing the 29

Ignoring Balance

    insert(current, n)
    {
      if (current == null)                    current = n;
      else if (n's data < current's data) insert(current's left,  n)
      else if (n's data > current's data) insert(current's right, n)
      else                                   print("Duplicate!")
    }
    

• The Easy Cases:
  • If the node to be removed is a leaf then it must be replaced by null
  • If the node to be removed has one nonempty subtree then the parent of the node to be removed must be adjusted to point to the nonempty subtree
• The Hard Case - A Node with Two Nonempty Subtrees:
  • We must decide which subtree should be pointed to by the parent
  • There are several ways to do this

• One Way to Handle the Hard Case:
  • Find the "immediate predecessor" of the node being removed by moving to its left child and then as far right as possible
  • Remove immediate predecessor
  • Replace the removed node with the immediate predecessor
• Why It Works:
  • The immediate predecessor has no right child (since we went as far right as possible)
  • So, it can be easily removed from its current position

• An Example:
  • 
• The Node to Remove:
  • The root node
• The Process:
  • Move to its left child and search to the right as far as we can which gets us to the node containing the 18
  • Remove that node (using the algorithm discussed above)
  • Replace the value in the root node with the 18
• The Resulting BST:
  •