যখন একটি বাইনারি সার্চ ট্রি-এ সবচেয়ে ছোট এবং সবচেয়ে বড় উপাদান বের করা প্রয়োজন হয়, তখন একটি বাইনারি ট্রি ক্লাস তৈরি করা হয় এবং ট্রিতে উপাদান যোগ করা, নির্দিষ্ট নোড সার্চ করা ইত্যাদি মেথডগুলো নির্ধারণ করা হয়। ক্লাসের একটি ইনস্ট্যান্স তৈরি করা হয় এবং সেই মেথডগুলো ব্যবহৃত হয়।
নিচে এর একটি উদাহরণ দেওয়া হলো:
উদাহরণ
class BST_Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.parent = None
def insert_elem(self, node):
if self.key > node.key:
if self.left is None:
self.left = node
node.parent = self
else:
self.left.insert_elem(node)
elif self.key < node.key:
if self.right is None:
self.right = node
node.parent = self
else:
self.right.insert_elem(node)
def search_node(self, key):
if self.key > key:
if self.left is not None:
return self.left.search_node(key)
else:
return None
elif self.key < key:
if self.right is not None:
return self.right.search_node(key)
else:
return None
return self
class BSTree:
def __init__(self):
self.root = None
def add_elem(self, key):
new_node = BST_Node(key)
if self.root is None:
self.root = new_node
else:
self.root.insert_elem(new_node)
def search_node(self, key):
if self.root is not None:
return self.root.search_node(key)
def get_smallest_elem(self):
if self.root is not None:
current = self.root
while current.left is not None:
current = current.left
return current.key
def get_largest_elem(self):
if self.root is not None:
current = self.root
while current.right is not None:
current = current.right
return current.key
my_instance = BSTree()
print('Menu (Assume no duplicate keys)')
print('add ')
print('smallest')
print('largest')
print('quit')
while True:
my_input = input('What operation would you perform ? ').split()
operation = my_input[0].strip().lower()
if operation == 'add':
key = int(my_input[1])
my_instance.add_elem(key)
if operation == 'smallest':
smallest = my_instance.get_smallest_elem()
print('The smallest element is : {}'.format(smallest))
if operation == 'largest':
largest = my_instance.get_largest_elem()
print('The largest element is : {}'.format(largest))
elif operation == 'quit':
breakআউটপুট
Menu (Assume no duplicate keys) addsmallest largest quit What operation would you perform ? add 5 What operation would you perform ? add 8 What operation would you perform ? add 11 What operation would you perform ? add 0 What operation would you perform ? add 3 What operation would you perform ? smallest The smallest element is : 0 What operation would you perform ? largest The largest element is : 11 What operation would you perform ? quit'
ব্যাখ্যা
প্রয়োজনীয় অ্যাট্রিবিউটসহ 'BST_Node' ক্লাস তৈরি করা হয়েছে।
এতে একটি 'init' ফাংশন আছে যা লेफট, রাইট এবং পেরেন্ট নোডকে 'None' সেট করতে ব্যবহৃত হয়।
এতে একটি 'insert_element' মেথড আছে যা বাইনারি ট্রিতে উপাদান ইনসার্ট করতে সাহায্য করে।
'search_node' নামে আরেকটি মেথড আছে যা ট্রিতে নির্দিষ্ট নোড সার্চ করে।
'BSTree' নামে আরেকটি ক্লাস নির্ধারণ করা হয়েছে, যেখানে রুট 'None' সেট করা হয়েছে।
'add_elem' নামে একটি মেথড নির্ধারণ করা হয়েছে যা ট্রিতে উপাদান যোগ করে।
'search_node' নামে আরেকটি মেথড আছে যা ট্রিতে নির্দিষ্ট নোড সার্চ করতে সাহায্য করে।
'get_smallest_node' নামে আরেকটি মেথড নির্ধারণ করা হয়েছে যা ট্রিতে সবচেয়ে ছোট নোড বের করতে সাহায্য করে।
'get_largest_node' নামে আরেকটি মেথড নির্ধারণ করা হয়েছে যা ট্রিতে সবচেয়ে বড় নোড বের করতে সাহায্য করে।
'BSTree' ক্লাসের একটি অবজেক্ট তৈরি করা হয়েছে।
ইউজারের নির্বাচিত অপারেশন অনুযায়ী অপারেশনটি সম্পাদন করা হয়েছে।
