Tree
When talking about Tree data structure, we normally omit the term free that a free tree is an acyclic, connected, undirected graph. And a possibly disconnected acyclic undirected graph is forest.
Theorem. 1. A G = (V, E) is an undirected graph, then
G is a free tree.
any two vertices in G are connected through a single path.
G is connected, but removing an edge will result in a disconnected graph.
G is connected, acyclic and |E| = |V| - 1.
if adding any single edge to |E| will cause the graph to form a cycle.
Rooted Tree and Ordered Tree
A Rooted 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 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 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 - a trivial implementation of a balanced binary tree.
Red-Black Tree - a prevalent balanced binary tree implementation.
Heap - a special tree structure facilitates various applications such as priority queue and heap sort.
B-Tree - a disk based tree structure, particularly useful in database design.
Disjoint-Set - a set operation that finds relevance among data and build up forests for faster manipulations.
Threaded Binary Tree - a special form of binary tree that connect leaves to parents, useful in designing Morris traversal, which require Ο(1) extra space.
Segment Tree - a binary tree used for storing intervals or segments within a data array to speed up queries such as Range Minimum Query.
Last updated