# Trees

**Depth**of a node: the length (no. of edges) of the branch to the root**Height**of a tree: the maximal depth (no. of layers - 1)**Perfect**tree: when all leaves are on the same*depth h*, there are $2^{h+1} - 1$ nodes which all all reachable in $h$ steps**Complete $n$-tree**: each vertex except for for the leafs has $n$ children, in total $\geq 2^h$ nodes (no gaps in array representation)**Binary tree**: every node has at most two children**Balenced**binary tree: the left and right subtrees of every node differ in height by no more than 1- #edges = #nodes - 1 (because every node execpt for the root has an edge to its parent)

## Tree traversal #

On a binary tree, in which: Node (N), Left (L), Right (R):

- Preorder (NLR)
- Postorder (LRN)
- Inorder (LNR)

## Expression trees #

In prefix notation:

- Operator before argumentens
- Never needs parentheses!
- Corresponds to preorder traversal

In infix notation:

- The 'usual' way of notating math
- Corresponds to
*inorder traversal*

## Tries #

A **standard trie** $T$ on a collection of words $W$, is a tree with the following properties:

- The root of T is empty, and every other node contains a letter
- The children of a node T contains different letters and are in alphabetical order
- The branches in T from the root correspond exactly with the words in W

**Compressed trie**: strings are concatenated

**Compact trie**: nodes store range of indicies referencing positions in word

Let $n$ be the sum of lengths of the words and $m$ be the number of words:

Trie | Number of nodes | Memory use |
---|---|---|

Standard trie | ${O}(n)$ | ${O}(n)$ |

Compressed trie | ${O}(m)$ | ${O}(n)$ |

Compact trie | ${O}(m)$ | ${O}(m)$ |

**Suffix trie**: store only suffixes of substrings since *every substring of a string is the prefix of a suffix*.

The childs of a Trie can either be implemented has an array or a list. Depending on the sparseness of your Trie either implementation can be more memory efficient. However the lookup times for entries in a linked list are slower because the list has to be traversed.

## Heaps #

- Heap property:
*for each node v, its descendants have a value that is smaller or equal than the value of v*. `enqueue`

/`removeMax`

in $O(\lg(n))$- Restoring heap property by:
`upheap`

: keep swapping with parent until heap property is maintained.`downheap`

: move node down until it is smaller than its ancestors.

- A heap is efficiently implemented as an array. Since the heap is a complete tree there will be no gaps.

Building a heap is $O(n)$ since the time varies with height of node:

```
algorithm buildMaxHeap(a, n):
for i in n/2 .. 1
fix heap order
```

Invariant: starts with the leaf nodes as heap, each node is the root of the new heap.

**Heapsort**: First, construct a max heap in ${O}(n)$ and then keep extracting max element in $O(\lg n)$. Hence the total time complexity is $O(n \lg n)$.

Note that heapsort is not stable.

## Binary Search trees (BSTs) #

Search tree property: if $x$ in node $k$ then:

- Everything in the left subtree of $k$ is smaller than $x$
- Everything in the right subtree of $k$ is greater than $x$

Operations: `search`

, `add`

, `remove`

are in ${O}(h)$ where $h$ is the height of the tree $(\lg n)$

Runtimes of BSTs are linear if they are not balanced. Hence, there are several **self-balancing BSTs** that balance themselves so that the operations stay logarithmic:

- AVL Trees
- Red-Black trees
- Treaps

### Rotations #

Rearranges subtrees with the goal to minimize the height of a tree while remaining ordered $O(1)$.

### Red-Black tree #

Properties:

- Every node is red or black
- The root is black
- Every leaf is black
- If a node is red, both is children are black
- All simple paths contain the same number of black nodes

Insertion: First, insert a node in color red. Then, recolor and rotate nodes to fix the properties.