Frequent Patterns in Tree Algorithms
Data is commonly stored in binary tree structures using specialized algorithms. Many advantages come from storing data in a tree structure. For example, searching an ordered binary tree is much faster than sorting a sequential data structure such as an array. A tree data structure can assume many types of patterns during the course of data access and modification. Understanding these patterns can help you design better algorithms to optimize a tree algorithm.
Other People Are Reading
-
Basic Components of a Binary Tree
-
A binary tree consists of nodes, which store data and point to other nodes in the tree. The root node is the starting point of the tree and occupies the top level. It can have up to two child nodes. These child nodes can also have up to two child nodes. The number of child nodes of a given node is called the degree of the node. A node without any children and a degree of zero is called a leaf. The length in nodes from the root node to the furthest leaf node is the height of the tree. The depth of a node is the distance from the root node to it. Every node that has the same depth is said to be on the same level.
Full Binary Tree
-
A full binary tree is a tree in which every node has exactly two or zero children. In other words, every node either has two children or is a leaf. An example of a full binary tree is the Binary Decision Diagram, or BDD.
-
Perfect Binary Tree
-
A perfect binary tree has the same properties of the full binary tree, but all of the leaf nodes are on the same level, which means that the depth of all leaves is the same in a perfect binary tree. Since it is also a full binary tree, all nodes except the leaf nodes have a degree of 2.
Balanced Binary Tree
-
A balanced binary tree is one in which the depth of every leaf node is either the same or differs by a value of one. Adding and removing nodes from a balanced binary tree can unbalance it, so a series of adjustments called rotations must take place to rebalance the tree. Keeping a tree balanced ensures that the average search time for any node is optimal. Significant overhead is required to maintain the balance of a tree.
Degenerate Binary Tree
-
A degenerate binary tree is one in which every node except the leaf node has exactly one child node. It has the same performance characteristics of a linked list, which increases the search time for any node by a considerable amount. For example, consider a case in which the node being searched for is the leaf node. The entire tree must be traversed in order to find this node. With a balanced binary tree, finding a leaf node only requires a number of node traversals equal to the depth of the leaf node. With large trees, the difference in performance can be significant.
-
References
Resources
- Photo Credit Jupiterimages/Photos.com/Getty Images
