Hierarchies and Trees

Prof. Dr. Mirco Schoenfeld

Recap and Motivation

Lists and Arrays just store sequential data

We often have to deal with hierarchical data.

Motivation

https://scrooge-mcduck.fandom.com/wiki/Don_Rosa%27s_Duck_Family_Tree

Motivation

https://www.ckmmphotographic.ca/wordpress/file-structure-for-editing/

Motivation

https://www.thecolumbiasciencereview.com/blog/dinosaurs-reclassified

Motivation

Today, it’s all about

https://en.wikipedia.org/wiki/File:Dwarf_Japanese_Juniper,_1975-2007.jpg

Motivation

Actually…

https://www.art-prints-on-demand.com/a/jones-6/der-umgedrehte-baum.html

Trees in Computer Science

In Computer Science, a tree is an abstract data type that represents hierarchical data with a set of connected nodes.

Trees in Computer Science

A tree is a connected, acyclic, undirected Graph.

Trees in Computer Science

Let \(G = (V,E)\) be a graph with

\(V\) a finite set of vertices (nodes) and
\(E \subseteq \{ \{u,v\} : u,v \in V \}\) a set of edges

Trees in Computer Science

What makes \(G = (V,E)\) a tree is

there is only one path between every pair of nodes \(u,v \in V\)
\(G\) is connected;
as soon as one edge is removed from \(E\), \(G\) is not connected anymore
\(G\) is acyclic;
as soon as one edge is added to \(E\), \(G\) is not acyclic anymore
\(|E| = |V| -1\)

Terminology

Let \(G = (V,E)\) be a tree.

There is exactly one node \(r \in V\) which is called root.
Removing \(r\) transforms a tree into a forest of subtrees.

Räcke (2019)

Terminology

Let \(G = (V,E)\) be a tree with a root \(r \in V\).

every node \(v \in V\) with node \(v \neq r\) is connected to exactly one parent node \(x \in V\) (or: ancestor)
\(v\) is called the child node of \(x \in V\) (or: descendant)
sibling nodes have the same parent node
a node without descendants is a leaf node, all other nodes are inner nodes.

Räcke (2019)

Terminology

Let \(G = (V,E)\) be a tree with a root \(r \in V\).

degree of \(x\): number of descendant nodes of \(x \in V\)
depth of \(x\): length of the path from root \(r\) to \(x \in V\).
level: all nodes sharing the same depth
height of the tree: biggest depth of a node

Räcke (2019)

Terminology

Important terminology:

node
parent
child
ancestors
descendandts
root
leaf

inner node
outer node
depth
height
subtree
size of tree

Why again?

Trees for Search

Remember that we like to organize and search stuff?

Trees for Search

So far, we have used

Arrays:

great for search ( down to \(O(\log n)\) )
sorting is costly (up to \(O(n^2)\) )
undynamic - insertions and deletions
are inefficient

Lists:

dynamic - inserting and deleting in \(O(1)\)
not great for search ( \(O(n)\) )

Trees for Search

Trees can be used for search:

\(O(\log n)\) to insert elements
\(O(\log n)\) to delete elements
\(O(\log n)\) to search elements!

But, we need to organize them first.

Binary Search Trees

Introducing:

The Binary Search Tree

https://commons.wikimedia.org/wiki/File:Binary_search_tree.svg

Binary Search Trees

A binary search tree is

a search tree, i.e. the nodes are ordered
a binary tree, i.e. each node has no more than two children

Binary Search Trees

It is ordered such that

all elements in the left sub-tree of node \(v\) have a smaller value than \(v\) itself, and
all elements in its right sub-tree have a larger value

(We assume that all node-values are different)

Binary Search in Binary Search Trees

Searching in Binary Search Trees is basically binary search.

Disclaimer: The following illustration are made by Harald Räcke (2019, 2021)

Binary Search in Binary Search Trees

Find “17”

Tree-Search(x, key)
    while x ≠ NIL and key ≠ x.key do
        if key < x.key then
            x := x.left
        else
            x := x.right
        end if
    repeat
    return x

Binary Search in Binary Search Trees

Find “17”

Tree-Search(x, key)
    while x ≠ NIL and key ≠ x.key do
        if key < x.key then
            x := x.left
        else
            x := x.right
        end if
    repeat
    return x

Binary Search in Binary Search Trees

Find “17”

Tree-Search(x, key)
    while x ≠ NIL and key ≠ x.key do
        if key < x.key then
            x := x.left
        else
            x := x.right
        end if
    repeat
    return x

Binary Search in Binary Search Trees

Find “17”

Tree-Search(x, key)
    while x ≠ NIL and key ≠ x.key do
        if key < x.key then
            x := x.left
        else
            x := x.right
        end if
    repeat
    return x

Binary Search in Binary Search Trees

Find “17”

Tree-Search(x, key)
    while x ≠ NIL and key ≠ x.key do
        if key < x.key then
            x := x.left
        else
            x := x.right
        end if
    repeat
    return x

Binary Search in Binary Search Trees

Find “17”

Tree-Search(x, key)
    while x ≠ NIL and key ≠ x.key do
        if key < x.key then
            x := x.left
        else
            x := x.right
        end if
    repeat
    return x

Binary Search in Binary Search Trees

Find “17”

Tree-Search(x, key)
    while x ≠ NIL and key ≠ x.key do
        if key < x.key then
            x := x.left
        else
            x := x.right
        end if
    repeat
    return x

Binary Search in Binary Search Trees

Find “8”

Tree-Search(x, key)
    while x ≠ NIL and key ≠ x.key do
        if key < x.key then
            x := x.left
        else
            x := x.right
        end if
    repeat
    return x

Binary Search in Binary Search Trees

Find “8”

Tree-Search(x, key)
    while x ≠ NIL and key ≠ x.key do
        if key < x.key then
            x := x.left
        else
            x := x.right
        end if
    repeat
    return x

Binary Search in Binary Search Trees

Find “8”

Tree-Search(x, key)
    while x ≠ NIL and key ≠ x.key do
        if key < x.key then
            x := x.left
        else
            x := x.right
        end if
    repeat
    return x

Binary Search in Binary Search Trees

Find “8”

Tree-Search(x, key)
    while x ≠ NIL and key ≠ x.key do
        if key < x.key then
            x := x.left
        else
            x := x.right
        end if
    repeat
    return x

Binary Search in Binary Search Trees

Find “8”

Tree-Search(x, key)
    while x ≠ NIL and key ≠ x.key do
        if key < x.key then
            x := x.left
        else
            x := x.right
        end if
    repeat
    return x

Binary Search in Binary Search Trees

Find “8”

Tree-Search(x, key)
    while x ≠ NIL and key ≠ x.key do
        if key < x.key then
            x := x.left
        else
            x := x.right
        end if
    repeat
    return x

Binary Search in Binary Search Trees

Find “8”

Tree-Search(x, key)
    while x ≠ NIL and key ≠ x.key do
        if key < x.key then
            x := x.left
        else
            x := x.right
        end if
    repeat
    return x

Binary Search in Binary Search Trees

By the way, the same procedure can be implemented using recursion:

Recursive-Tree-Search(x, key)
    if x = NIL or key = x.key then
        return x
    if key < x.key then
        return Recursive-Tree-Search(x.left, key)
    else
        return Recursive-Tree-Search(x.right, key)
    end if

Binary Search Trees: Obtaining the Minimum

In Binary Search Trees, finding the minimum is simple:

Binary Search Trees: Obtaining the Minimum

BST-Minimum(x)
     while x.left ≠ NIL do
         x := x.left
     repeat
     return x

Binary Search Trees: Obtaining the Minimum

BST-Minimum(x)
     while x.left ≠ NIL do
         x := x.left
     repeat
     return x

Binary Search Trees: Obtaining the Minimum

BST-Minimum(x)
     while x.left ≠ NIL do
         x := x.left
     repeat
     return x

Binary Search Trees: Obtaining the Minimum

BST-Minimum(x)
     while x.left ≠ NIL do
         x := x.left
     repeat
     return x

Binary Search Trees: Obtaining the Minimum

BST-Minimum(x)
     while x.left ≠ NIL do
         x := x.left
     repeat
     return x

Binary Search Trees: Insertion

New nodes are always inserted as leaf nodes.

Binary Search Trees: Insertion

Insert “20”

BST-Insert(T, z)
    y := NIL
    x := T.root
    while x ≠ NIL do
       y := x
       if z.key < x.key then
          x := x.left
       else
          x := x.right
       end if
   repeat
   z.parent := y
   if y = NIL then
      T.root := z
   else if z.key < y.key then
      y.left := z
   else
      y.right := z
   end if

Binary Search Trees: Insertion

Insert “20”

BST-Insert(T, z)
    y := NIL
    x := T.root
    while x ≠ NIL do
       y := x
       if z.key < x.key then
          x := x.left
       else
          x := x.right
       end if
   repeat
   z.parent := y
   if y = NIL then
      T.root := z
   else if z.key < y.key then
      y.left := z
   else
      y.right := z
   end if

Binary Search Trees: Insertion

Insert “20”

BST-Insert(T, z)
    y := NIL
    x := T.root
    while x ≠ NIL do
       y := x
       if z.key < x.key then
          x := x.left
       else
          x := x.right
       end if
   repeat
   z.parent := y
   if y = NIL then
      T.root := z
   else if z.key < y.key then
      y.left := z
   else
      y.right := z
   end if

Binary Search Trees: Insertion

Insert “20”

BST-Insert(T, z)
    y := NIL
    x := T.root
    while x ≠ NIL do
       y := x
       if z.key < x.key then
          x := x.left
       else
          x := x.right
       end if
   repeat
   z.parent := y
   if y = NIL then
      T.root := z
   else if z.key < y.key then
      y.left := z
   else
      y.right := z
   end if

Binary Search Trees: Insertion

Insert “20”

BST-Insert(T, z)
    y := NIL
    x := T.root
    while x ≠ NIL do
       y := x
       if z.key < x.key then
          x := x.left
       else
          x := x.right
       end if
   repeat
   z.parent := y
   if y = NIL then
      T.root := z
   else if z.key < y.key then
      y.left := z
   else
      y.right := z
   end if

Binary Search Trees: Insertion

Insert “20”

BST-Insert(T, z)
    y := NIL
    x := T.root
    while x ≠ NIL do
       y := x
       if z.key < x.key then
          x := x.left
       else
          x := x.right
       end if
   repeat
   z.parent := y
   if y = NIL then
      T.root := z
   else if z.key < y.key then
      y.left := z
   else
      y.right := z
   end if

Binary Search Trees: Deletion

Deletions from a binary search tree, case 1: deleting a leaf node

Binary Search Trees: Deletion

Deletions from a binary search tree, case 1: deleting a leaf node

Binary Search Trees: Deletion

Case 2: deleting a node with exactly one child

Binary Search Trees: Deletion

Case 2: deleting a node with exactly one child

Binary Search Trees: Deletion

Case 2: deleting a node with exactly one child

Binary Search Trees: Deletion

Case 3: deleting an element with two children.

Binary Search Trees: Deletion

Case 3 requires to reorganize the tree:

find the successor of the element
splice the successor out
replace the element by its successor

What is the successor and how can we find it?

Binary Search Trees: Successor

The successor of a node \(x \in V\): the smallest node greater than \(x\).

BST-Successor(x)
   if x.right ≠ NIL then
       return BST-Minimum(x.right)
   end if
   y := x.parent
   while y ≠ NIL and x = y.right do
       x := y
       y := y.parent
   repeat
   return y

Binary Search Trees: Successor

Either obtain the minimum from the subtree on the right.

BST-Successor(x)
   if x.right ≠ NIL then
       return BST-Minimum(x.right)
   end if
   y := x.parent
   while y ≠ NIL and x = y.right do
       x := y
       y := y.parent
   repeat
   return y

Binary Search Trees: Successor

In other cases, that is not as trivial:

BST-Successor(x)
   if x.right ≠ NIL then
       return BST-Minimum(x.right)
   end if
   y := x.parent
   while y ≠ NIL and x = y.right do
       x := y
       y := y.parent
   repeat
   return y

Binary Search Trees: Successor

BST-Successor(x)
   if x.right ≠ NIL then
       return BST-Minimum(x.right)
   end if
   y := x.parent
   while y ≠ NIL and x = y.right do
       x := y
       y := y.parent
   repeat
   return y

Binary Search Trees: Successor

BST-Successor(x)
   if x.right ≠ NIL then
       return BST-Minimum(x.right)
   end if
   y := x.parent
   while y ≠ NIL and x = y.right do
       x := y
       y := y.parent
   repeat
   return y

Binary Search Trees: Successor

BST-Successor(x)
   if x.right ≠ NIL then
       return BST-Minimum(x.right)
   end if
   y := x.parent
   while y ≠ NIL and x = y.right do
       x := y
       y := y.parent
   repeat
   return y

Binary Search Trees: Deletion

Now that we can find the successor reliably,
we can delete an inner element with two children:

Binary Search Trees: Deletion

BST-Delete(BST, z)
  if z.left = NIL then
      Shift-Nodes(BST, z, z.right)
  else if z.right = NIL then
      Shift-Nodes(BST, z, z.left)
  else
    y := BST-Successor(z)
    if y.parent ≠ z then
      Shift-Nodes(BST, y, y.right)
      y.right := z.right
      y.right.parent := y
    end if
    Shift-Nodes(BST, z, y)
    y.left := z.left
    y.left.parent := y
  end if

Shift-Nodes(BST, u, v)
  if u.parent = NIL then
    BST.root := v
  else if u = u.parent.left then
    u.parent.left := v
  else
    u.parent.right := v
  end if
  if v ≠ NIL then
    v.parent := u.parent
  end if

Comparison

Assume we have \(n\) elements and a tree with height \(h\)

Implementation	Search	Insert	Delete
sorted array	\(O( \log n)\)	\(O(n)\)	\(O(n)\)
unsorted list	\(O(n)\)	\(O(1)\)	\(O(n)\)
binary search tree	\(O(h)\)	\(O(h)\)	\(O(h)\)

Summary

Some observations:

height of a tree \(h\) is more important than its size
in a balanced tree, we have \(h = \log_2 n\)
if we insert elements that are already sorted, and without rebalancing, the height of the tree may grow the same as \(O(n)\)
there are self-balancing binary search trees like 2-3 trees, AVL trees, Red-black trees…

Modeling Binary Search Trees

With all the conceptual advantages of trees,
how are they actually modelled in programs?

Modeling Binary Search Trees

With a lot of pointers…

Thanks

mirco.schoenfeld@uni-bayreuth.de

https://xkcd.com/835/

Acknowledgement

Acknowledgement:

This script is inspired by Tantau (2016) and Räcke (2019, 2021).

References

Räcke, Harald. 2019. “Lecture Notes to the Lecture Algorithmen und Datenstrukturen.” TUM. https://wwwalbers.in.tum.de/lehre/2019SS/ad/index.html.de.

———. 2021. “Lecture Notes to the Lecture Intro to Linear Programming.” TUM. http://www14.in.tum.de/lehre/2021WS/ea/.

Tantau, Till. 2016. Einführung in Die Informatik. Online. https://www.tcs.uni-luebeck.de/de/mitarbeiter/tantau/lehre/lectures/EinfuehrungindieInformatik-2016.pdf.