The Complexity of Sorting a Binary Tree

Introduction

A binary tree is a data structure, that is, a way of storing information in an organized form. Knuth defines them as follows:

A binary tree is a finite set of nodes that either is empty or consists of a root and two disjoint binary trees called the left and the right subtrees of the root.

The generic structure of a binary tree is:

  A
 / \
B   C
   / \
  D   E
     / \
    F   G
   / \ / \
  H  L M  N

There are of course non-binary trees. However, it is important to note that a binary tree is not a special case of a tree, but is a different concept. For example, trees

  A   A
 /     \
B       B

are identical when considered as ordinary trees but different when analyzed as binary trees.

In a binary search tree, each node is identified by a key, which is stored respecting the following property:

Let \(x\) be a node of a binary tree. If \(y\) is a node in the left subtree of \(x\) then \(key[y]\leq key[x]\). If \(y\) is a node in the right subtree of \(x\), then \(key[y]\geq key[x]\).

Basic Operations in Binary Search Trees

Suppose a set of data, for example, a database \(D\) which contains information in ASCII format. Each row or record in the database is made up of a series of distinct fields or information identified by a key. Let \(n\) be the number of records of the database, each consisting of \(N\) fields. Then, we have a key field and \(N-1\) fields containing the associated information. Suppose that the key is unique for each record. It is possible to store \(D\) organized as a binary search tree based on the property mentioned above.

Basic or primitive operations in the binary search trees are SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT, and DELETE. Computational complexity depends on the concept of tree height \(h\), which we can informally define as the number of levels of which the tree is composed. We will illustrate this concept using as an example the SEARCH operation.

Suppose we have a key \(k\) and we want to retrieve the associated fields of \(D\) for \(k\). The problem consists in the identification of the node \(x\) such that \(key [x] = k\). So, we move into the tree, starting from the root node, comparing our key with the keys of the nodes we visit. Note that each move involves the descent of a level in the tree. If the key is unique, it should be clear to the reader that the computational complexity of the search is at most equal to \(h\) and the search can be done in time \(O (h)\). This behavior is also satisfied by the other primitive operations, so we have the following important and intuitive result:

Theorem 1. SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT and DELETE operations can be performed in a search binary tree of height \(h\) in time \(O (h)\).

BINARY-TREE-ORDER (x)
    if x! = NIL
    then BINARY-TREE-ORDER (leftt [x])
        print key [x]
        BINARY-TREE-ORDER (right [x])