เมื่อต้องการหาค่าน้อยที่สุด (smallest) และมากที่สุด (largest) ใน Binary Search Tree (BST) สามารถใช้คุณสมบัติของ BST: ค่าน้อยที่สุดอยู่ที่โหนดซ้ายสุด (leftmost) และค่ามากที่สุดอยู่ที่โหนดขวาสุด (rightmost)
โค้ดตัวอย่าง
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: แทนโหนดของ BST มี key, left, right, parentเมธอด
insert_elem: เพิ่มโหนดตามกฎ BST (น้อยกว่าไปซ้าย, มากกว่าไปขวา)เมธอด
search_node: ค้นหาโหนดแบบ recursiveคลาส
BSTree: จัดการต้นไม้ทั้งต้น มี root และเมธอดต่างๆget_smallest_elem: เดินไปทางซ้ายจนถึงโหนดสุดท้ายget_largest_elem: เดินไปทางขwajนจนถึงโหนดสุดท้ายโปรแกรมหลักรับคำสั่งจากผู้ใช้แบบ interactive
ความซับซ้อนเวลา: O(h) โดย h = ความสูงของต้นไม้ (O(log n) สำหรับ balanced tree, O(n) สำหรับ skewed tree)
