বাইনারি সার্চ ট্রি (BST) কনস্ট্রাক্ট করে ইন-অর্ডার ট্রাভার্সাল দিয়ে সর্টেড আউটপুট পাওয়া যায়।
উদাহরণ
class BSTNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.parent = None
def insert(self, node):
if self.key > node.key:
if self.left is None:
self.left = node
node.parent = self
else:
self.left.insert(node)
else:
if self.right is None:
self.right = node
node.parent = self
else:
self.right.insert(node)
def inorder(self):
if self.left:
self.left.inorder()
print(self.key, end=" ")
if self.right:
self.right.inorder()
class BST:
def __init__(self):
self.root = None
def add(self, key):
node = BSTNode(key)
if self.root is None:
self.root = node
else:
self.root.insert(node)
def inorder(self):
if self.root:
self.root.inorder()
# ডেমো
bst = BST()
nums = list(map(int, input("সংখ্যাগুলো দিন: ").split()))
for n in nums:
bst.add(n)
print("সর্টেড লিস্ট:", end=" ")
bst.inorder()
আউটপুট
সংখ্যাগুলো দিন: 67 54 89 0 11 34 99 সর্টেড লিস্ট: 0 11 34 54 67 89 99
ব্যাখ্যা
BST প্রোপার্টি: লেফট < রুট < রাইট।
ইনসার্শন সময় এই প্রোপার্টি মেইনটেইন করা হয়।
ইন-অর্ডার ট্রাভার্সাল BST-কে সর্টেড আউটপুট দেয়।
অ্যাভারেজ টাইম: O(n log n), ওয়ার্স্ট (স্কিউড ট্রি): O(n²)۔
ব্যালেন্সড BST (AVL, Red-Black) দিয়ে O(n log n) গ্যারান্টি।
