Trees

Contents

• Dictionary ADT
• General Trees
• Binary Trees
• Binary Search Trees
• Balanced Search Trees
  • (2,4)-Trees
  • B Trees

Dictionary ADT

Dictionary ADT represents a collection of items, where each item can be a key or a (key, value) pair.

ADT	Item	Ordered?	Duplicates?	Implementation
Set	key	✗	✗	Hash table
Sorted set	key	✓	✗	Balanced tree
Multiset	key	✗	✓	Hash table
Sorted multiset	key	✓	✓	Balanced tree
Map	(key, value)	✗	✗	Hash table
Sorted map	(key, value)	✓	✗	Balanced tree
Multimap	(key, value)	✗	✓	Hash table
Sorted multimap	(key, value)	✓	✓	Balanced tree

Map

A map is a collection of key-value pairs (k, v), where keys are unique.

Key	Value
Dictionary word	Word meaning
User ID	User record
Employee ID	Employee record
Student ID	Student record
Patient ID	Patient record
Profile ID	Person details
Order ID	Order details
Transaction ID	Transaction details
URL	Web page
Full file name	File

Set ADT (java.util.Set interface)

Method	Functionality
add(e)	Adds the element e to S if it is not already present.
remove(e)	Removes the element e from S if it is present.
contains(e)	Returns whether e is an element of S.
iterator()	Returns an iterator of the elements of S.
addAll(T)	Updates S to also include all elements of set T, effectively replacing S by S ∪ T.
retainAll(T)	Updates S so that it only keeps those elements that are also elements of set T, effectively replacing S by S ∩ T.
removeAll(T)	Updates S by removing any of its elements that also occur in set T, effectively replacing S by S − T.

• Set = unordered set; Map = unordered map.
  java.util.HashSet is an implementation of the set ADT.
  java.util.HashMap is an implementation of the map ADT.

Sorted set ADT (java.util.SortedSet interface)

Method	Functionality
first()	Returns the smallest element in S.
last()	Returns the largest element in S.
ceiling(e)	Returns the smallest element ≥ e.
floor(e)	Returns the largest element ≤ e.
lower(e)	Returns the largest element < e.
higher(e)	Returns the smallest element > e.
subSet(e1,e2)	Returns an iteration of all elements greater than or equal to e1, but strictly less than e2.
pollFirst()	Returns and removes the smallest element in S.
pollLast()	Returns and removes the largest element in S.

• java.util.TreeSet is an implementation of the sorted set ADT.
  java.util.TreeMap is an implementation of the sorted map ADT.
• TreeSet and TreeMap use balanced search trees.

Multiset ADT

Method	Functionality
add(e)	Adds a single occurrence of e to the multiset.
contains(e)	Returns true if the multiset contains an element equal to e.
count(e)	Returns the number of occurrences of e in the multiset.
remove(e)	Removes a single occurrence of e from the multiset.
remove(e, n)	Removes n occurrences of e from the multiset.
size()	Returns the number of elements of the multiset (including duplicates).
iterator()	Returns an iteration of all elements of the multiset (repeating those with multiplicity greater than one).

• Java does not include any form of a multiset.
  Guava = Google Core Libraries for Java.
  Guava's Multiset is an implementation of the multiset ADT.
  Guava's Multimap is an implementation of the multimap ADT.
• Similarly, one can define a sorted multiset ADT.

Dictionary operations (for unique keys)

	Worst case			Average case
Data structure	Search	Insert	Delete	Search	Insert	Delete
Sorted array	$\Theta(\log n)$	$\Theta(n)$	$\Theta(n)$	$\Theta(\log n)$	$\Theta(n)$	$\Theta(n)$
Unsorted list	$\Theta(n)$	$\Theta(1)$	$\Theta(n)$	$\Theta(n)$	$\Theta(1)$	$\Theta(n)$
Hashing	$\Theta(n)$	$\Theta(n)$	$\Theta(n)$	$\Theta(1)^*$	$\Theta(1)^*$	$\Theta(1)^*$
BST	$\Theta(n)$	$\Theta(n)$	$\Theta(n)$	$\Theta(\log n)$	$\Theta(\log n)$	$\Theta(\log n)$
Splay tree	$\Theta(\log n)^*$	$\Theta(\log n)^*$	$\Theta(\log n)^*$	$\Theta(\log n)^*$	$\Theta(\log n)^*$	$\Theta(\log n)^*$
Scapegoat tree	$\Theta(\log n)$	$\Theta(\log n)^*$	$\Theta(\log n)^*$	$\Theta(\log n)$	$\Theta(\log n)$	$\Theta(\log n)$
AVL tree	$\Theta(\log n)$	$\Theta(\log n)$	$\Theta(\log n)$	$\Theta(\log n)$	$\Theta(\log n)$	$\Theta(\log n)$
Red-black tree	$\Theta(\log n)$	$\Theta(\log n)$	$\Theta(\log n)$	$\Theta(\log n)$	$\Theta(\log n)$	$\Theta(\log n)$
AA tree	$\Theta(\log n)$	$\Theta(\log n)$	$\Theta(\log n)$	$\Theta(\log n)$	$\Theta(\log n)$	$\Theta(\log n)$
(a,b)-tree	$\Theta(\log n)$	$\Theta(\log n)$	$\Theta(\log n)$	$\Theta(\log n)$	$\Theta(\log n)$	$\Theta(\log n)$
B-tree	$\Theta(\log n)$	$\Theta(\log n)$	$\Theta(\log n)$	$\Theta(\log n)$	$\Theta(\log n)$	$\Theta(\log n)$

* = Amortized

General Trees

Family tree

Company organization tree

File system tree

Book organization tree

Terminology

Term	Meaning
Tree	ADT that stores elements hierarchically
Parent node	Immediate previous-level node
Child nodes	Immediate next-level nodes
Root node	Top node of the tree
Sibling nodes	Nodes that are children of the same parent
External nodes	Nodes without children
Internal nodes	Nodes with one or more children
Ancestor node	Parent node or ancestor of parent node
Descendent node	Child node or descendent of child node
Subtree	Tree consisting of the node and its descendants
Edge	Pair of nodes denoting a parent-child relation
Path	Pair of nodes denoting an ancestor-descendant relation
Ordered tree	Tree with a meaningful linear order among child nodes

Terminology

Binary Trees

A binary tree is an ordered tree with the following properties:

1. Every node has at most two children.
2. Each child node is labeled as a left child or a right child.
3. A left child precedes a right child in the order of children.

A recursive definition of the binary tree:

• An empty tree.
• A nonempty tree having a root node $r$, which stores an element, and two binary trees that are respectively the left and right subtrees of $r$.

Decision tree

Arithmetic expression tree

Tree represents $((((3+1)*3)/((9-5)+2))-((3*(7-4))+6))$.

Terminology

Term	Meaning
Left subtree	Subtree rooted at the left child of an internal node
Right subtree	Subtree rooted at the right child of an internal node
Proper/full tree	A tree in which every node has either 0 or 2 children
Complete tree	Tree in which all except possibly the last level is completely filled and the nodes in the last level are as far left as possible
Perfect tree	Complete tree in which the last level is completely filled

Tree examples

Binary ✓, Proper ✗, Complete ✗, Perfect ✗

Binary ✓, Proper ✓, Complete ✗, Perfect ✗

Binary ✓, Proper ✓, Complete ✗, Perfect ✗

Binary ✓, Proper ✗, Complete ✓, Perfect ✗

Binary ✓, Proper ✓, Complete ✓, Perfect ✗

Binary ✓, Proper ✓, Complete ✓, Perfect ✓

Levels and maximum number of nodes

Properties of binary tree

Let

• $T =$ nonempty binary tree
• $n_{\text{external}} =$ number of external nodes
• $n_{\text{internal}} =$ number of internal nodes
• $n = n_{\text{external}} + n_{\text{internal}}$
• $d_{\text{max}} =$ maximum depth of the tree

Then

• $d_{\text{max}} + 1 \le n \le 2^{d_{\text{max}} + 1} - 1$
• $1 \le n_{\text{external}} \le 2^{d_{\text{max}}}$
• $d_{\text{max}} \le n_{\text{internal}} \le 2^{d_{\text{max}}} - 1$
• $\log(n + 1) - 1 \le d_{\text{max}} \le n - 1$

Properties of proper binary tree

If $T$ is a proper nonempty binary tree,

• $2d_{\text{max}} + 1 \le n \le 2^{d_{\text{max}} + 1} - 1$
• $d_{\text{max}} + 1 \le n_{\text{external}} \le 2^{d_{\text{max}}}$
• $d_{\text{max}} \le n_{\text{internal}} \le 2^{d_{\text{max}}} - 1$
• $\log(n + 1) - 1 \le d_{\text{max}} \le (n - 1)/2$
• $n_{\text{external}} = n_{\text{internal}} + 1$

Implementing a binary tree using linked structure

Implementing a binary tree using array

Implementing a binary tree using array

Implementing a binary tree using array

• Level numbering or level ordering
  Let $p =$ a node of tree and $f(p) =$ index of node $p$
  Let $q =$ parent of $p$ and $f(q) =$ index of node $q$

$$ f(p) = \begin{cases} 0 & \text{if $p$ is the root} \\ 2f(q) + 1 & \text{if $p$ is the left child of position $q$} \\ 2f(q) + 2 & \text{if $p$ is the right child of position $q$} \end{cases} $$

• Then, node $p$ will be stored at index $f(p)$ in the array.
• $0 \le f(p) < 2^n - 1$, where $n =$ number of levels in the tree.

Implementing a general tree using linked structure

Tree traversals

• A traversal of a tree $T$ is a systematic way of accessing or visiting all the nodes of $T$.

Traversal	Binary tree?	General tree?
Preorder traversal	✓	✓
Inorder traversal	✓	✗
Postorder traversal	✓	✓
Breadth-first traversal	✓	✓

Preorder / inorder / postorder traversals

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{PreorderTraversal}{$root$}
    \IF{$root \ne null$}
        \STATE \CALL{Visit}{$root$}
        \STATE \CALL{PreorderTraversal}{$root.left$}
        \STATE \CALL{PreorderTraversal}{$root.right$}
    \ENDIF
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{InorderTraversal}{$root$}
    \IF{$root \ne null$}
        \STATE \CALL{InorderTraversal}{$root.left$}
        \STATE \CALL{Visit}{$root$}
        \STATE \CALL{InorderTraversal}{$root.right$}
    \ENDIF
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{PostorderTraversal}{$root$}
    \IF{$root \ne null$}
        \STATE \CALL{PostorderTraversal}{$root.left$}
        \STATE \CALL{PostorderTraversal}{$root.right$}
        \STATE \CALL{Visit}{$root$}
    \ENDIF
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

• Preorder traversal = A B C
• Inorder traversal = B A C
• Postorder traversal = B C A

• Preorder traversal = A [left] [right] = A B D E C F G
• Inorder traversal = [left] A [right] = D B E A F C G
• Postorder traversal = [left] [right] A = D E B F G C A

Preorder traversal

Preorder traversal: Table of contents

Postorder traversal

Postorder traversal: Compute disk space

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{ComputeDiskSpace}{$root$}
    \STATE $space \gets root.key$
    \FORALL{child $child$ of $root$ node}
        \STATE $space \gets space +$ \CALL{ComputeDiskSpace}{$root.child$}
    \ENDFOR
    \RETURN $space$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Inorder traversal: Arithmetic expression

$(((3+1) \times 3) / ((9-5) + 2)) - ((3 \times (7-4)) + 6)$

Breadth-first traversal: Game trees

Breadth-first traversal

General tree.

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{BreadthFirstTraversal}{$root$}
    \STATE $Q$.Enqueue($root$)
    \WHILE{$Q$ is not empty}
        \STATE $curr \gets Q$.Dequeue$()$
        \STATE \CALL{Visit}{$curr$}
        \FORALL{child $child$ of $curr$ node}
            \STATE $Q$.Enqueue$(curr.child)$
        \ENDFOR
    \ENDWHILE
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Binary tree.

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{BreadthFirstTraversal}{$root$}
    \STATE $Q$.Enqueue($root$)
    \WHILE{$Q$ is not empty}
        \STATE $curr \gets Q$.Dequeue$()$
        \STATE \CALL{Visit}{$curr$}
        \IF{$curr.left \ne null$}
            \STATE $Q$.Enqueue$(curr.left)$
        \ENDIF
        \IF{$curr.right \ne null$}
            \STATE $Q$.Enqueue$(curr.right)$
        \ENDIF
    \ENDWHILE
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Binary Search Trees (BST)

Binary search tree (BST)

A binary search tree is a binary tree $T$ such that, for each internal node $p$ of $T$:

• Node $p$ stores an element, say $p.key$.
• Keys stored in the left subtree of $p$ are less than $p.key$.
• Keys stored in the right subtree of $p$ are greater than $p.key$.

Binary search tree node

class Node<T>
{
    T key;
    Node<T> left;
    Node<T> right;

    Node(T item, Node<T> lchild, Node<T> rchild)
    { key = item; left = lchild; right = rchild; }

    Node(T item)
    { this(item, null, null); }
}

Search: 65 exists

Search: 68 does not exist

Search: Recursive algorithm

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{Search}{$curr, target$}
    \IF{$curr = null$}
        \RETURN $curr$ \COMMENT{unsuccessful search}
    \ENDIF
    \IF{$target < curr.key$}
        \RETURN \CALL{Search}{$curr.left, target$} \COMMENT{recur on left subtree}
    \ENDIF
    \IF{$target > curr.key$}
        \RETURN \CALL{Search}{$curr.right, target$} \COMMENT{recur on right subtree}
    \ENDIF
    \IF{$target = curr.key$}
        \RETURN $curr$ \COMMENT{successful search}
    \ENDIF
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Search: Non-recursive algorithm

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{Search}{$curr, target$}
    \WHILE{$curr \ne null$}
        \IF{$target < curr.key$}
            \STATE $curr \gets curr.left$ \COMMENT{recur on left subtree}
        \ELSIF{$target > curr.key$}
            \STATE $curr \gets curr.right$ \COMMENT{recur on right subtree}
        \ELSIF{$target = curr.key$}
            \RETURN $curr$ \COMMENT{successful search}
        \ENDIF
    \ENDWHILE
    \RETURN $null$ \COMMENT{unsuccessful search}
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Search: Analysis

$\text{Time} = O(h) = O(n)$

Add 68

Add: Recursive algorithm

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{Add}{$curr, item$}
    \IF{$curr = null$}
        \STATE $curr \gets$ Node$(item)$ \COMMENT{item does not exist}
    \ELSIF{$curr \ne null$}
        \IF{$item < curr.key$}
            \STATE $curr.left \gets$ \CALL{Add}{$curr.left, item$} \COMMENT{recur on left subtree}
        \ELSIF{$item > curr.key$}
            \STATE $curr.right \gets$ \CALL{Add}{$curr.right, item$} \COMMENT{recur on right subtree}
        \ELSIF{$item = curr.key$}
            \STATE do nothing \COMMENT{item exists}
        \ENDIF
    \ENDIF

    \RETURN $curr$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Add: Non-recursive algorithm

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{Add}{$curr, item$}
    \STATE $parent \gets null$
    \WHILE{$curr \ne null$}
        \STATE $parent \gets curr$
        \IF{$item < curr.key$}
            \STATE $curr \gets curr.left$ \COMMENT{recur on left subtree}
        \ELSIF{$item > curr.key$}
            \STATE $curr \gets curr.right$ \COMMENT{recur on right subtree}
        \ELSIF{$item = curr.key$}
            \RETURN $curr$ \COMMENT{item exists}
        \ENDIF
    \ENDWHILE

    \STATE $curr \gets$ Node$(item)$ \COMMENT{item does not exist}
    \IF{$parent \ne null$}
        \IF{$item < parent.key$}
            \STATE $parent.left \gets curr$
        \ENDIF
        \IF{$item > parent.key$}
            \STATE $parent.right \gets curr$
        \ENDIF
    \ENDIF

    \RETURN $curr$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Add: Analysis

$\text{Time} = O(h) = O(n)$

Remove 32: Node 32 has one child

Remove 88: Node 88 has two children

Remove

Removing a node (with a particular key) has four cases:

1. Node is not found.
   Do nothing.
2. Node is found and it has 0 nonempty children.
   Remove the node.
3. Node is found and it has 1 nonempty child.
   Remove the node.
   Its nonempty child will take the location of the node.
4. Node is found and it has 2 nonempty children.
   Locate the predecessor of the node.
   Predecessor = curr.left.right.right........right
   Predecessor will take the location of the node.
   Predecessor's left child will take the location of the predecessor.
   (Can we use successor instead of predecessor?)

Remove: Recursive algorithm

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{Remove}{$curr, item$}
    \IF{$curr = null$}
        \STATE do nothing \COMMENT{item does not exist}
    \ELSIF{$item < curr.key$}
        \STATE $curr.left \gets$ \CALL{Remove}{$curr.left, item$} \COMMENT{recur on left}
    \ELSIF{$item > curr.key$}
        \STATE $curr.right \gets$ \CALL{Remove}{$curr.right, item$} \COMMENT{recur on right}
    \ELSE
        \IF{$curr.left = null$}
            \STATE $curr \gets curr.right$ \COMMENT{0 or 1 child}
        \ELSIF{$curr.right = null$}
            \STATE $curr \gets curr.left$ \COMMENT{1 child}
        \ELSE
            \STATE $curr.key \gets$ \CALL{Maximum}{$curr.left$}.key \COMMENT{find predecessor}
            \STATE $curr.left \gets$ \CALL{Remove}{$curr.left, curr.key$} \COMMENT{remove predecessor}
        \ENDIF
    \ENDIF

    \RETURN $curr$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Remove: Non-recursive algorithm

Remove: Analysis

$\text{Runtime} = O(h) = O(n)$

Balanced Search Trees

Balanced search trees: Motivation

Data structure	Search	Add	Remove
Binary search tree	$O(n)$	$O(n)$	$O(n)$
Balanced search tree	$O(\log n)$	$O(\log n)$	$O(\log n)$

(2,4)-trees

• A (2,4)-tree or 2-3-4 tree is a balanced search tree.
• A (2,4)-tree satisfies two properties:
  1. Size property. Every non-empty node has 2, 3, or 4 children.
  2. Depth property. All empty nodes have the same depth.

There are three types of non-empty nodes:

• 2-nodes have 2 children and 1 key. e.g.: [11], [12], [15], [17]
• 3-nodes have 3 children and 2 keys. e.g.: [3 4], [5 10], [13 14]
• 4-nodes have 4 children and 3 keys. e.g.: [6 7 8]

Search: 24 exists

Search: 12 does not exist

Add 17

Size and depth properties are satisfied.

Overflow: Size property is violated at [13 14 15 17].

Size property at [13 14 15 17] will be fixed via split operation.

Overflow: Size property is violated at [5 10 12 15].

Size property at [5 10 12 15] will be fixed via split operation.

Size and depth properties are satisfied.

Add: Node split

Add 4, 6, 12, 15

Add 3, 5

Add 10, 8

Remove 4

Underflow: Size property is violated is [4].

Size property will be fixed via transfer operation.

Remove 12

Underflow: Size property is violated is [12], which has non-empty children. It will be fixed via swap with predecessor.

Underflow: Size property is violated is [11].

Size property will be fixed via fusion operation.

Remove 13

Remove

$n_e =$ node with empty children

$n_{\ne e} =$ node with non-empty children

$s_{3,4} =$ immediate sibling of $n_e$ is a 3-node or a 4-node

$s_2 =$ immediate sibling of $n_e$ is a 2-node

$p =$ parent of $n_e$

• Removal of $n_{\ne e}$ can always be reduced to $n_e$
• Suppose removed node is:
  1. $n_{\ne e}$.
     Swap with the $n_e$ predecessor
  2. $n_e$ and $s_{3,4}$ exists.
     Transfer a child and key of $s_{3,4}$ to $p$ and a key of $p$ to $n_e$.
  3. $n_e$ and $s_{3,4}$ does not exist.
     Fuse/merge $n_e$ with $s_2$ to get $n_e'$. Move key from $p$ to $n_e'$.

(2,4)-trees: Complexity

Method	Running time
Search	$O(\log n)$
Add	$O(\log n)$
Remove	$O(\log n)$

B Trees

Computer memory

Cache-efficient algorithms: Example

Cache data locality

An algorithm must have the following two features in order to make good use of cache.

1. Spatial data locality
2. Temporal data locality

Spatial data locality:

• Meaning?
  Whenever a cache block is brought into the cache, it contains as much useful data as possible.
• How to exploit?
  Group data in blocks (or pages). Move data in blocks.

Temporal data locality:

• Meaning?
  Whenever a cache block is brought into the cache, as much useful work as possible is performed on this data before removing the block from the cache.
• Necessary condition?
  Total computations is asymptotically greater than space
  i.e., $T(n) \in \omega(S(n))$
• How to exploit?
  Design recursive divide-and-conquer algorithms

Cache complexity

• Cache complexity is the asymptotic number of cache misses or page faults incurred by an algorithm.
• Cache-efficient algorithms incur fewer cache misses.
• Cache-efficient algorithms try to exploit both spatial and temporal data locality.
• Terminology: $B$ = data block size, $M$ = cache size

Cache-efficient algorithms

Problem	Cache-inefficient algorithm	Cache-efficient algorithm
Sorting	Merge sort $O(n \log n)$	Ext-memory merge sort $O(\frac{n}{B}\log_{\frac{M}{B}}\frac{n}{B})$
Balanced tree	(2,4)-tree $O(\log n)$	B tree $O(\log_B n)$
Matrix product	Iterative $O(n^3)$	Recursive D&C $O(\frac{n^3}{B\sqrt{M}})$

$(a, b)$-trees

• $(a, b)$-tree is a straightforward generalization of (2,4)-tree in which the complexities depend on $a$ and $b$.
• By choosing proper values for $a$ and $b$, we get a balanced search tree that has excellent external-memory performance.
• (a, b)-tree is a multiway search tree such that each node has between $a$ and $b$ children and stores between $a-1$ and $b-1$ entries.

• An $(a,b)$-tree is a balanced multiway search tree.
• An $(a,b)$-tree satisfies three properties:

1. $2 \le a \le (b+1)/2$
2. Size property. Every non-empty node has children in the range $[a, b]$.
3. Depth property. All empty nodes have the same depth.

B trees

• B tree of order $d$ is an $(a, b)$ tree with $a = \lceil d/2 \rceil$ and $b = d$.
• B trees are analyzed for cache complexity.
• B trees are cache-efficient when $d = B$, as they exploit spatial data locality.

B trees: Complexity

	(2,4)-tree		B tree
Method	Communication	Computation	Communication	Computation
Search	$O(\log n)$	$O(\log n)$	$O(\log_B n)$	$O(\log n)$
Add	$O(\log n)$	$O(\log n)$	$O(\log_B n)$	$O(\log n)$
Remove	$O(\log n)$	$O(\log n)$	$O(\log_B n)$	$O(\log n)$

Applications

B trees (and variants such as B+ trees, B* trees, B# trees) are used for file systems and databases.

• Microsoft: NTFS
• Mac: HFS, HFS+
• Linux: BTRFS, EXT4, JFS2
• Databases: Oracle, DB2, Ingres, SQL, PostgreSQL