Here we give definitions and links to several different types of tree structures

Basic Definitions

Vocabulary used to define trees

1. A tree (or free tree) is a connected, acyclic, undirected graph

2. If an undirected graph is acyclic, but disconnected, it is called a forest.

3. rooted trees have a distinguished node called the root - r.

4. x is an ancestor of y if x is on the unique simple path between r and y.

5. In the case above, y is a descendent of x.

6. A node is both a descendent and a ancestor to itself.

7. If x is an ancestor to y and x!=y then x is a proper acestor of y.

8. Proper descendent is similarly defined.

9. We use child and parent for nodes with edges between them. Likewise we use the term siblings for nodes that have the same parent.

10. A node with no children is an external node

11. A non-leaf node is an internal node.

12. The subtree rooted at x is the tree induced by descendants of x, rooted at x.

13. The number of children of a node in a rooted tree T is called the degree of the node.

14. The length of the path (edges) from the root r to a node x is the depth of x in T.

15. The height of a node in a tree is the number of edges on the longest simple downward path from the node to a leaf.

16. The height of a tree is the height of its root.

Properties of trees

1. G is a free tree.

2. Any 2 vertices in G are connected by a unique SimplePath

3. G is connected, but if any edge is removed from E, the resulting graph is disconnected
4. G is connected, and |E|=|V|-1.
5. G is acyclic, and |E|=|V|-1.
6. G is acyclic, but if any edge is added to E, the resulting graph contains a cycle.

Ordered vs. Positional Trees

Ordered trees have a root and are considered ordered from root to leaf. There is no distinction in how siblings are ordered. Positional trees are what we commonly work with in computer science because we order the siblings as well. A k-nary tree is a positional tree where the children are numbered 1 - k.

1. A Full Tree is a k-nary tree in which each node is either a leaf or has degree k.

2. A Complete k-nary Tree is a k-nary tree in which all the leaves have the same depth.

Binary Trees

A Binary Tree is a positional tree structure defined recursively on a finite set of nodes that:

• Contain no nodes, or

• is composed of three disjoint set of nodes: a root node, a binary tree called it's left subtree, and a binary tree called its right subtree.

Binary Search Trees

Red Black Trees

B-Trees