7.2 Complexity

Let [latex]T[/latex] be a binary search tree with [latex]n[/latex] nodes.

1. If [latex]T[/latex] is balanced, the time complexity of searching for an element is [latex]O(\text{log } n)[/latex].
2. If [latex]T[/latex] is unbalanced, the worst-case time complexity is [latex]O(n)[/latex].

Proof

a. In a balanced BST, each node has two children such that the height of the left and right subtrees differ by at most one. This ensures that the tree height [latex]h[/latex] is approximately [latex]\text{log}_{2} n[/latex].

To search for a key, we start at the root and recursively compare the key with the current node. If the key equals the node’s value, we return success. If the key is less, we search the left subtree. If the key is greater, we search the right subtree. At each step, we eliminate half of the remaining nodes. Therefore, the number of comparisons is proportional to the height of the tree. To conclude, in a balanced BST, the maximum number of comparisons is [latex]h = O(\text{log } n)[/latex].

[latex]\square[/latex]

b. In the worst case, the BST degenerates into a linked list, for example, when nodes are inserted in sorted order without rebalancing. In this case, each node has only one child, and the height of the tree becomes [latex]h = n - 1[/latex].

We must traverse each node sequentially from the root to the leaf, performing one comparison per node. Hence, in the worst case, the number of comparisons is [latex]O(n)[/latex].

[latex]\square[/latex]

Let [latex]T[/latex] be a binary search tree with [latex]n[/latex] nodes. The time complexity of inserting a new element into [latex]T[/latex] is

1. [latex]O(\text{log } n)[/latex] in the best case (balanced tree), and
2. [latex]O(n)[/latex] in the worst case (unbalanced tree).

Proof

a. To insert a new element into a BST, we must first locate the correct position for the new node by comparing it with existing nodes, starting from the root.

In a balanced BST, the height [latex]h[/latex] of the tree is approximately [latex]\text{log}_{2} n[/latex].Begin at the root. At each level, compare the new key with the current node. Move left or right depending on whether the key is smaller or larger. Repeat until a null child is found, and insert the new node there. Since each comparison moves one level deeper, and the maximum number of levels is [latex]h[/latex], the number of comparisons is bounded by [latex]O(h) = O(\text{log } n)[/latex].

[latex]\square[/latex]

b. In the worst case, the BST degenerates into a linear chain (e.g., inserting sorted data into an empty tree). The height becomes [latex]h = n - 1[/latex].

Traverse each node sequentially from root to leaf. Perform one comparison per node until the correct position is found. To conclude, in the worst case, insertion requires [latex]O(n)[/latex] comparisons.

[latex]\square[/latex]

Let [latex]T[/latex] be a binary search tree with [latex]n[/latex] nodes. The time complexity of deleting an element from [latex]T[/latex] is [latex]O(\text{log } n)[/latex] in the best case (balanced tree) and [latex]O(n)[/latex] in the worst case (unbalanced tree).

Proof

To delete a node from a BST, we must first locate the node and then restructure the tree to preserve the BST property. The process of locating the node to be deleted is identical to the search operation. Thus, the time to locate the node equals the search time. That is, by Theorem 7.4, the best case (balanced tree) is [latex]O(\text{log } n)[/latex], and the worst case (unbalanced tree) is [latex]O(n)[/latex].

Once the node is found, deletion falls into one of three cases.

Case 1: Leaf Node. Remove the node. No restructuring is needed.

Case 2: Node with One Child. Replace the node with its child. This takes constant time [latex]O(1)[/latex].

Case 3: Node with Two Children. Find the in-order successor (minimum node in the right subtree) or in-order predecessor (maximum node in the left subtree), replace the node’s value with the successor/predecessor, then recursively delete the successor/predecessor node. Finding the in-order successor/predecessor requires a traversal down one subtree, which, according to Theorem 7.4, has a best case (balanced) [latex]O(\text{log } n)[/latex] and a worst case (unbalanced) [latex]O(n)[/latex].

The total time for deletion includes the time to locate the node, which is [latex]O(\text{log } n)[/latex] or [latex]O(n)[/latex], and the time to restructure the tree, which is [latex]O(\text{log } n)[/latex] or [latex]O(n)[/latex]. Thus, the best case (balanced tree) is [latex]O(\text{log } n)[/latex], and the worst case (unbalanced) is [latex]O(n)[/latex].

[latex]\square[/latex]

Let [latex]T[/latex] be a binary search tree constructed from [latex]n[/latex] elements. The time complexity of sorting the elements using tree sort (insertion followed by in-order traversal) is [latex]O(n \text{ log } n)[/latex] if [latex]T[/latex] remains balanced during insertion.

Proof

Recall from Section 7.1  that tree sort is a two-phase algorithm:

1. Insertion Phase: Insert all [latex]n[/latex] elements into a binary search tree.
2. Traversal Phase: Perform an in-order traversal to retrieve the elements in sorted order.

From Theorem 7.5, we know that inserting a single element into a balanced BST takes [latex]O(\text{log } n)[/latex] time. To insert [latex]n[/latex] elements, each insertion takes [latex]O(\text{log } n)[/latex], and the total insertion time is

[latex]T_{\text{insert}}(n) = n O(\text{log } n) = O(n \text{log } n)[/latex]

In-order traversal visits each node exactly once. Each visit takes constant time [latex]O(1)[/latex] and the total traversal time is

[latex]T_{\text{traverse}}(n) = O(n)[/latex]

Combining both phases gives

[latex]T_{\text{total}}(n) = T_{\text{insert}}(n) + T_{\text{traverse}}(n) = O(n \text{log } n) + O(n) = O(n \text{log } n) \quad[/latex]

[latex]\square[/latex]