Visualize
Algorithm |
Binary Search TreesSummaryConsider the problem to maintain a set of objects, each one identified by a key, during a sequence of query and update operations. To be more specific, we want to design a data structure for a set which supports test of membership, insertion and removal. Sometimes such a dynamic set is called a dictionary. In the following, we assume a total order on the set of key-values. Search trees are data structures that support many dynamic-set operations including the following operations. (We use the parameter names S for sets, x for elements and k for key-values.)
Tree Data StructureA binary search tree is organized, as the name suggests, in a binary tree, as shown below. Such a tree can be represented by a recursive data structure, in which each node is an object. In addition to a key field, each node contains fields left and right, corresponding to the left and right subtrees at this node. In a more formal description, a tree is either the empty tree NULL, or it's a node containing a key and the two subtrees: datatype Tree = NULL | node of KeyType * Tree * TreeGiven a tree x = node(key,y,x) we call x the root of the tree and we call y and z its children. The elements in a binary search tree are always organized in a way to satisfy the important binary-search-tree property: Let x be a node in a binary search tree. If y is a node in the left subtree of x, then key[y] <= key[x]. If y is a node in the right subtree of x, then key[x] >= key[y]. Tree AlgorithmsIn the following, we're only considering operations on a specific tree. Therefore, we omit the tree parameter for the operations. Also, we identify keys and elements assuming a one-to-one correspondence. Search(k)The search operations searches recursively for a key k. If the key x at the root is equal to k we can return the root node, otherwise the search continues in the appropriate subtree (k < x left subtree, x > k right subtree). In case the corresponding subtree doesn't exist (i.e. is a NULL tree), we abort the search unsuccessfully.Examples
Insert(x)The insert operation searches recursively for x. Thereby, the search path for x is identified. In case x is not found, we add x as a child of y the last node on that path.ExampleDelete(x)The delete operation searches recursively for x. Depending on the number of children of x we consider three cases:
In case x is a leaf node, i.e. it doesn't have any
children, we can simply remove x. Example
The remaining case deals with the situation that both subtrees are present at x: At first, we locate the predecessor y, which is the largest element of the left subtree. Observe, that y has at most one child. Next, we swap the nodes x and y. Now, x has at most one child and we can remove it according to the first two cases. Example
References[1] Introduction To Algorithms, Cormen, Leiserson, Rivest, MIT Press, 1989 |
Henning Biermann, biermann@cs.nyu.edu