Notes from CS2040S Week 4 Lecture 2 on Trees

CS2040S_w4l2.md

CS2040S Week 4 Lecture 2

Notes from CS2040S Week 4 Lecture 2 on Trees

Dictionary

A collection of (key, value) pairs

interface	IDictionary

void		insert
Value		search
Key 		successor
Key 		predecessor
void 		delete
boolean 	contains
int 		size

We can implement dictionaries using arrays, vectors, queues, linked lists, or Java libraries like ArrayList.

Trees

Trees are a form of graph with nodes and edges (branches). The nodes contain values. The first node is called the root. Nodes at the same level are called siblings. Nodes under nodes are called child nodes while those nodes above are called parents. Nodes with no children are called leaves. Nodes have left and right branches.

// using trees as dictionaries
public class BinaryTree {
	private TreeNode left;
	private TreeNode right;
	
	private int key;
	private int value;

	// remainder of BT implementation
}

Binary Search Trees

All in left subtree < key < all in right subtree.

Height of Trees

Number of nodes between root node and the deepest/bottommost node.

h(v) = 0 if v is a leaf
h(v) = max(h(v.left), h(v.right)) + 1

Inserting into Trees

For every new item `x`, check if `x` is less than or greater than the root. If less than, move left and repeat until a leaf is found. Same with the right side. The shape of a tree is determined by the order of insertion.

The number of ways to order insertions is n! and the shapes of binary trees is ~4^n called the Catalan Numbers.

Searching Trees

The worst-case runtime for BSTs is O(n) when all elements are on the right of one another:

11
  20
    29
      41
        65

Tree Traversal

• In-order: left + key + right
• Pre-order: key + left + right
• Post-order: left + right + key
• Level-order: per level (uses queue)

Successor

If item not in tree, we'll either find predecessor or successor. Works from time to time. To get the successor,

1. Search for key in tree
2. If (result > key), return result
3. If (result < key), search for successor of result

Predecessor

1. Search for key in tree
2. If (result < key), return result
3. If (result > key), search for predecessor of result