أنواع الأشجار في هيكل البيانات

قبل أن ننطرق لموضوع أنواع الأشجار في هيكل البيانات، يجب نتعلم كيف يتم وضع الشجرة في الذاكرة فلهذا ندرس تنفيذ هيكل البيانات الشجري.

تنفيذ هيكل البيانات الشجري

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

وفقًا للبيان أعلاه ، يمكن تعريف كل عقدة على أنها فئة في البرمجة:

Class Node {
    public int value;
    public Node left;
    public Node right; 
}

في الكود أعلاه ، يشير left  إلى عقدة (كائن Node) تكون قيمتها أقل من قيمة العقدة الحالية. وبالمثل ، يشير right  إلى العقدة (كائن Node) التي تكون قيمتها أكبر من العقدة الحالية. هنا تتعلق المناقشة بالشجرة الثنائية. الشجرة الثنائية لها فرعان في معظم الحالات. أي أن العقدة بها صفر أو فرع واحد أو فرعين كحد أقصى. يمكن أن تحتوي الشجرة العامة (Generic Tree) على أكثر من فرعين.

ما هي أنواع الأشجار في هيكل البيانات؟

في وصف تطبيقات هيكل بيانات الشجرة الذي تم سردها في المقال السابق، تم ذكر بعض أنواع الأشجار في بنية البيانات ضمنيًا. في هذا القسم ، حاولنا تقديم كل نوع من أنواع الهياكل الشجرية بشكل شامل قدر الإمكان. أولاً ، يتم سرد كل نوع من أنواع الشجرة في بنية البيانات أدناه:

• شجرة عامة (Generic)
• شجرة ثنائية (Binary)
• شجرة بحث ثنائية (Binary Search)
• شجرة AVL
• شجرة حمراء سوداء (Red–black)
• شجرة سبلاي (Splay Tree)
• شجرة Treap

الشجرة العامة في هيكل البيانات

“الشجرة العامة” (Generic Tree) هي نوع واحد من الأشجار في هيكل البيانات ، حيث لا يوجد حد لعدد العقد في هيكلها الهرمي. كل عقدة لديها من صفر إلى n العقد. تبدأ الشجرة العامة بعقدة جذر ويشكل أبناء العقدة الأصلية شجرة فرعية عامة أخرى. ومن ثم ، فإن كل عقدة جذر عبارة عن شجرة فرعية ، أي في الشجرة العامة ، يوجد عدد n من الأشجار الفرعية. جميع الأشجار الفرعية موجودة في شجرة عامة غير مرتبة.

ميزات الشجرة العامة في هيكل البيانات

فيما يلي خصائص هذا النوع من الأشجار:

• تتبع الشجرة العامة جميع خصائص هيكل بيانات الشجرة.
• يمكن أن تحتوي العقدة على أي عدد من العقد.

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

“الشجرة الثنائية” (Binary) هي نوع واحد من الأشجار في هيكل البيانات حيث يمكن أن تحتوي كل عقدة على فرعين كحد أقصى (أي 0 ، 1 أو 2 فروع). لا توجد قيود على بيانات الفرع الأيسر أو الفرع الأيمن.

ميزات الشجرة الثنائية في هيكل البيانات

هذه الميزات مذكورة أدناه:

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

شجرة البحث الثنائية في هيكل البيانات

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

ميزات الشجرة الثنائية في هيكل البيانات

خصائص الشجرة الثنائية هي كما يلي:

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

شجرة AVL في هيكل البيانات

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

يتميز هذا التوازن بشيء يسمى عامل التوازن. تعتبر الشجرة شجرة AVL تفي بخصائص شجرة البحث الثنائية وعامل التوازن. يعتبر الفرق بين ارتفاع الشجرة الفرعية اليسرى والشجرة الفرعية اليمنى بمثابة ارتفاع شجرة AVL. يجب أن تكون قيمة عامل الموازنة 0 و 1 و -1 لكل عقدة في شجرة AVL.

ميزات شجرة AVL في بنية البيانات

يتم سرد كل من خصائص شجرة AVL في هيكل البيانات أدناه:

• يتبع AVL أيضًا جميع خصائص هيكل بيانات الشجرة.
• إنها موازنة ذاتية (Self-Balancing).
• تخزن كل عقدة قيمة تسمى عامل التوازن ، وهو فرق الارتفاع بين الشجرة الفرعية اليسرى والشجرة الفرعية اليمنى.
• تحتوي جميع العقد في شجرة AVL على “عامل توازن” (Balance Factor) بقيم -1 أو 0 أو 1.

شجرة حمراء-سوداء في هيكل البيانات

“Red-Black Tree” هو نوع آخر من الأشجار في هيكل البيانات ، وهو عبارة عن شجرة بحث ثنائية ذاتية التوازن تكون فيها كل عقدة إما حمراء أو سوداء. يتم استخدام لون العقد لضمان بقاء الشجرة متوازنة تقريبًا أثناء عمليات الإدراج والحذف.
الفرق الوحيد بين الشجرة ذات اللون الأحمر والأسود وشجرة AVL هو أننا لا نعرف عدد الدورات اللازمة لتحقيق التوازن بين الشجرة. ولكن في الشجرة ذات اللون الأحمر والأسود ، يلزم إجراء دورتين على الأكثر لموازنة الشجرة. يحتوي هذا النوع من الشجرة على جزء صغير يشير إلى اللون الأحمر أو الأسود للعقدة لضمان توازن الشجرة.

خصائص الشجرة الحمراء-السوداء في هيكل البيانات

فيما يلي خصائص الشجرة ذات اللون الأحمر والأسود في هيكل البيانات:

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

شجرة splay في هيكل البيانات

شجرة Splay هي نوع آخر من الأشجار في هيكل البيانات. هذه الشجرة هي شجرة ثنائية ذاتية التوازن.

ميزات شجرة Splay في هيكل البيانات

يتم سرد خصائص شجرة Splay في هيكل البيانات أدناه:

• يتبع خصائص هيكل بيانات الشجرة الثنائية.
• إنها موازنة ذاتية.
• من الأسرع إعادة الوصول إلى العناصر التي تم الوصول إليها مؤخرًا.
• بعد إجراء عمليات مثل عمليات الإدراج والحذف ، يتم تشغيل شجرة Splay وتبدأ في إجراء عمليات «Splaying» ، والتي تعيد ترتيب الشجرة بحيث يتم وضع عناصر معينة في جذر الشجرة.

شجرة Treap في هيكل البيانات

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

ميزات شجرة Treap في هيكل البيانات

خصائص شجرة Treap في هيكل البيانات هي كما يلي:

• كل عقدة لها قيمتان ؛ مفتاح وأولوية.
• يتبع هذا النوع من الشجرة خصائص شجرة البحث الثنائية.
• أولوية شجرة Treap يتبع خاصية الهرم.

التنقل (Traversal) الشجري في هياكل البيانات

التنقل الشجري هو عملية زيارة كل عقدة وطباعة قيمتها. هناك ثلاث طرق للتنقل في هيكل بيانات الشجرة:

1. “التنقل بالترتيب” (In-Order Traversal)
2. “تنقل بترتيب مسبق” (Pre-Order Traversal)
3. “تنقل بترتيب لاحق” (Post-Order Traversal)

في ما يلي ، تتم مناقشة كل من طرق التنقل الثلاثة هذه في هيكل الشجرة بشكل منفصل.

التنقل الشجري حسب طريقة بالترتيب

في “التنقل بالترتيب” (In-Order Traversal)، تتم زيارة الشجرة الفرعية اليسرى أولاً ، ثم الجذر ، ثم الشجرة الفرعية اليمنى.

خوارزمية التنقل بالترتيب في الشجرة

كل خطوة من خطوات تنقل الشجرة في طريقة In-Order هي كما يلي:

الخطوة 1: يعبر بشكل متكرر الشجرة الفرعية اليسرى.
الخطوة 2: تمت زيارة عقدة الجذر.
والخطوة 3: يتنقل بشكل متكرر إلى أسفل الشجرة على اليمين.

التنقل الشجري حسب طريقة بالترتيب المسبق

في “تنقل بترتيب مسبق” (Pre-Order Traversal)، تتم زيارة عقدة الجذر أولاً ، ثم الشجرة الفرعية اليسرى وأخيراً الشجرة الفرعية اليمنى.

خوارزمية التنقل بالترتيب المسبق في الشجرة

فيما يلي خطوات تنفيذ خوارزمية تنقل الشجرة بطريقة Pre-Order:

الخطوة 1: تمت زيارة عقدة الجذر.
الخطوة 2: يعبر بشكل متكرر الشجرة الفرعية اليسرى.
والخطوة 3: يتنقل بشكل متكرر إلى أسفل الشجرة على اليمين.

التنقل الشجري حسب طريقة بالترتيب العكسي

في “تنقل بترتيب لاحق أو العكسي” (Post-Order Traversal)، تتم زيارة الشجرة الفرعية اليسرى أولاً ، ثم الشجرة الفرعية اليمنى وأخيرًا العقدة الجذرية.

خوارزمية التنقل بالترتيب اللاحق في الشجرة

فيما يلي خطوات تنقل الشجرة بطريقة الترتيب اللاحق:

الخطوة 1: تنقل بشكل متكرر في الشجرة الفرعية اليسرى.
الخطوة 2: قم بزيارة عقدة الجذر.
والخطوة 3: تنقل بشكل متكرر في الشجرة الفرعية اليمنى.

الأسئلة الشائعة حول هيكل بيانات الشجرة

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

لماذا تعتبر الشجرة هيكل بيانات غير خطية؟

هيكل بيانات الشجرة غير خطي لأنه لا يتم تخزينه بالتسلسل. تحتوي الشجرة على هيكل هرمي لأن عناصر الشجرة مرتبة على عدة مستويات. تُعرف أعلى عقدة في هيكل بيانات الشجرة بالعقدة الجذرية. تحتوي كل عقدة على بيانات وبيانات يمكن أن تكون من أي نوع.

ما فائدة هيكل بيانات الشجرة في الحياة الواقعية؟

قد تستخدم قواعد البيانات هيكل بيانات الشجرة للفهرسة (Indexing). تستخدم خوادم أسماء المجالات (DNS) أيضًا هياكل شجرة. يستخدم BST في رسومات الحاسوب.

ما هي الشجرة المثالية؟

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

لماذا تستخدم الشجرة في هيكل البيانات؟

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

ما هي خصائص الشجرة في هيكل البيانات؟

الشجرة عبارة عن رسم بياني غير مدور ويوجد مسار فريد بين كل زوج من رؤوسها. تحتوي الشجرة التي تحتوي على عدد N من الرؤوس على حواف (N-1). يسمى الرأس الذي تكون درجته صفر جذر الشجرة.

ما هي العمليات التي يمكن القيام بها على الشجرة؟

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

ما هي أنواع الأشجار في هيكل البيانات وما هي استخداماتها؟

يمكن استخدام شجرة البحث الثنائية للبحث عن عنصر في مجموعة من العناصر. تستخدم أشجار الهرم لفرز الهرم. تستخدم أجهزة التوجيه الحديثة نوعًا من الشجرة تسمى “T