Tree sort is an efficient sorting algorithm that uses a binary tree data structure to sort data. It is a comparison-based sorting algorithm, meaning it compares two elements at a time to determine their relative order. Tree sort is a stable sorting algorithm, meaning it preserves the relative order of equal elements. Tree sort has a time complexity of O(n log n) on average and in the worst case, and a space complexity of O(n) in the worst case.
What is a Binary Tree?
A binary tree is a data structure that stores data in nodes. A node has two children, a left child and a right child. The left child is always less than the parent node and the right child is always greater than the parent node. This allows the tree to be sorted in an efficient manner.
How Tree Sort Works
Tree sort works by inserting the elements of an unsorted list into a binary tree. The tree is then traversed in-order to retrieve the elements in sorted order. Tree sort is an efficient sorting algorithm as it only requires one comparison per item, making it faster than other comparison-based sorting algorithms such as quicksort and merge sort.
Python Code
The following Python code shows how tree sort works:
# Define a Node class
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
# Define a Tree class
class Tree:
def __init__(self):
self.root = None
# Insert a new node into the tree
def insert(self, value):
new_node = Node(value)
if self.root == None:
self.root = new_node
else:
curr_node = self.root
while True:
if value <= curr_node.value:
if curr_node.left == None:
curr_node.left = new_node
break
else:
curr_node = curr_node.left
else:
if curr_node.right == None:
curr_node.right = new_node
break
else:
curr_node = curr_node.right
# Traverse the tree in-order to retrieve the elements
# in sorted order
def in_order_traversal(self, node):
if node != None:
self.in_order_traversal(node.left)
print(node.value)
self.in_order_traversal(node.right)
# Sort the elements of an unsorted list
# using tree sort
def tree_sort(unsorted_list):
tree = Tree()
for item in unsorted_list:
tree.insert(item)
sorted_list = []
tree.in_order_traversal(tree.root, sorted_list)
return sorted_list
Time Complexity
Tree sort has a time complexity of O(n log n) in the average and worst case. This is because the tree must be traversed in-order to retrieve the elements in sorted order, which requires O(n log n) time.
Space Complexity
Tree sort has a space complexity of O(n) in the worst case. This is because the tree data structure requires O(n) space to store the elements.
Conclusion
Tree sort is an efficient sorting algorithm that uses a binary tree data structure to sort data. It is a comparison-based sorting algorithm, meaning it compares two elements at a time to determine their relative order. Tree sort has a time complexity of O(n log n) in the average and worst case, and a space complexity of O(n) in the worst case.
Exercises
Write a function that takes an unsorted list and sorts it using the tree sort algorithm.
def tree_sort(unsorted_list):
tree = Tree()
for item in unsorted_list:
tree.insert(item)
sorted_list = []
tree.in_order_traversal(tree.root, sorted_list)
return sorted_list
Write a function to traverse a binary tree in pre-order.
def pre_order_traversal(self, node):
if node != None:
print(node.value)
self.pre_order_traversal(node.left)
self.pre_order_traversal(node.right)
Write a function to traverse a binary tree in post-order.
def post_order_traversal(self, node):
if node != None:
self.post_order_traversal(node.left)
self.post_order_traversal(node.right)
print(node.value)
Given the following binary tree, write a function to return the deepest node.
1
/ \
2 3
/ \ / \
4 5 6 7
def deepest_node(root):
if root is None:
return None
queue = [root]
deepest_node = None
while queue:
node = queue.pop(0)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
deepest_node = node
return deepest_node
Write a function to calculate the height of a binary tree.
def height(root):
if root is None:
return 0
else:
left_height = height(root.left)
right_height = height(root.right)
if left_height > right_height:
return left_height + 1
else:
return right_height + 1