二叉树中的排序

1. Introduction

In this tutorial, we’ll explain how to sort a binary tree, and show the time and space complexity calculations of sorting it.

2. Binary Tree

A binary tree is a tree data structure in which each node has at most two child nodes. The child nodes are called the left child and right child.

A binary tree could have different types: rooted, full, complete, perfect, balanced, or degenerate.

The illustration shows a complete binary tree, which has each level completely filled, but with a possible exception for the last level:

Binary trees have two common representations:

• Array representation: fills the array in a top-down approach, from left to right in each level, and an empty slot for any missing child
• Linked list representation: represents node object by node data, left pointer, and right pointer

3. Binary Search Tree (BST)

Binary Search Tree, Binary Sorted Tree or BST, is a binary tree satisfies the following condition:

• For each node, the left sub-tree contains only nodes with values less than that node’s value
• For each node, the right sub-tree contains only nodes with values greater than that node’s value
• Left and right sub-trees are also BSTs

The illustration shows a binary search tree of size 9 and depth 3:

BST keeps the keys in sorted order so that searching for a key or finding a place to insert a key is done in in the worst case, and in the average case, where is a tree size.

4. Tree Sort

4.1. Definition

Tree sort is an online sorting algorithm that builds a binary search tree from the elements input to be sorted, and then traverses the tree, in-order, so that the elements come out in sorted order.

Let’s look at the steps:

1. Takes the elements input in an array
2. Creates a binary search tree by inserting data items from the array into the tree
3. Performs in-order traversal on the tree to get the elements in sorted order

So we’ll use the array representation of the binary tree as an input to sort it.

4.2. Pseudocode

Since the first step is very simple, we present pseudocode for step two and three.

For the second step of the algorithm, the function keeps looking for the right position for the input element recursively by comparing it to the root of each subtree. The following pseudocode, shows the details of that function:

algorithm insert(node, value):
    // INPUT
    //   node = the input node object
    //   value = the value of node key
    // OUTPUT
    //   Returns the inserted node object

    if node = null:
        return Node(value)
    else if value <= node.value:
        node.left <- insert(node.left, value)
    else:
        node.right <- insert(node.right, value)
    
    return node

For the third step, the function goes through all the tree recursively to get the left side of each subtree printed before the right side. This guarantees to print the tree in order. The following pseudocode,  shows the details of that function:

algorithm traverseInOrder(node):
    // INPUT
    //   node = the input node object
    // OUTPUT
    //   Prints the final BST in ascending order

    if node != null:
        traverseInOrder(node.left)
        print(node.value)
        traverseInOrder(node.right)

5. Complexity Analysis

5.1. Time Complexity

Given the following two points:

• Inserting a new node in a BST takes in the average case and in the worst case, as mentioned before
• The input array to tree sort algorithm is of size

So the time complexity for constructing the BST is the time of inserting nodes, which results in total time complexity of in the average case, and in the worst case. We’ll name it .

For the traversal time complexity, it takes steps equal to the tree size to read and print all the nodes, so it takes steps. So that the time complexity of traversing and printing the BST in order is , and we’ll name it .

Finally, the worst-case time complexity of sorting a binary tree using the steps of the tree sort algorithm is as follows:

   

The calculations of the worst-case assume an unbalanced BST. To maintain the average case, a balanced BST is needed.

To build a balanced binary search tree, we need a different data structure to maintain the balancing, and we call it a self-balancing (or height balancing) binary search tree. Most known implementations of the self-balancing BST are AVL Tree, B-Tree, Red-Black Tree, and Splay Tree.

5.2. Space Complexity

As we need to create nodes for elements during all the steps, so the space complexity is .

6. Conclusion

In this tutorial, we explained, in a nutshell, the binary tree, the binary search tree, and the tree sort algorithm. Then we showed the pseudocode of the main two functions of the algorithm; inserting a new node in newly created BST, and traversing this BST to print it in ascending order.

Finally, we showed the time and space complexity of tree sort.