9. Binary search trees

Binary search trees

Given two things: a list of $\boxed{L}$ items and a linear order $\boxed{\prec }$ on them. A binary search tree for $L$ and $\prec$ is a binary tree in which every vertex is labelled with an item from $L$ such that we have:

1. the label of each vertex:
   • is $\prec$-greater than the labels of all vertices in the left subtree
   • is $\prec$-less than the labels of all vertices in its right subtree
2. every path in the tree be compatible with the order of listing:

   graph G {
    layout=neato
   	node[shape=point]
    
    a[xlabel="5" pos="2,4!"]
    b[xlabel="3" pos="1,3!"]
    c[xlabel="128" pos="3,3!"]
    d[xlabel="2" pos="0.5,2!"]
    e[xlabel="4" pos="1.5,2!"]
    f[xlabel="15" pos="2.5,2!"]
    g[xlabel="20" pos="3,1!"]
    
    a--b,c
    b--d,e
    c--f
    f--g
   }

   For the list $(5,128,3,2,15,4,20)$ and linear order $\le$.

Binary Tree from Linearly ordered list

We are given a list $L$ of items, and a linear order $\prec$ on them. We go through each member of the list, from left to right:

• First item: becomes our root
• Comparing: We take the next item in the list, and first compare it with the labels of the ‘old’ vertices already in the list, starting from the root then:
  • moving to the left: if the new item is $\prec$-less than the label of the respective ‘old’ vertex, if this ‘old’ vertex has a left child, or:
  • moving to the right: if the new item is $\prec$-greater than the label of the respective ‘old’ vertex, if this ‘old’ vertex has a right child.
• Adding:
  • When the new item is $\prec$-less than the label of an ‘old’ vertex and the vertex has no left child, insert a new left child to the ‘old’ vertex and label it with the new item.
  • When the new item is $\prec$-larger than the label of an ‘old’ vertex and the vertex has no child, then we insert a new right child to the ‘old’ vertex and label it with the new item.

Example BST

Build a binary search tree for the following list of words using the lexicographical order $\boxed{\prec }$.

$$\boxed{\text{mathematics, physics, geography, zoology, meteorology, geology, psychology}}$$

1. Take mathematics and label the root with it:

   graph G {
   	m[shape=point xlabel=mathematics]
   }

2. We take physics and compare it with mathematics, $\text{mathematics}\prec \text{physics}$, mathematics has no right child so we label a new right child with physics:

   graph G {
   	layout=neato
    node[shape=point]
   	m[xlabel=mathematics pos="0,0!"]
    p[xlabel=physics pos="1,-1!"]
    
    m--p
   }

3. We take geography, $\text{geography}\prec \text{mathematics}$, mathematics has no left child so we create a new left child with geography:

   graph G {
   	layout=neato
    node[shape=point]
   	m[xlabel=mathematics pos="0,0!"]
    p[xlabel=physics pos="1,-1!"]
    g[xlabel=geography pos="-1,-1!"]
    
    m--p,g
   }

4. We take zoology, $\text{mathematics}\prec \text{zoology}$, so we move to the right child of the root and take the label, which in this case is physics.
5. We now compare zoology with physics, $\text{physics}\prec \text{zoology}$, physics has no right child, hence we label a new right child:

   graph G {
   	layout=neato
    node[shape=point]
   	m[xlabel=mathematics pos="0,0!"]
    p[xlabel=physics pos="1,-1!"]
    g[xlabel=geography pos="-1,-1!"]
    z[xlabel=zoology pos="1.5,-2!"]
    
    m--p,g
    p--z
   }

6. We take meteorology, $\text{mathematics}\prec \text{meteorology}$, so we move to the right child of the root and take the label, which in this case is physics.
7. We now compare zoology with physics, $\text{meteorology}\prec \text{physics}$, physics has no left child, hence we label a new left child:

   graph G {
   	layout=neato
    node[shape=point]
   	m[xlabel=mathematics pos="0,0!"]
    p[xlabel=physics pos="1,-1!"]
    g[xlabel=geography pos="-1,-1!"]
    z[xlabel=zoology pos="1.5,-2!"]
    2[xlabel=meteorology pos="0.5,-2!"]
    
    m--p,g
    p--z,2
   }

8. We take geology, $\text{geology}\prec \text{mathematics}$, so we move to the left child of the root and take the label, which in this case is geography.
9. We now compare geology with geography, $\text{geography}\prec \text{geology}$, physics has no right child, hence we label a new right child:

   graph G {
   	layout=neato
    node[shape=point]
   	m[xlabel=mathematics pos="0,0!"]
    p[xlabel=physics pos="2,-1!"]
    g[xlabel=geography pos="-2,-1!"]
    z[xlabel=zoology pos="2.5,-2!"]
    2[xlabel=meteorology pos="1.5,-2!"]
    3[xlabel=geology pos="-1.5,-2!"]
    
    m--p,g
    p--z,2
    g--3
   }

10. Finally, we take psychology, compare it with mathematics, move to the right, compare it with physics, move to the right then compare it with zoology, $\text{psychology}\prec \text{zoology}$, hence create a new left child:

    graph G {
    	layout=neato
     node[shape=point]
    	m[xlabel=mathematics pos="0,0!"]
     p[xlabel=physics pos="2,-1!"]
     g[xlabel=geography pos="-2,-1!"]
     z[xlabel=zoology pos="2.5,-2!"]
     2[xlabel=meteorology pos="1.5,-2!"]
     3[xlabel=geology pos="-1.5,-2!"]
     4[xlabel=psychology pos="2,-3!"]
     
     m--p,g
     p--z,2
     g--3
     z--4
    }

Say we had to add a new word, chemistry, to our BST. How many comparisons do we need to locate or find it?

In this case, it’s just $2$. We compare it with mathematics, move left, compare it with geography. As $\text{chemistry}\prec \text{geography}$ and geography has no left child, we know that chemistry is not in the tree. We can create a new left child and label it as such.

graph G {
	layout=neato
	node[shape=point]
	m[xlabel=mathematics pos="0,0!"]
	p[xlabel=physics pos="2,-1!"]
	g[xlabel=geography pos="-2,-1!"]
	z[xlabel=zoology pos="2.5,-2!"]
	2[xlabel=meteorology pos="1.5,-2!"]
	3[xlabel=geology pos="-1.5,-2!"]
	5[label=chemistry pos="-2.5,-2!" shape="plain"]
	4[xlabel=psychology pos="2,-3!"]
 
	m--p,g
	p--z,2
	g--3
	z--4
	g--5
 
	subgraph cluster0 {
		5
	}
}