CoCalc Public Filessage_worksheets / binary_tree_sort.sagewsOpen with one click!
Author: Ken Levasseur
Views : 298
Description: Binary Tree Sort
Compute Environment: Ubuntu 18.04 (Deprecated)

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.
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 slice 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]