Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Insert and AttachKey Methods

The Insert method of the BinarySearchTree class is defined in Program gif. This method takes as its argument the object which is to be inserted into the binary search tree. It is assumed in this implementation that duplicate keys are not permitted. That is, all of the keys contained in the tree are unique.

   program18695
Program: BinarySearchTree class Insert, AttachKey and Balance methods.

The Insert method behaves like the Find method until it arrives at an external, empty node. Once the empty node has been found, it is transformed into an internal node by calling the AttachKey method. AttachKey works as follows: The object being inserted is assigned to the key field and two new empty binary trees are attached to the node.

Notice that after the insertion is done, the Balance method is called. However, as shown in Program gif, the BinarySearchTree.Balance method does nothing. (Section gif describes the class AVLTree which is derived from the BinarySearchTree class and which inherits the Insert method but overrides the Balance operation).

The asymptotic running time of the Insert method is the same as that of Find for an unsuccessful search. That is, in the worst case the running time is tex2html_wrap_inline63299 and the average case running time is

displaymath63947

where tex2html_wrap_inline63951 is the average depth of an external node in a binary search tree with n internal nodes. When tex2html_wrap_inline63929, the worst case running time is O(n) and the average case is tex2html_wrap_inline59121.


next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.