> For the complete documentation index, see [llms.txt](https://cs-notes.gitbook.io/algorithm-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs-notes.gitbook.io/algorithm-notes/outline/overview-4.md).

# Tree

When talking about [Tree](/algorithm-notes/outline/overview-4.md#tree) data structure, we normally omit the term ***free*** that a *free tree* is an acyclic, connected, undirected [graph](broken://pages/-LRtesR0DJ4n-523mHQr). And a possibly disconnected acyclic undirected graph is *forest*.

Theorem. 1. A *G = (V, E)* is an undirected graph, then

1. *G* is a *free tree*.
2. any two vertices in *G* are connected through a single path.
3. *G* is connected, but removing an edge will result in a disconnected graph.
4. *G* is connected, acyclic and |*E*| = |*V*| - 1.
5. if adding any single edge to |*E*| will cause the graph to form a cycle.

## Rooted Tree and Ordered Tree

A [Rooted Tree](/algorithm-notes/outline/overview-4.md#rooted-tree-and-ordered-tree) is a *free tree* that has a virtual topmost node distinguishable from others which called the *root* of the tree.

The children of a tree node is called the *descendant* of that node and every children call their parent node the *ancestor*. Child nodes under the same node call each other *siblings* and node with no children is called *leaf* (external node), a non-leaf node is *internal node*.

The length of a path from *root* of a tree to a node x is the ***depth*** of x in the tree (the ***depth*** of *root* is 0). The ***height*** of a node in a tree is the value of longest path leading from that node to a leaf in the tree; it generalizes to a formula for computing:

𝒽(x) = max( 𝒽(*left subtree of x*), 𝒽(*right subtree of x*)) + 1

An [ordered tree](/algorithm-notes/outline/overview-4.md#rooted-tree-and-ordered-tree) is a rooted tree in which children of each node are ordered. e.g. a node in a tree has *k* children, then it has 1th, 2nd, .. kth child.

*Note: most of the tree data structure we use is a **rooted tree** for analysis simplicity.*

## Binary and *k*-ary Tree

A [Binary tree](/algorithm-notes/outline/overview-4.md#binary-and-k-ary-tree) is defined on a set of nodes that either contains no nodes or is composed with the *root* node, its connected left subtree and a corresponding right subtree.

In a binary tree structure, filling all missing children of nodes with empty nodes of no descendants will result in a structure called ***full binary tree***.

For trees that have more than 2 children per node, every node (includeing the *root*) in such a tree has no more than *k* number of children. It is termed as a *k*-ary Tree.

A ***complete k-ary tree*** is a tree in which all leaves have the same *depth* and all non-leaf nodes have *k* direct children.

## Table of Contents

* [AVL Tree](/algorithm-notes/outline/overview-4/balanced-search-tree/avl-tree.md) - a trivial implementation of a balanced binary tree.
* [Red-Black Tree](/algorithm-notes/outline/overview-4/balanced-search-tree/red-black-tree.md) - a prevalent balanced binary tree implementation.
* [Heap](/algorithm-notes/outline/overview-4/heap.md) - a special tree structure facilitates various applications such as [priority queue](https://en.wikipedia.org/wiki/Priority_queue) and [heap sort](/algorithm-notes/outline/overview-2/heap-sort.md).
* [B-Tree](/algorithm-notes/outline/overview-4/balanced-search-tree/b-tree.md) - a disk based tree structure, particularly useful in database design.
* [Disjoint-Set](/algorithm-notes/outline/overview-4/disjoint-set.md) - a set operation that finds relevance among data and build up forests for faster manipulations.
* [Threaded Binary Tree](/algorithm-notes/outline/overview-4/threaded-binary-tree.md) - a special form of binary tree that connect leaves to parents, useful in designing Morris traversal, which require Ο(1) extra space.
* [Segment Tree](/algorithm-notes/outline/overview-4/segment-tree.md) - a binary tree used for storing intervals or segments within a data array to speed up queries such as [Range Minimum Query](/algorithm-notes/outline/overview-4/segment-tree.md).