Algorithms/tree sort

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

خطوات الخوارزمية

1. جلب العناصر من المصفوفة المدخلة.
2. إنشاء شجرة بحث ثنائية باستخدام عناصر المصفوفة المدخلة.
3. تنفيذ عملية تنقل وسطي على شجرة البحث ثنائية للحصول على الترتيب المطلوب.

تنفيذ الخوارزمية

تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:

• C++‎:

#include<bits/stdc++.h> 

using namespace std; 

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

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

// تخزّن هذه الدالة نتيجة التنقل الوسطي المنفّذ على شجرة البحث الثنائية في المصفوفة المعطاة
void storeSorted(Node *root, int arr[], int &i) 
{ 
	if (root != NULL) 
	{ 
		storeSorted(root->left, arr, i); 
		arr[i++] = root->key; 
		storeSorted(root->right, arr, i); 
	} 
} 

// دالة مساعدة لإدراج عقدة جديدة 
// مع المفتاح المعطى في شجرة البحث الثنائية
Node* insert(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; 
} 

// الدالة المسؤولة عن ترتيب المصفوفة المعطاة
// باستخدام خوارزمية الترتيب بالشجرة
void treeSort(int arr[], int n) 
{ 
	struct Node *root = NULL; 

	// بناء شجرة البحث الثنائية
	root = insert(root, arr[0]); 
	for (int i=1; i<n; i++) 
		insert(root, arr[i]); 

	// تخزين نتيجة التنقل الوسطي في شجرة البحث الثنائية
	// arr[] في المصفوفة
	int i = 0; 
	storeSorted(root, arr, i); 
} 

// اختبار الدوال السابقة
int main() 
{ 
	//إنشاء المصفوفة المدخلة
	int arr[] = {5, 4, 7, 2, 11}; 
	int n = sizeof(arr)/sizeof(arr[0]); 

	treeSort(arr, n); 

		for (int i=0; i<n; i++) 
	cout << arr[i] << " "; 

	return 0; 
}

• بايثون:

• جافا:

class GFG 
{ 

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

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

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

	GFG() 
	{ 
		root = null; 
	} 

	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; 
	} 
	
	// ينفذ التابع عملية تنقل وسطي في شجرة البحث الثنائية
	void inorderRec(Node root) 
	{ 
		if (root != null) 
		{ 
			inorderRec(root.left); 
			System.out.print(root.key + " "); 
			inorderRec(root.right); 
		} 
	} 
	void treeins(int arr[]) 
	{ 
		for(int i = 0; i < arr.length; i++) 
		{ 
			insert(arr[i]); 
		} 
		
	} 

	// اختبار التوابع السابقة
	public static void main(String[] args) 
	{ 
		GFG tree = new GFG(); 
		int arr[] = {5, 4, 7, 2, 11}; 
		tree.treeins(arr); 
		tree.inorderRec(tree.root); 
	} 
}

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

Output:
2 4 5 7 11

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

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

ويبلغ التعقيد الزمني لهذه الخوارزمية في الحالة السوأى المقدار O(n^2)‎. ويمكن تحسين التعقيد الزمني في هذه الحالة باستخدام شجرة البحث الثنائية ذاتية التوازن self-balancing مثل شجرة أحمر أسود وشجرة AVL. يؤدي استخدام هذا النوع من الأشجار إلى تخفيض التعقيد الزمني للحالة السوأى إلى المقدار O(n log n)‎.

تحتاج هذه الخوارزمية إلى مساحة ساندة مقدارة O(n)‎.

مصادر

• صفحة Tree Sort في توثيق الخوارزميات في موقع GeeksforGeeks.