Contact Us!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutSign UpSign In

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place. Commercial Alternative to JupyterHub.

| Download

Binary Tree Sort

Views: 647
Tweet
Share
Share

Binary Tree Sorting

Applied Discrete Structures by Alan Doerr & Kenneth Levasseur is licensed under a Creative Commons Attribution - Noncommercial -  No Derivative Works 3.0 United States License.

For more information on the algorithm, see Section 10.4 of Applied Discrete Structures. This is really all Python, although it's evaluated in Sage.

We implement the binary tree sort algorthm in SageMath by first defining a Node in the the tree to contain three components, a key value, a left child and a right child. This is accomplished with the following code. An expression of the form Node(k) creates a node with key k and no children.
class Node:
    def __init__(self, keyval=None,Lchild=None,Rchild=None):
        self.key = keyval
        self.left = Lchild
        self.right = Rchild
    def depth(self):
                    if self.left==None and self.right==None:
            return 0
        else:
            if self.left==None:
                return 1+self.right.depth()
            else:
                if self.right==None:
                    return 1+self.left.depth()
                else:
                    return max(self.left.depth(),self.right.depth())
We define the function insert_sort to recursively insert a key value, b, into a tree rooted at r. We will use this function to build a binary tree. Smaller key values are steered to the left and larger ones to the right.
def insert_sort(r,b):
    if b<r.key:
        if r.left==None:
            r.left=Node(b)
        else:
            insert_sort(r.left,b)
    else:
        if r.right==None:
            r.right=Node(b)
        else:
            insert_sort(r.right,b)
Once the tree is built, we traverse it with the function inorder_traverse, which assembles a sorted list.
def inorder_traverse(r):
    if r.left!=None:
        ls=inorder_traverse(r.left)
    else:
        ls=[]
    m=r.key
    if r.right!=None:
        rs=inorder_traverse(r.right)
    else:
        rs=[]
    return ls+[m]+rs
We demonstrate the process with a list of integers.
a=[6953,811,2324,1884,8945,1943,2923,7909,3390,8229,8337,9656,4545,7082,7333,6461,5306,2945,8414,9352,2993,8663,8260,6810,4263]
The first number in the list is placed at the root of our tree and then the rest are inserted using insert_sort. Note: In Python (and hence in SageMath), all but the first entry in a list a is most easily specified using notation, a[1:].
root=Node(a[0])
for b in a[1:]:
    insert_sort(root,b)
Now we traverse the tree to get our sorted list.
a2=inorder_traverse(root)
a2
[811, 1884, 1943, 2324, 2923, 2945, 2993, 3390, 4263, 4545, 5306, 6461, 6810, 6953, 7082, 7333, 7909, 8229, 8260, 8337, 8414, 8663, 8945, 9352, 9656]