Algorithms/binary trees

تصنف المصفوفات والقوائم المترابطة والأكداس والأرتال كبنى معطيات خطية، أمّا أشجار البيانات فتصنّف كبنى معطيات هرمية hierarchical.

تسمى العقدة العليا في شجرة البيانات بجذر الشجرة root، وتسمى العناصر التي تتفرع من عنصر معين بأبناء ذلك العنصر children، أما العنصر الذي يكون فوق عنصر آخر فيسمى بالعنصر الأب parent، أما العناصر التي لا تمتلك أبناء فتسمّى بالأوراق leaves.

في المثال التالي العنصر a هو ابن للعنصر f والعنصر f هو أب العنصر a.

      tree
      ----
       j    <-- جذر
     /   \
    f      k  
  /   \      \
 a     h      z    <-- أوراق

تطبيقات تستخدم أشجار البيانات

تستخدم أشجار البيانات لتخزين المعلومات بصورة هرمية، مثل نظام الملفات في الحاسوب:

file system
-----------
     /    <-- الجذر
  /      \
...       home
      /          \
   ugrad        course
    /       /      |     \
  ...      cs101  cs112  cs113

وهناك تطبيقات أخرى لأشجار البيانات منها:

1. تتيح أشجار البيانات (مع بعض الترتيب مثل أشجار البيانات الثنائية) إجراء عمليات وصول وبحث متوسطة السرعة (أسرع من القوائم المترابطة وأبطأ من المصفوفات).
2. تتيح أشجار البيانات إجراء عمليات إدراج وحذف متوسطة السرعة (أسرع من المصفوفات وأبطأ من القوائم المترابطة غير المرتبة).
3. تشبه أشجار البيانات القوائم المترابطة في عدم وجود حدّ علوي لعدد العقد وذلك لأنّها مترابطة بواسطة المؤشرات.
4. معالجة البيانات الهرمية.
5. تسهيل عملية البحث عن المعلومات (راجع التنقل في شجرة البيانات).
6. معالجة القوائم المرتبة من البيانات.
7. تستخدم أشجار البيانات كمسار عمل لمعالجة الصور الرقمية وإضافة المؤثرات البصرية.
8. خوارزميات المسارات Router.
9. صورة من صور عمليات اتخاذ القرار ذات المراحل المتعددة.
10. الكومة هي شجرة بيانات ويمكن إنشاؤها باستخدام المصفوفات وتستخدم لإنشاء أرتال الأولوية.
11. B-Tree و B+ Tree وتستخدم لتنفيذ عملية الفهرسة في قواعد البيانات.
12. شجرة الصيغة Syntax Tree: تستخدم في المصرّفات Compilers.
13. K-D Tree: شجرة لتجزئة المساحة وتستخدم لترتيب النقاط في مساحة من K من الأبعاد.
14. شجرة اللواحق Suffix Tree: وتستخدم للبحث السريع عن نمط معين في نص ثابت.

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

تسمى الشجرة التي يمتلك كل عنصر فيها ابنين اثنين على الأكثر بشجرة البيانات الثنائية Binary Tree، ولما كان كل عنصر يمتلك ابنين فقط، فيمكن تسميتهما بالابن الأيمن والابن الأيسر.

تمثيل شجرة البيانات الثنائية

تمثّل شجرة البيانات الثنائية بواسطة مؤشر إلى العقدة العلوية في شجرة البيانات، وإن كانت الشجرة فارغة فإنّ قيمة الجذر تساوي NULL.

تضمّ العقدة الأجزاء التالية:

1. البيانات.
2. مؤشر إلى العقدة اليسرى.
3. مؤشر إلى العقدة اليمنى.

يمكن تمثيل العقدة في لغة C بواسطة البنى structures، ويعرض المثال التالية عقدة تضمّ بيانات عددية:

struct node 
{ 
int data; 
struct node *left; 
struct node *right; 
};

أما في لغتي بايثون وجافا فيمكن استخدام الأصناف لتمثيل العقد:

• بايثون:

class Node: 
	def __init__(self,key): 
		self.left = None
		self.right = None
		self.val = key

• جافا

class Node 
{ 
	int key; 
	Node left, right; 

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

إنشاء شجرة بيانات ثنائية بسيطة

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

      tree
      ----
       1    <-- الجذر
     /   \
    2     3  
   /   
  4

• C++‎:

struct node 
{ 
	int data; 
	struct node *left; 
	struct node *right; 
}; 

/* تحجز هذه الدالة عقدة جديدة تمتلك البيانات المعطاة ومؤشرين للعقدتين اليمنى واليسرى واللتان تحملان القيمة null */
struct node* newNode(int data) 
{ 
// حجز الذاكرة للعقدة الجديدة
struct node* node = (struct node*)malloc(sizeof(struct node)); 

// إسناد البيانات إلى هذه العقدة
node->data = data; 

// NULL تهيئة العقدتين اليمنى واليسرى لتحملا القيمة 
node->left = NULL; 
node->right = NULL; 
return(node); 
} 


int main() 
{ 
// إنشاء الجذر
struct node *root = newNode(1); 
/* بعد تنفيذ العبارة أعلاه تصبح الشجرة بالشكل التالي

		1 
	/       \ 
   NULL    NULL 
*/
	

root->left	 = newNode(2); 
root->right	 = newNode(3); 
/* أصبحت العقدتان 2 و 3 الابنين الأيسر والأيمن للعقدة 1
		1 
		/ \ 
		2	 3 
	/ \ / \ 
	NULL NULL NULL NULL 
*/


root->left->left = newNode(4); 
/* أصبحت العقدة 4 الابن الأيسر للعقدة 2 
		1 
	/	 \ 
	2		 3 
	/ \	 / \ 
4 NULL NULL NULL 
/ \ 
NULL NULL 
*/

getchar(); 
return 0; 
}

• بايثون:

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


# إنشاء الجذر
root = Node(1) 
''' أصبحت الشجرة بعد تنفيذ العبارة السابقة بالشكل التالي 
		1 
	/ \ 
	None None'''

root.left	 = Node(2); 
root.right	 = Node(3); 
	
''' أصبحت العقدتان 2 و 3 الابنين الأيسر والأيمن للعقدة 1 
		1 
		/ \ 
		2	 3 
	/ \ / \ 
None None None None'''


root.left.left = Node(4); 
'''أصبحت العقدة 4 الابن الأيسر للعقدة 2 
		1 
	/	 \ 
	2		 3 
	/ \	 / \ 
4 None None None 
/ \ 
None None'''

• جافا:

/* يضمّ هذا الصنف الابن الأيسر والأيمن للعقد الحالية وكذلك قيمة المفتاح */
class Node 
{ 
	int key; 
	Node left, right; 

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

class BinaryTree 
{ 
	// جذر الشجرة الثنائية
	Node root; 

	// الدوال البانية
	BinaryTree(int key) 
	{ 
		root = new Node(key); 
	} 

	BinaryTree() 
	{ 
		root = null; 
	} 

	public static void main(String[] args) 
	{ 
		BinaryTree tree = new BinaryTree(); 

		/*إنشاء الجذر*/
		tree.root = new Node(1); 

		/* تصبح الشجرة بعد تنفيذ العبارة السابقة بالشكل التالي 

			1 
			/ \ 
		null null	 */

		tree.root.left = new Node(2); 
		tree.root.right = new Node(3); 

		/* أصبحت العقدتان 2 و 3 الابنين الأيسر والأيمن للعقدة 1 
			1 
			/ \ 
			2	 3 
		/ \ / \ 
		null null null null */


		tree.root.left.left = new Node(4); 
		/* أصبحت العقدة 4 الابن الأيسر للعقدة 2 
					1 
				/	 \ 
			2		 3 
			/ \	 / \ 
			4 null null null 
		/ \ 
		null null 
		*/
	} 
}

خصائص أشجار البيانات الثنائية

1- أقصى عدد للعقد في أي مستوى 'l' في شجرة البيانات الثنائية هو ‎2^‎l-1

يقصد بالمستوى هنا هو عدد العقد ابتداءً من الجذر وانتهاءً بالعقدة المعنية (ومن ضمنها الجذر والعقدة المعنية)، ويقع الجذر في المستوى رقم 1.

يمكن إثبات هذه القاعدة بالطريقة التالية:

l = 1 في الجذر، وبهذا يصبح عدد العقد ‎2^1-1 = 1‎

لو فرضنا أنّ أقصى عدد للعقد في المستوى l هو ‎2^l-1، ولمّا كانت كل عقدة في شجرة البيانات الثنائية تمتلك عقدتين فقط من عقد الأبناء، فإنّ المستوى التالي لهذه العقدة سيمتلك ضعف عدد العقد، أي ‎2*2^l-1.

2- أقصى عدد للعقد في شجرة بيانات ثنائية ذات ارتفاع 'h' هو ‎2^h-1‎

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

تمتلك الشجرة أقصى عدد من العقد إن احتوت جميع المستويات على أقصى عدد من العقد؛ لذا فإنّ العدد الأقصى للعقد في الشجرة الثنائية ذات الارتفاع h هو 1 + 2 + 4 + .. + 2^h-1، وهي متسلسلة هندسية بسيطة تضمّ h من الأطراف ومجموعها هو ‎‎‎2^h-1‎‎‎.

تشير بعض الكتب إلى أنّ ارتفاع الجذر هو 0، وعلى هذا الفرض تصبح الصيغة السابقة بالهيئة التالية: 2‎‎‎^h+1-1‎‎‎.

3- إن أدنى ارتفاع ممكن أو أدنى عدد من المستويات في شجرة بيانات ثنائية تمتلك N من العقد هو Log₂(N+1)‎

لو أخذنا بنظر الاعتبار الفرض القائل بأن عقدة الورقة تمتلك الارتفاع 0، فإنّ الصيغة السابقة ستصبح: ‎Log₂(N+1)‎ - 1.

4- شجرة البيانات الثنائية التي تحتوي على L من الأوراق تمتلك على الأقل Log₂L + 1 من المستويات

تمتلك شجرة البيانات الثنائية أقصى عدد من الأوراق (وأدنى عدد من المستويات) عندما تكون جميع المستويات مملوءة بالكامل، ولو فرضنا أنّ لدنيا مستوى واحدًا فقط، فإنّ ما يلي صحيح لعدد L من من الأوراق.

   L   <=  2l-1  [From Point 1]
   l =   ? Log2L ? + 1 
   l هو أدنى عدد من المستويات
   where l is the minimum number of levels.

5- في شجرة البيانات الثنائية التي تمتلك كل عقدة فيها إمّا 0 أو 2 من عقد الأبناء، فإنّ عدد عقد الأوراق هو دائمًا أكبر بواحد من العقد التي تمتلك عقدتي أبناء

   L = T + 1
	  L = عدد عقد الأوراق
      T = عدد العقد الداخلية التي تمتلك عقدتي أبناء

أنواع أشجار البيانات الثنائية

شجرة البيانات الثنائية الممتلئة Full

تكون شجرة البيانات الثنائية ممتلئة إن كان لكل عقدة فيها 0 أو 2 من عقد الأبناء. ويمكن كذلك تعريف شجرة البيانات الثنائية الممتلئة بأنّها الشجرة التي يكون لكل عقدة فيها عقدتا أبناء باستثناء عقد الأوراق.

               18
           /       \  
         15         30  
        /  \        /  \
      40    50    100   40

             18
           /    \   
         15     20    
        /  \       
      40    50   
    /   \
   30   50

               18
            /     \  
          40       30  
                   /  \
                 100   40

إن عدد عقد الأوراق في شجرة البيانات الثنائية الممتلئة يساوي عدد العقد الداخلية مضافًا إليه واحد.

L = I + 1

L = عدد عقد الأوراق.

I = عدد العقد الداخلية.

شجرة البيانات الثنائية الكاملة Complete

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

               18
           /       \  
         15         30  
        /  \        /  \
      40    50    100   40


               18
           /       \  
         15         30  
        /  \        /  \
      40    50    100   40
     /  \   /
    8   7  9

الكومات الثنائية هي من الأمثلة العملية على أشجار البيانات الثنائية الكاملة.

أشجار البيانات الثنائية التامّة Perfect

تعدّ شجرة البيانات الثنائية تامّة إن كان لجميع العقد الداخلية عقدتا أبناء وكانت جميع عقد الأوراق في مستوى واحد.

               18
           /       \  
         15         30  
        /  \        /  \
      40    50    100   40


               18
           /       \  
         15         30

تحتوي شجرة البيانات الثنائية التامّة ذات الارتفاع h على ‎2^h-1 من العقد.

يمكن تمثيل أسلاف الإنسان بشجرة بيانات ثنائية تامة، فلو جعلنا الشخص في جذر الشجرة، يصبح أبواه عقدتي أبناء، ويصبح آباء الآباء عقدتي أبناء لكل أب وهكذا دواليك.

      			   الشخص
			/    	          \
		  الأب                 الأم
	 /          \         /         \
أب الأب    أم الأب    أب الأم       أم الأم

شجرة البيانات الثنائية المتوازنة Balanced

تكون شجرة البيانات الثنائية متوازنة إن كان ارتفاع الشجرة هو O(Log n)‎ و n هو عدد العقد. على سبيل المثال تحافظ شجرة AVL على الارتفاع O(Log n)‎ وذلك بالتأكد من أنّ الفرق بين ارتفاع الأفرع اليسرى والأفرع اليمنى هو 1. أما أشجار البيانات أحمر-أسود فتحافظ على الارتفاع O(Log n)‎ وذلك بالتأكد من أن عدد العقد السوداء متساوٍ في كل المسارات التي تبدأ من الجذر وتنتهي بعقدة ورقة ولا وجود لعقد حمراء مجاورة.

تعدّ أشجار البيانات الثنائية المتوازنة خيارًا جيّدًا من ناحية الأداء في عمليات البحث والإدراج والحذف لأنّ التعقيد الزمني لها هو O(Log n)‎.

الأشجار البيانية الثنائية المتحللة degenerate (المريضة pathological)

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

      10
      /
    20
     \
     30
      \
      40

إدراج العناصر في أشجار البيانات الثنائية

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

أمثلة

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

• C++‎:

#include <iostream> 
#include <queue> 
using namespace std; 

/* تمتلك العقدة في الشجرة الثائية مفتاحًا ومؤشرًا إلى العقدة الابن اليسرى ومؤشراً إلى العقدة الابن اليمنى */
struct Node { 
	int key; 
	struct Node* left, *right; 
}; 

/* دالة لإنشاء عقدة جديدة في الشجرة الثنائية وإعادة المؤشر */
struct Node* newNode(int key) 
{ 
	struct Node* temp = new Node; 
	temp->key = key; 
	temp->left = temp->right = NULL; 
	return temp; 
}; 

/* التنقل عبر عناصر الشجرة الثنائي حسب الترتيب */

void inorder(struct Node* temp) 
{ 
	if (!temp) 
		return; 

	inorder(temp->left); 
	cout << temp->key << " "; 
	inorder(temp->right); 
} 

/* دالة لإدراج عنصر في الشجرة الثنائية */

void insert(struct Node* temp, int key) 
{ 
	queue<struct Node*> q; 
	q.push(temp); 

	// التنقل عبر مستويات الشجرة الثنائية بحثًا عن مكان فارغ
    
    while (!q.empty()) { 
		struct Node* temp = q.front(); 
		q.pop(); 

		if (!temp->left) { 
			temp->left = newNode(key); 
			break; 
		} else
			q.push(temp->left); 

		if (!temp->right) { 
			temp->right = newNode(key); 
			break; 
		} else
			q.push(temp->right); 
	} 
} 

// اختبار الدوال السابقة
int main() 
{ 
	struct Node* root = newNode(10); 
	root->left = newNode(11); 
	root->left->left = newNode(7); 
	root->right = newNode(9); 
	root->right->left = newNode(15); 
	root->right->right = newNode(8); 

	cout << "Inorder traversal before insertion:"; 
	inorder(root); 

	int key = 12; 
	insert(root, key); 

	cout << endl; 
	cout << "Inorder traversal after insertion:"; 
	inorder(root); 

	return 0; 
}

• بايثون:

class newNode(): 

	def __init__(self, data): 
		self.key = data 
		self.left = None
		self.right = None
		
# التنقل عبر مستويات الشجرة الثنائية

def inorder(temp): 

	if (not temp): 
		return

	inorder(temp.left) 
	print(temp.key,end = " ") 
	inorder(temp.right) 


# دالة لإدراج عنصر في الشجرة الثنائية

def insert(temp,key): 

	q = [] 
	q.append(temp) 
	
    # التنقل عبر مستويات الشجرة الثنائية بحثاً عن مكان فارغ
	while (len(q)): 
		temp = q[0] 
		q.pop(0) 

		if (not temp.left): 
			temp.left = newNode(key) 
			break
		else: 
			q.append(temp.left) 

		if (not temp.right): 
			temp.right = newNode(key) 
			break
		else: 
			q.append(temp.right) 
	
# اختبار الدوال السابقة
if __name__ == '__main__': 
	root = newNode(10) 
	root.left = newNode(11) 
	root.left.left = newNode(7) 
	root.right = newNode(9) 
	root.right.left = newNode(15) 
	root.right.right = newNode(8) 

	print("Inorder traversal before insertion:", end = " ") 
	inorder(root) 

	key = 12
	insert(root, key) 

	print() 
	print("Inorder traversal after insertion:", end = " ") 
	inorder(root)

• جافا:

import java.util.LinkedList; 
import java.util.Queue; 
public class GFG { 
	
	// تمتلك العقدة في الشجرة الثنائية مفتاحًا ومؤشرًا إلى عقدة الابن اليسرى ومؤشرًا إلى عقدة الابن اليمنى
	static class Node { 
		int key; 
		Node left, right; 
		
		// دالة بانية
		Node(int key){ 
			this.key = key; 
			left = null; 
			right = null; 
		} 
	} 
	static Node root; 
	static Node temp = root; 
	
    // التنقل عبر مستويات الشجرة الثنائية
	
	static void inorder(Node temp) 
	{ 
		if (temp == null) 
			return; 
	
		inorder(temp.left); 
		System.out.print(temp.key+" "); 
		inorder(temp.right); 
	} 
	
	// دالة لإدراج عنصر في الشجرة الثنائية
	static void insert(Node temp, int key) 
	{ 
		Queue<Node> q = new LinkedList<Node>(); 
		q.add(temp); 
	
		// التنقل عبر مستويات الشجرة الثنائية بحثًا عن مكان فارغ
		while (!q.isEmpty()) { 
			temp = q.peek(); 
			q.remove(); 
	
			if (temp.left == null) { 
				temp.left = new Node(key); 
				break; 
			} else
				q.add(temp.left); 
	
			if (temp.right == null) { 
				temp.right = new Node(key); 
				break; 
			} else
				q.add(temp.right); 
		} 
	} 
	
	// اختبار الدوال السابقة
	public static void main(String args[]) 
	{ 
		root = new Node(10); 
		root.left = new Node(11); 
		root.left.left = new Node(7); 
		root.right = new Node(9); 
		root.right.left = new Node(15); 
		root.right.right = new Node(8); 
	
		System.out.print( "Inorder traversal before insertion:"); 
		inorder(root); 
	
		int key = 12; 
		insert(root, key); 
	
		System.out.print("\nInorder traversal after insertion:"); 
		inorder(root); 
	} 
}

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

Inorder traversal before insertion: 7 11 10 15 9 8
Inorder traversal after insertion: 7 11 12 10 15 9 8

المصادر

• صفحة Binary Tree | Set 1 (Introduction)‎ في توثيق بنى المعطيات في موقع GeeksforGeeks.
• صفحة Binary Tree | Set 2 (Properties)‎ في توثيق بنى المعطيات في موقع GeeksforGeeks.
• صفحة Binary Tree | Set 3 (Types of Binary Tree)‎ في توثيق بنى المعطيات في موقع GeeksforGeeks.
• صفحة Deletion in a Binary Tree في توثيق بنى المعطيات في موقع GeeksforGeeks.