Sections Summary Data Structure Search Insert Delete References Visualize Tree operations Algorithm Visualization Homepage

Binary Search Trees Summary Consider 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.) search(S,k) returns an element x in S such that key[x]=k, if such an element exists. Otherwise returns NULL. insert(S,x) augments S with x. delete(S,x) removes x from S (if it's contained in S). minimum(S) returns an element x of minimum key-value in S. maximum(S) returns an element x of maximum key-value in S. predecessor(S,x) returns an element which key-value is next larger than key[x] in the set of keys of S. successor(S,x) returns an element which key-value is next smaller than key[y] in the set of keys of S. Basic operations on a binary search tree take time proportional to the height of a tree. For a complete binary tree with n nodes, such operations run in theta (ln(n)) worst-case time. If the tree is a linear chain of n nodes, however, the same operations take theta (n) time. Tree Data Structure A 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 * Tree Given 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 Algorithms In 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. Example Delete(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. In case only one child y is present at x we remove x by replacing it with y. 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