شجرة البحث الثنائي

شجرة البحث الثنائي Binary Search Tree هي شجرة ثنائية تحتوي على عقد وتمتلك الخصائص التالية:

• يحتوي الفرع الأيسر من العقدة على عقد تمتلك مفاتيح ذات قيمة أقل من قيمة مفتاح هذه العقدة.
• يحتوي الفرع الأيمن من العقدة على عقد تمتلك مفاتيح ذات قيمة أكبر من قيمة مفتاح هذه العقدة.
• يجب أن يكون الفرع الأيمن والأيسر شجرتي بحث ثنائيتين أيضًا، ولا يمكن أن تكون هناك عقد متشابهة.

تفرض هذه الخصائص ترتيبًا خاصًّا للعناصر في شجرة البيانات الثنائية يعتمد على قيمة المفتاح، ونتيجة لذلك تزداد سرعة تنفيذ عمليات البحث والعثور على القيمة الدنيا أو العظمى؛ ولولا وجود هذا الترتيب لكان لزامًا علينا مقارنة جميع المفاتيح مع المفتاح المعطى للحصول على النتيجة المطلوبة.

البحث عن مفتاح

تبدأ عملية البحث عن مفتاح معين في شجرة البحث الثنائية بمقارنة هذا المفتاح مع الجذر، فإن كان المفتاح المطلوب موجودًا في الجذر أعدناه، أمّا إذا كان المفتاح أكبر من الجذر أعدنا البحث في الفرع الأيمن من عقدة الجذر، وإن لم نعثر على المفتاح المطلوب أعدنا عملية البحث في الفرع الأيسر من العقدة.

أمثلة

تعرض الأمثلة التالية كيفية إجراء عملية البحث في شجرة البحث الثنائية وفي عدد من لغات البرمجة:

• C++‎:

struct node* search(struct node* root, int key) 
{ 
	// الحالة الأساسية: أن يكون الجذر فارغًا أو يكون المفتاح موجودًا في الجذر
	if (root == NULL || root->key == key) 
	return root; 
	
	// المفتاح أكبر من مفتاح الجذر
	if (root->key < key) 
	return search(root->right, key); 

	// المفتاح أصغر من مفتاح الجذر
	return search(root->left, key); 
}

• بايثون:

def search(root,key): 
	
	# الحالة الأساسية: أن يكون الجذر فارغًا أو يكون المفتاح موجودًا في الجذر
	if root is None or root.val == key: 
		return root 

	# أن يكون المفتاح أكبر من مفتاح الجذر
	if root.val < key: 
		return search(root.right,key) 
	
	# أن يكون المفتاح أصغر من مفتاح الجذر
	return search(root.left,key)

• جافا:

public Node search(Node root, int key) 
{ 
	// الحالة الأساسية: أن يكون المفتاح فارغًا أو أن يكون المفتاح موجودًا في الجذر
	if (root==null || root.key==key) 
		return root; 

	// أن يكون المفتاح أكبر من مفتاح الجذر
	if (root.key > key) 
		return search(root.left, key); 

	// أن يكون المفتاح أصغر من مفتاح الجذر
	return search(root.right, key); 
}

• البحث عن العقدة 6 في الشجرة التالية:

1. ابدأ البحث من الجذر.
2. مقارنة العنصر المطلوب مع الجذر، فإن كان أقل منه أعدنا عملية البحث من العقدة الفرعية اليسرى، وإن كان أكبر من منه أعدنا عملية البحث من العقدة الفرعية اليمنى.
3. إن عُثر على العنصر المطلوب في أي مكان نعيد قيمة صحيحة، وإلا أعدنا قيمة خاطئة.

إدراج مفتاح في شجرة البحث الثنائية

يُدرج العنصر الجديد دائمًا في عقد الأوراق، إذ نبدأ البحث عن مفتاح معين ابتداءً من الجذر وانتهاءً بعقدة الورقة، فإن عثرنا على عقدة ورقة ندرج العقدة الجديد كعقدة ابن لها.

      100                               100
        /   \        Insert 40            /    \
      20     500    --------->          20     500 
     /  \                              /  \  
    10   30                           10   30
                                              \   
                                              40

أمثلة

تعرض الأمثلة التالية طريقة إدراج عنصر في شجرة البحث الثنائية وفي عدد من لغات البرمجة:

• C++‎:

#include<stdio.h> 
#include<stdlib.h> 

struct node 
{ 
	int key; 
	struct node *left, *right; 
}; 

// دالة مساعدة لإنشاء عقدة جديدة في شجرة البحث الثنائية
struct node *newNode(int item) 
{ 
	struct node *temp = (struct node *)malloc(sizeof(struct node)); 
	temp->key = item; 
	temp->left = temp->right = NULL; 
	return temp; 
} 

// دالة مساعدة لإجراء عملية التنقل الوسطي في شجرة البحث الثنائية 
void inorder(struct node *root) 
{ 
	if (root != NULL) 
	{ 
		inorder(root->left); 
		printf("%d \n", root->key); 
		inorder(root->right); 
	} 
} 

/* دالة مساعدة لإدراج عقدة جديدة مع المفتاح المعطى في شجرة البحث الثنائية */
struct node* insert(struct node* node, int key) 
{ 
	/* إن كانت الشجرة فارغة، تعيد الدالة عقدة جديدة */
	if (node == NULL) return newNode(key); 

	/* وإلا فإنّ الدالة تستدعي نفسها على الفرع الأيسر */
	if (key < node->key) 
		node->left = insert(node->left, key); 
	else if (key > node->key) 
		node->right = insert(node->right, key); 

	/* تعيد الدالة مؤشر العقدة */
	return node; 
} 

// اختبار الدوال السابقة
int main() 
{ 
	/* للنشئ شجرة البحث الثنائي التالية 
			50 
		/	 \ 
		30	 70 
		/ \ / \ 
	20 40 60 80 */
	struct node *root = NULL; 
	root = insert(root, 50); 
	insert(root, 30); 
	insert(root, 20); 
	insert(root, 40); 
	insert(root, 70); 
	insert(root, 60); 
	insert(root, 80); 

	// طباعة نتيجة عملية التنقل الوسطي 
	inorder(root); 

	return 0; 
}

• بايثون:

# صنف مساعد يستخدم لتمثيل عقدة مفردة في شجرة البحث الثنائية
class Node: 
	def __init__(self,key): 
		self.left = None
		self.right = None
		self.val = key 

# دالة مساعدة لإدراج عقدة جديدة مع المفتاح المعطى
def insert(root,node): 
	if root is None: 
		root = node 
	else: 
		if root.val < node.val: 
			if root.right is None: 
				root.right = node 
			else: 
				insert(root.right, node) 
		else: 
			if root.left is None: 
				root.left = node 
			else: 
				insert(root.left, node) 

# دالة مساعدة لإجراء عملية التنقل الوسطي
def inorder(root): 
	if root: 
		inorder(root.left) 
		print(root.val) 
		inorder(root.right) 


# اختبار الدوال السابقة
# لننشئ شجرة البحث الثنائية التالية
#	 50 
# /	 \ 
# 30	 70 
# / \ / \ 
# 20 40 60 80 
r = Node(50) 
insert(r,Node(30)) 
insert(r,Node(20)) 
insert(r,Node(40)) 
insert(r,Node(70)) 
insert(r,Node(60)) 
insert(r,Node(80)) 

# طباعة نتيجة التنقل الوسطي 
inorder(r)

• جافا:

class BinarySearchTree { 

// صنف يحتوي على العقدتين اليمنى واليسرى للعقدة الحالية وقيمة المفتاح
	class Node { 
		int key; 
		Node left, right; 

		public Node(int item) { 
			key = item; 
			left = right = null; 
		} 
	} 

	// جذر شجرة البحث الثنائية
	Node root; 

	// الدالة البانية
	BinarySearchTree() { 
		root = null; 
	} 

	// insertRec يستدعي هذا التابع الدالة 
	void insert(int key) { 
	root = insertRec(root, key); 
	} 
	
	/* دالة تعاودية لإدراج مفتاح جديد في شجرة البحث الثنائية */
	Node insertRec(Node root, int key) { 

		/* إن كانت الشجرة فارغة تعيد الدالة عقدة جديدة */
		if (root == null) { 
			root = new Node(key); 
			return root; 
		} 

		/* وإلا تعيد الدالة استدعاء نفسها على فروع الشجرة */
		if (key < root.key) 
			root.left = insertRec(root.left, key); 
		else if (key > root.key) 
			root.right = insertRec(root.right, key); 

		/* تعيد الدالة مؤشر العقدة */
		return root; 
	} 

	// inorderRec يستدعي هذا التابع الدالة 
	void inorder() { 
	inorderRec(root); 
	} 

	// دالة مساعدة لإجراء عملية التنقل الوسطي في شجرة البحث الثنائية 
	void inorderRec(Node root) { 
		if (root != null) { 
			inorderRec(root.left); 
			System.out.println(root.key); 
			inorderRec(root.right); 
		} 
	} 

	// اختبار الدوال السابقة 
	public static void main(String[] args) { 
		BinarySearchTree tree = new BinarySearchTree(); 

		/* لننشئ شجرة البحث الثنائية التالية 
			50 
		/	 \ 
		30	 70 
		/ \ / \ 
	20 40 60 80 */
		tree.insert(50); 
		tree.insert(30); 
		tree.insert(20); 
		tree.insert(40); 
		tree.insert(70); 
		tree.insert(60); 
		tree.insert(80); 

		// طباعة نتيجة عملية التنقل الوسطي 
		tree.inorder(); 
	} 
}

تعطي الشيفرات السابقة المخرجات التالية:

20
30
40
50
60
70
80

مثال لإدراج العقدة 2 في الشجرة التالية:

1. نبدأ من الجذر.
2. نقارن العنصر المطلوب مع الجذر، فإن كان أصغر منه أعدنا عملية البحث في العقدة اليسرى، وإن كان أكبر منه أعدنا عملية البحث في العقدة اليمنى.
3. بعد الوصول إلى نهاية الشجرة نُدرج العقدة في جهة اليسار (إن كانت أصغر من العقدة الحالية) وإلا أدرجناها في الجهة اليمنى.

التعقيد الزمني

إن أسوأ احتمال للتعقيد الزمني لعمليتي البحث والإدراج هو O(h)‎ وتمثّل h ارتفاع شجرة البحث الثنائية. سنضطر في أسوأ الاحتمالات إلى التنقل عبر عناصر الشجرة من الجذر إلى آخر عقدة ورقية. في بعض الأحيان يمكن لارتفاع شجرة البيانات المائلة skewed أن يصبح n وعندها يصبح التعقيد الزمني لعمليتي الإدراج والبحث هو O(n)‎.

مصادر

• صفحة Binary search Trees في توثيق بنى المعطيات في موقع GeeksforGeeks.