Insert and AttachKey Methods

Data Structures and Algorithms with Object-Oriented Design Patterns in C#

`Insert` and `AttachKey` Methods

The Insert method of the BinarySearchTree class is defined in Program . 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 , the BinarySearchTree.Balance method does nothing. (Section 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 and the average case running time is

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