Rooted Tree
Definition
A rooted tree is a tree in which one vertex has been designated the root. The edges of the tree are directed away from the root, establishing a parent-child relationship between nodes. The root is the only node in the tree with no parent. Each other node has exactly one parent and zero or more children.
Properties
Rooted trees have several important properties that distinguish them from other types of trees in graph theory. These properties include:
- Unique Paths: In a rooted tree, there is a unique path from the root to every other node. This is a direct consequence of the tree property that there are no cycles, and the rooted tree property that there is a designated root.
- Subtrees: Each child of a node, along with its descendants, forms a subtree. This property allows many problems on trees to be solved using recursive methods, as the problem can be broken down into smaller problems on subtrees.
- Levels: The level of a node is defined as the number of edges on the path from the root to the node. The root is at level 0, its children are at level 1, its grandchildren are at level 2, and so on. The level of a node also corresponds to its depth in the tree.
- Height: The height of a rooted tree is the maximum level of any node in the tree. Equivalently, it is the length of the longest path from the root to a leaf. The height of a tree gives an indication of the maximum number of recursive calls that would be needed to solve a problem on the tree.
Types of Rooted Trees
There are several special types of rooted trees that are frequently studied in graph theory and computer science:
- Binary Trees: A binary tree is a rooted tree in which each node has at most two children, often designated as the left child and the right child.
- Ordered Trees: An ordered tree, or plane tree, is a rooted tree in which the order of the children matters. The children of each node can be viewed as being arranged in a sequence, from left to right.
- Balanced Trees: A balanced tree is a rooted tree in which the heights of the subtrees of each node differ by at most one. Balanced trees are important in computer science, as they are used to implement binary search trees that have good worst-case performance.
- Heap Trees: A heap tree, or simply a heap, is a complete binary tree that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of C.
Applications
Rooted trees have many applications in computer science and mathematics. Some of the most common applications include:
- Data Structures: Rooted trees are used to implement various data structures in computer science, including binary search trees, heaps, and tries. These data structures are used in a wide variety of applications, from database indexing to network routing.
- Algorithms: Many algorithms, particularly those in graph theory and artificial intelligence, make use of rooted trees. For example, the depth-first search and breadth-first search algorithms explore a graph by constructing a rooted tree.
- Combinatorics: In combinatorics, rooted trees are used to count certain types of combinatorial objects. For example, the number of rooted trees with n nodes is given by the (n-1)st Cayley's formula.