# Trees

• A tree is an abstract model of a heirarchical structure
• A tree consists of nodes with a parent-child relationship
• A parent has one or more children
• Each child has only one parent
• The root is the top node in the tree, the only node without a parent
• An internal node has at least one child
• An external node (or leaf) is a mode with no children
• Nodes have ancestors (ie, the parent node of a parent)
• The depth of a node is its number of ancestors
• The height of a tree is its maximum depth

Tree ADTs are defined using a similar concept to positional lists, as they don't have a natural ordering/indexing in the same way arrays do.

public interface Tree<E>{
int size();
boolean isEmpty();
Node<E> root(); //returns root node
Node<E> parent(Node<E> n); //returns parent of Node n
Iterable<Node<E>> children(Node<E> n); //collection of all the children of Node n
int numChildren(Node<E> n);
Iterator<E> iterator(); //an iterator over the trees elements
Iterator<Node<E>> nodes(); //collection of all the nodes
boolean isInternal(Node<E> n); //does the node have at least one child
boolean isExternal(Node<E> n); //does the node have no children
boolean isRoot(Node<E> n); //is the node the root

}


## Tree Traversal

Trees can be traversed in 3 different orders. As trees are recursive data structures, all 3 traversals are defined recursively. The tree below is used as an example in all 3 cases.

### Pre-order

• Visit the root
• Pre order traverse the left subtree
• Pre order traverse the right subtree

Pre-order traversal of the tree gives: F B A D C E G I H

### In-order

• In order traverse the left subtree
• Visit the root
• In order traverse the right subtree

In-order traversal of the tree gives: A B C D E F G H I

### Post-order

• Post order traverse the left subtree
• Post order traverse the right subtree
• Visit the root

Post-order traversal of the tree gives: A C E D B H I G F

## Binary Trees

A binary tree is a special case of a tree:

• Each node has at most two children (either 0, 1 or 2)
• The children of the node are an ordered pair (the left node is less than the right node)

A binary tree will always fulfil the following properties:

Where:

• is the number of nodes in the tree
• is the number of external nodes
• is the number of internal nodes
• is the height/max depth of the tree

The binary tree ADT is an extension of the normal tree ADT with extra accessor methods.

public interface BinaryTree<E> extends Tree<E>{
Node<E> left(Node<E> n); //returns the left child of n
Node<E> right(Node<E> n); //returns the right child of n
Node<E> sibling(Node<E> n); //returns the sibling of n
}


### Arithmetic Expression Trees

Binary trees can be used to represent arithmetic expressions, with internal nodes as operators and external nodes as operands. The tree below shows the expression . Traversing the tree in-order will can be used to print the expression infix, and post-order evaluating each node with it's children as the operand will return the value of the expression.

### Implementations

• Binary trees can be represented in a linked structure, similar to a linked list
• Node objects are positions in a tree, the same as positions in a positional list
• Each node is represented by an object that stores
• The element
• A pointer to the parent node
• A pointer to the left child node
• A pointer to the right child node
• Alternatively, the tree can be stored in an array A
• A[root] is 0
• If p is the left child of q, A[p] = 2 * A[q] + 1
• If p is the right child of q, A[p] = 2 * A[q] + 2
• In the worst, case the array will have size

## Binary Search Trees

• Binary trees can be used to implement a sorted map
• Items are stored in order by their keys
• For a node with key , every key in the left subtree is less than , and every node in the right subtree is greater than
• This allows for support of nearest-neighbour queries, so can fetch the key above or below another key
• Binary search can perform nearest neighbour queries on an ordered map to find a key in time
• A search table is an ordered map implemented using a sorted sequence
• Searches take
• Insertion and removal take time
• Only effective for maps of small size

### Methods

Binary trees are recursively defined, so all the methods operating on them are easily defined recursively also.

• Search
• To search for a key
• Compare it with the key at
• If , the value has been found
• If , search the right subtree
• If , search the left subtree
• Insertion
• Search for the key being inserted
• Insert at the leaf reached by the search
• Deletion
• Find the internal node that is follows the key being inserted in an in order traversal (the in order successor)
• Copy key into the in order successor node
• Remove the node copied out of

### Performance

• Consider a binary search tree with items and height
• The space used is
• The methods get, put, remove take time
• The height h is in the best case, when the tree is perfectly balanced
• In the worst case, when the tree is basically just a linked list, this decays to

## AVL Trees

• AVL trees are balanced binary trees
• For every internal node of the tree, the heights of the subtrees of can differ by at most 1
• The height of an AVL tree storing keys is
• Balance is maintained by rotating nodes every time a new one is inserted/removed

### Performance

• The runtime of a single rotation is
• The tree is assured to always have , so the runtime of all methods is
• This makes AVL trees an efficient implementation of binary trees, as their performance does not decay as the tree becomes unbalanced