# Trees

## Overview

A tree is a acyclic connected graph.

Conventional tree operations are insert, search, remove, and traverse.

Tree's usually have a designated *root* that indicates the top of
the tree. *Leaves* refer to nodes with no children. A *parent* is
the node above the current one. A *child* is the node below the
current one.

### Properties

A tree is *balanced* when every path from root to leaf has the same
length.

## Binary Search Trees

In a **binary tree**, each node contains one element and has at most
two child nodes.A **binary search tree** (BST) is a binary tree with
the following requirements:

- ∀ y ∈ left subtree of x, y ≤ x
- ∀ y ∈ right subtree of x, y ≥ x

Operation | Best Complexity | Worst Complexity |
---|---|---|

Insert | \(O(\log n)\) | \(O(n)\) |

Search | \(O(\log n)\) | \(O(n)\) |

Delete | \(O(\log n)\) | \(O(n)\) |

A binary search tree is **complete** if every node has zero or two
children and all leaves are at the same level.

The shape of the binary search tree depends entirely on the order of insertions and deletions, and can become degenerate. A skewed binary tree can greatly affect performance.

## Self-Balancing Binary Search Trees

Examples include:

- AVL trees
- Red-black trees