A binary search tree

A binary search tree is a tree structure where each node contains a unique value, has at most two children, contains values in the left subtree that are less than that in the node and values in the right subtree that are greater than that in the node. However, a binary tree is not the only possible tree structure. A decimal search tree contains unique values just like a binary search tree, but instead of having at most two children each node has at most ten children. If the objects being saved in the tree have a sorting key that is a non-negative whole number with a known maximum number of digits (k), then every operation reduces to O(k), because each layer of the tree represents a different digit in the key. The layers of the tree are in Most Significant Digit (MSD) order, with the most significant digit at the top and the least significant digit at the bottom of the tree.

Leave a Reply

Your email address will not be published. Required fields are marked *