Contents |
A binary search tree is a binary tree where the nodes in the tree are ordered by ther values. Usually nodes on the left side are "less than" than those on the right side of the tree, recursively. When we say a node A is less than a node B, we mean the value stored at node A is less than the value stored at node B. More specifically, the following rules apply at any point in the tree.
class binaryTreeNode { var value; var left; var right; var parent; //optional } class binarySearchTree { var root; //the top-level binary tree node // operations ... }
The terms used in describing a binary search tree are the same as those describing a generic binary tree.
Binary search trees are considered top-level data structures.
Binary search trees are based upon tree nodes.
The operation descriptions assume unique values in the tree, with values to the left less than those to the right. For trees with duplicate values or a reversed ordering, appropriate modifications to the descriptions should be made.
The typical insertion strategy looks like this:
The helper function implements this straegy, with current referring to its first argument and n refering to the second:
if node n is less than the current node //n must belong on left side of tree if the current node has no left child set the left child pointer of the current node to n else recur, passing the left child and n to the helper else //n must belong on right side of tree if the current node has no right child set the right child pointer of the current node to n else recur, passing the right child and n to the helper
A special case exists if the tree is empty, since the root pointer will need to be set. Inserting a value into a binary tree can take linear time, if the tree is pathologically unbalanced.
There are a number of deletion strategies. One that preserves the existing balance of the tree to some degree is as follows...
Traversals for binary search trees are the same as those of binary trees.
Contents |