Binary Search Tree

Is an ordered dictionary ADT.
Operations with k = key, v = value: 


  • insert(k, v):inserts an element with value v and key k
  • search(k): returns the value with key k
  • delete(k): deletes the element with key k
  • contains(k): true if the dictionary contains an element with key k
  • floor(k): returns next key ≤ k
  • ceiling(k): returns next key ≥ k
  • size(): returns the size of the dictionary 

This is also called Ordered Symbol Tables


The left child is smaller than the parent and the right child is larger than the parent.
The height is the number of edges on the longest path from node to a leaf
Depth of anode is the number of edges to the root.
Height of tree = depth of deepest node

Properties

- Nodes left subtree contains keys with strictly less than node's keys
- Nodes right subtree contains keys with strictly more than node's keys.
- The left and right subtrees are binary trees
- There cannot be the same keys

Are these trees:

Yes





No
-> 50 is bigger than 12




Yes




Yes




No
-> 13 is bigger than 12




Yes




No
-> repeats

Problem:
We are doing a charity call but we need to know exactly how many families earn exactly $a amount and less than $a amount or more than $a amount.
What kind of Operation do we need?

Operations:



  • height(): returns the height of the node
  • search(k) : returns an object v with key k
  • searchMin() : finds the minimum key k
  • searchMax() : finds the maximum key k
  • successor(): returns next key > k
  • predecessor(): returns next key < k
  • insert(k,v): inserts an object v with key k
  • delete(k) : deletes the node with key k  


Height

Makes use of recursion to get the height.
We will check the height of the left and the right tree and return the biggest +1
ie. h(o) = max(h(o.left),h(o.right)) +1
We will stop checking when reach the base case,
ie. h(o) = 0 where o is the tree

PSEUDOCODE
function height()
  leftHeight = -1 //this is a zero becos we will return a +1 (Basecase)
  rightHeight = -1
  if m_leftTree is not null
       leftHeight = m_leftTree.height()
  if m_rightTree is not null
       rightHeight = m_rightTree.height()
  return max(leftHeight, rightHeight) + 1

In a standard BST with N nodes, what is worst case height?
->O(n)
It can be one sided and form a chain

Searching 

We binary search inside a bst using recussion
If the searchingkey < currentKey
-> Go left
    -> If left is null, return not found
         else continue recusion
else if searchingkey > currentKey
 -> Go Right
     -> if right is null, return not found
else
return this



MinMax keys

The minimum key is at the left most node and the maximum key is the right most node 
function searchMin()
   if m_leftTree is not null
       return m_leftTree.searchMin()

return this


function searchMax()
   if m_rightTree is not null
       return m_rightTree.searchMax()
    return this  

In the standard BST, which search have the worst time case?
Searchmin , searchmax , search
->They are all the same O(h)

 Successor


Successor is the node with the smallest key that is larger than K

If o has right subtree
-> min of right tree
else
   If o is left child, its parent is successor
   -> Move up one
   If o is right child, the successor is an ancestor that is bigger than myself
   -> Keep going up till find bigger


function successor()
if m_rightTree is not null then
   return m_rightTree.searchMin()
else
    p = m_parent, temp = this //p is my parent
    while (p is not null) and (temp == p.rightTree)
//continue going up, stop loop when i am left tree
           temp = p, p = temp.m_parent //change p into my parent
      if p is null then return -1 //theres no successor
      else return p

O(logn)/O(h)

For predecessor, everything reversed,
continue the loop if I am still left tree,
stop when I am the right child,
Return parent

Insertion

if insertedKey > current
-> go right
   -> if key is null, put here //create new node right
      else recurse insert
else if insertedKey < current
-> go left
   -> Key is null, put here //create new node left
   else recurse insert
return


function insert(Key k)
   if k < m_key
        if m_leftTree is not null
               return m_leftTree.insert(k)
         else
                m_leftTree = new BinaryTree(k)
    else if k > m_key
       if m_rightTree is not null
            return m_rightTree.insert(k)
       else
             m_rightTree = new BinaryTree(k)
    else return  

Just need to go left or right and check for null each time, insert when see null
If not continue recursion

This is not AVL, we don't need to make it balance/ do swaps
This is the reason why there is a case where the bst is lopsided.

O(h)

Shape of the tree & Order of Insertion

Performance of searching and inserts depends on height.
Height depends on shape
Shape depends on order of insertion (and deletions)

But it is not infinite amount of shapes when inserted in different order. There is always the same amount of shapes of BST. But they might be different to each other.

Delete

- Node not found, do nothing
- Node is a leaf, remove
- Node has one child, remove node and connect child to parent
- Node has 2 children, replace node with its successor. ,
if successor have child, reattach loose successor nodes with parents

Condition:
1. Successor s maintains the BST property when inserted to where k use to be
2. The successor s has at most 1 right child so we can reattach


O(h)
-> Traversal + Successor

Ceiling

-> Number does not have to be from the tree.

function ceiling(Node x, k)
if x is null then return null
if x.key == k then return x //if equal
if k > x.key then //go right
    return ceiling(x.righttree,K)
if k < x.key then
     t= ceiling(x.leftTree,k)
   // enter left tree check if its larger than key, if it is then recurse there
     if t is not null, return t
    else return me

O(h)

Printing nodes in Order

1. InOrder
Left, self, Right

function in-order-traversal()
// Traverse left sub-tree
if m_leftTree is not null
       m_leftTree.in-order-traversal()

visit(this)

// Traverse right sub-tree
if m_rightTree is not null then
     m_rightTree.in-order-traversal()  

- If theres a left subtree, traverse left
- else print myself, the right subtree downwards then go to parent


2. Pre-Order (Deep-Copy)
Self, Left, Right

function deepCopy()
n = new Node(key, value)
// Traverse left sub-tree
if m_leftTree is not null
    n.m_leftTree = m_leftTree.deepCopy()

// Traverse right sub-tree
if m_rightTree is not null
     n.m_rightTree = m_rightTree.deepCopy()
return n  


3. Post-Order (Good for deleting)
Left, Right, Self

function deleteTree(Node n)
// Traverse left sub-tree
if n.m_leftTree is not null
     deleteTree(n.m_leftTree)

// Traverse right sub-treeif n.m_rightTree is not null then
      deleteTree(n.m_rightTree)
free(n)