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". Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to the "root" node (the ancestor of all nodes), if it exists. 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. Ternary trees are used to implement Ternary search trees and Ternary heaps.
Definition Directed Edge - The link from the parent to the child. Root - The node with no parents. There is at most one root node in a rooted tree. Leaf Node - Any node that has no children. Parent Node - Any node connected by a directed edge to its child or children. Child Node - Any node connected to a parent node by a directed edge. Depth - Length of the path from the root to the node. The set of all nodes at a given depth is sometimes called a level of the tree. The root node is at depth zero. Height - Length of the path from the root to the deepest node in the tree. A (rooted) tree with only one node (the root) has a height of zero. In the example diagram, the tree has height of 2. Sibling - Nodes that share the same parent node. A node p is an ancestor of a node q if it exists on the path from q to the root. The node q is then termed a descendant of p. The size of a node is the number of descendants it has, including itself.
Properties of ternary trees Maximum number of nodes – Let h {\displaystyle h} be height of a ternary tree. – Let M ( h ) {\displaystyle M(h)} be the maximum number of nodes in a ternary tree of height h {\displaystyle h}
– M ( h ) = 1 + 3 + 9 + ⋯ + 3 h = ∑ i = 0 h 3 i = 3 h + 1 − 1 2 {\displaystyle M(h)=1+3+9+\cdots +3^{h}=\sum _{i=0}^{h}3^{i}={\frac {3^{h+1}-1}{2}}}
– Every tree of height h has at most 3 h + 1 − 1 2 {\displaystyle {\frac {3^{h+1}-1}{2}}} nodes.
If Breadth-first search (BFS) algorithm for searching a ternary tree data structure is considered, then : If a node N {\displaystyle N} occupies TREE [ k ] {\displaystyle [k]} , then its Left Child is stored in TREE [ 3 k − 1 ] {\displaystyle [3k-1]}
Mid Child is stored in TREE [ 3 k ] {\displaystyle [3k]}
Right Child is stored in TREE [ 3 k + 1 ] {\displaystyle [3k+1]}
here, [ k ] {\displaystyle [k]} denotes the node position based on sequentialisation in tree traversal using breadth-first search (BFS) algorithm option.
Common operations
Insertion Nodes can be inserted into ternary trees in between three other nodes or added after an external node. In Ternary trees, a node that is inserted is specified as to which child it is.
External nodes Say that the external node being added onto is node A. To add a new node after node A, A assigns the new node as one of its children and the new node assigns node A as its parent.
Internal nodes Insertion on internal nodes is more complex than on external nodes. Say that the internal node is node A and that node B is the child of A. (If the insertion is to insert a right child, then B is the right child of A, and similarly with a left child insertion or mid child.) A assigns its child to the new node and the new node assigns its parent to A. Then the new node assigns its child to B and B assigns its parent as the new node.
Deletion Deletion is the process whereby a node is removed from the tree. Only certain nodes in a ternary tree can be removed unambiguously.
Node with zero or one child Say that the node to delete is node A. If a node has no children (external node), deletion is accomplished by setting the child of A's parent to null and A's parent to null. If it has one child, set the parent of A's child to A's parent and set the child of A's parent to A's child.
Comparison with other trees The picture below is a binary search tree that represents 12 two-letter words. All nodes on the left child have smaller values, while all nodes on the right child have greater values for all nodes. A search starts from the root. To find the word "ON", we compare it to "IN" and take the right branch. Every comparison could access each character of both words.
in / \ be of / \ / \ as by is or \ \ \ / \ at he it on to
Digital search tries to store strings character by character. The next picture is a tree that represents the same set of 12 words;
_ _ _ _ _ _ _ _ _ _ _ _ _ / / / \ \ \ / / / \ \ \ a b h i o t / \ / \ | / | \ /|\ | s t e y e n s t f n r o as at be by he in is it of on or to
… excerpt ends here. Continue reading the full article.
