concept tree in category AI
This is an excerpt from Manning's book Grokking Artificial Intelligence Algorithms.
A tree is a popular data structure that simulates a hierarchy of values or objects. A hierarchy is an arrangement of things in which a single object is related to several other objects below it. A tree is a connected acyclic graph—every node has an edge to another node, and no cycles exist.
In a tree, the value or object represented at a specific point is called a node. Trees typically have a single root node with zero or more child nodes that could contain subtrees. Let’s take a deep breath and jump into some terminology. When a node has connected nodes, the root node is called the parent. You can apply this thinking recursively. A child node may have its own child nodes, which may also contain subtrees. Each child node has a single parent node. A node without any children is a leaf node.
The terminology used to relate family members is heavily used in working with trees. Keep this analogy in mind, as it will help you connect the concepts in the tree data structure. Note that in figure 2.12, the height and depth are indexed from 0 from the root node.
Figure 2.12 The main attributes of a tree
The topmost node in a tree is called the root node. A node directly connected to one or more other nodes is called a parent node. The nodes connected to a parent node are called child nodes or neighbors. Nodes connected to the same parent node are called siblings. A connection between two nodes is called an edge.
A path is a sequence of nodes and edges connecting nodes that are not directly connected. A node connected to another node by following a path away from the root node is called a descendent, and a node connected to another node by following a path toward the root node is called an ancestor. A node with no children is called a leaf node. The term degree is used to describe the number of children a node has; therefore, a leaf node has degree zero.