BST (Binary Search Trees)
«درخت جستجوی دودویی (BST)» یک درخت دودویی است. در هر گره، مقدارهای سمت چپ کوچک ترند و مقدارهای سمت راست بزرگ ترند. بنابراین جستجو و درج و حذف خیلی سریع می شوند.
تعریف BST و ویژگی ها
برای هر گره «X»، همه گره های چپ از X کوچک تر هستند. همچنین، همه گره های راست از X بزرگ تر هستند. دو زیر درخت چپ و راست نیز خودشان BST هستند. فرض می کنیم همه مقادیر یکتا باشند.
پیمایش inorder برای بررسی BST
اگر یک درخت واقعاً BST باشد، «میان سفری (In-order)» خروجی صعودی می دهد. کد زیر همان درخت نمونه را می سازد و inorder را چاپ می کند.
class TreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def inOrderTraversal(node):
if node is None:
return
inOrderTraversal(node.left)
print(node.data, end=", ")
inOrderTraversal(node.right)
root = TreeNode(13)
node7 = TreeNode(7)
node15 = TreeNode(15)
node3 = TreeNode(3)
node8 = TreeNode(8)
node14 = TreeNode(14)
node19 = TreeNode(19)
node18 = TreeNode(18)
root.left = node7
root.right = node15
node7.left = node3
node7.right = node8
node15.left = node14
node15.right = node19
node19.left = node18
inOrderTraversal(root)
جستجو در BST
جستجو مثل «جستجوی دودویی (Binary Search)» در آرایه مرتب است. اگر مقدار هدف کوچک تر بود، چپ برو. اگر بزرگ تر بود، راست برو.
def search(node, target):
if node is None:
return None
elif node.data == target:
return node
elif target < node.data:
return search(node.left, target)
else:
return search(node.right, target)
result = search(root, 13)
if result:
print(f"Found the node with value: {result.data}")
else:
print("Value not found in the BST.")
نکته: زمان جستجو در BST متعادل حدود O(log n) است. اما در بدترین حالت نامتعادل، O(n) می شود.
درج گره در BST
درج مثل جستجو پیش می رود. در نهایت در اولین جای خالی، گرهِ جدید برگ می شود. مقدار تکراری را نادیده بگیر.
def insert(node, data):
if node is None:
return TreeNode(data)
else:
if data < node.data:
node.left = insert(node.left, data)
elif data > node.data:
node.right = insert(node.right, data)
return node
insert(root, 10)
کمینه زیر درخت در BST
برای حذف گره با دو فرزند، باید «جانشین inorder» را بیابیم. کمینه زیر درخت راست همان جانشین است.
def minValueNode(node):
current = node
while current.left is not None:
current = current.left
return current
print("\nLowest value:", minValueNode(root).data)
حذف گره در BST
سه حالت داریم: 1) برگ است؛ لینک را حذف کن. 2) یک فرزند دارد؛ والد را به همان فرزند وصل کن. 3) دو فرزند دارد؛ جانشین inorder را جایگزین کن و سپس او را حذف کن.
def delete(node, data):
if not node:
return None
if data < node.data:
node.left = delete(node.left, data)
elif data > node.data:
node.right = delete(node.right, data)
else:
if not node.left:
temp = node.right
node = None
return temp
elif not node.right:
temp = node.left
node = None
return temp
node.data = minValueNode(node.right).data
node.right = delete(node.right, node.data)
return node
delete(root, 15)
تعادل BST و پیچیدگی زمان
عملیات ها در اصل O(h) هستند. اگر درخت متعادل باشد، ارتفاع حدود \log_2 n است. پس جستجو، درج و حذف حدود O(log n) می شوند. در نامتعادل، ارتفاع نزدیک n است و هزینه O(n) می شود.
نکته: برای متعادل سازی خودکار، به AVL Tree مراجعه کن. برای پایه درخت ها، صفحه درخت های دودویی را ببین.
گام های عملی سریع
- کلاس TreeNode را بساز.
- گره ها را بچین و پیوند بده.
- با inorder صحت BST را بسنج.
- جستجو، درج و حذف را تمرین کن.
جمع بندی سریع
- BST یعنی چپ کوچک تر، راست بزرگ تر.
- inorder در BST خروجی صعودی می دهد.
- درج و حذف مانند جستجو مسیر می روند.
- تعادل، سرعت را تضمین می کند.