paxread.blogg.se - Trinary note lookup

The node q is then termed a descendant of p. A node p is an ancestor of a node q if it exists on the path from q to the root.

Sibling - Nodes that share the same parent node.

In the example diagram, the tree has height of 2. A (rooted) tree with only one node (the root) has a height of zero.

Height - Length of the path from the root to the deepest node in the tree.

The set of all nodes at a given depth is sometimes called a level of the tree.

Depth - Length of the path from the root to the node.

Child Node - Any node connected to a parent node by a directed edge.

Parent Node - Any node connected by a directed edge to its child or children.

Leaf Node - Any node that has no children.

There is at most one root node in a rooted tree.

Directed Edge - The link from the parent to the child.

Ternary trees are used to implement Ternary search trees and Ternary heaps. Any node in the data structure can be reached by starting at root node and repeatedly following references to either the left, mid or right child. Outside the tree, there is often a reference to the "root" node (the ancestor of all nodes), if it exists. Nodes with children are parent nodes, and child nodes may contain references to their parents. In computer science, a ternary tree is a tree data structure in which each node has at most three child nodes, usually distinguished as "left", “mid” and "right".

A simple ternary tree of size 10 and height 2.