نقرأ هياكل البيانات الخطية مثل المصفوفة والقائمة المرتبطة والمكدس وقائمة الانتظار حيث يتم ترتيب جميع العناصر بطريقة تسلسلية. يتم استخدام هياكل البيانات المختلفة لأنواع مختلفة من البيانات.
dateformat.format
يتم أخذ بعض العوامل في الاعتبار عند اختيار بنية البيانات:
شجرة يعد أيضًا أحد هياكل البيانات التي تمثل البيانات الهرمية. لنفترض أننا نريد إظهار الموظفين ومناصبهم بشكل هرمي فيمكن تمثيله كما هو موضح أدناه:
الشجرة أعلاه تظهر التسلسل الهرمي التنظيمي من بعض الشركات. في الهيكل أعلاه، جون هل المدير التنفيذي للشركة، وجون لديه تقريران مباشران تم تسميتهما باسم ستيف و روهان . ستيف لديه ثلاثة تقارير مباشرة مسماة لي، بوب، إيلا أين ستيف هو مدير. لدى بوب تقريران مباشران تم تسميتهما سوف و إيما . إيما لديه تقريرين مباشرين اسمه توم و راج . توم لديه تقرير مباشر واحد اسمه فاتورة . يُعرف هذا الهيكل المنطقي الخاص باسم أ شجرة . هيكلها مشابه للشجرة الحقيقية، لذلك سميت أ شجرة . في هذا الهيكل، جذر في الأعلى، وفروعه تتحرك في اتجاه الأسفل. لذلك، يمكننا القول أن بنية بيانات الشجرة هي وسيلة فعالة لتخزين البيانات بطريقة هرمية.
دعونا نفهم بعض النقاط الرئيسية في بنية بيانات الشجرة.
- يتم تعريف بنية بيانات الشجرة على أنها مجموعة من الكائنات أو الكيانات المعروفة باسم العقد المرتبطة معًا لتمثيل أو محاكاة التسلسل الهرمي.
- بنية البيانات الشجرية هي بنية بيانات غير خطية لأنها لا تخزن بطريقة تسلسلية. إنه هيكل هرمي حيث يتم ترتيب العناصر في الشجرة في مستويات متعددة.
- في بنية بيانات الشجرة، تُعرف العقدة العليا بالعقدة الجذرية. تحتوي كل عقدة على بعض البيانات، ويمكن أن تكون البيانات من أي نوع. في بنية الشجرة أعلاه، تحتوي العقدة على اسم الموظف، وبالتالي فإن نوع البيانات سيكون سلسلة.
- تحتوي كل عقدة على بعض البيانات ورابط أو مرجع للعقد الأخرى التي يمكن تسميتها بالأبناء.
بعض المصطلحات الأساسية المستخدمة في بنية بيانات الشجرة.
دعونا نفكر في بنية الشجرة، كما هو موضح أدناه:
في البنية المذكورة أعلاه، يتم تسمية كل عقدة برقم معين. يُعرف كل سهم موضح في الشكل أعلاه باسم a وصلة بين العقدتين.
خصائص بنية بيانات الشجرة
استنادا إلى خصائص بنية بيانات الشجرة، يتم تصنيف الأشجار إلى فئات مختلفة.
تنفيذ الشجرة
يمكن إنشاء بنية بيانات الشجرة عن طريق إنشاء العقد ديناميكيًا بمساعدة المؤشرات. يمكن تمثيل الشجرة الموجودة في الذاكرة كما هو موضح أدناه:
يوضح الشكل أعلاه تمثيل بنية بيانات الشجرة في الذاكرة. في البنية المذكورة أعلاه، تحتوي العقدة على ثلاثة حقول. الحقل الثاني يخزن البيانات. يخزن الحقل الأول عنوان الطفل الأيسر، ويخزن الحقل الثالث عنوان الطفل الأيمن.
في البرمجة، يمكن تعريف بنية العقدة على النحو التالي:
struct node { int data; struct node *left; struct node *right; } لا يمكن تعريف البنية المذكورة أعلاه إلا للأشجار الثنائية لأن الشجرة الثنائية يمكن أن تحتوي على طفلين كحد أقصى، ويمكن أن تحتوي الأشجار العامة على أكثر من طفلين. سيكون هيكل العقدة للأشجار العامة مختلفًا مقارنةً بالشجرة الثنائية.
تطبيقات الأشجار
وفيما يلي تطبيقات الأشجار:
أنواع بنية بيانات الشجرة
فيما يلي أنواع بنية بيانات الشجرة:
يمكن أن يكون هناك ن عدد الأشجار الفرعية في الشجرة العامة في الشجرة العامة، تكون الأشجار الفرعية غير مرتبة حيث لا يمكن ترتيب العقد الموجودة في الشجرة الفرعية.
كل شجرة غير فارغة لها حافة سفلية، وهذه الحواف متصلة بالعقد المعروفة باسم العقد الفرعية . تتم تسمية العقدة الجذرية بالمستوى 0. وتعرف العقد التي لها نفس الأصل باسم إخوة .
لمعرفة المزيد عن الشجرة الثنائية، انقر على الرابط أدناه:
https://www.javatpoint.com/binary-tree
يجب أن تحتوي كل عقدة في الشجرة الفرعية اليسرى على قيمة أقل من قيمة العقدة الجذرية، ويجب أن تكون قيمة كل عقدة في الشجرة الفرعية اليمنى أكبر من قيمة العقدة الجذرية.
يمكن إنشاء عقدة بمساعدة نوع بيانات محدد من قبل المستخدم يعرف باسم هيكل, كما هو مبين أدناه:
struct node { int data; struct node *left; struct node *right; } ما ورد أعلاه هو بنية العقدة مع ثلاثة حقول: حقل البيانات، والحقل الثاني هو المؤشر الأيسر لنوع العقدة، والحقل الثالث هو المؤشر الأيمن لنوع العقدة.
لمعرفة المزيد عن شجرة البحث الثنائية، انقر على الرابط أدناه:
https://www.javatpoint.com/binary-search-tree
وهي أحد أنواع الشجرة الثنائية، أو يمكننا القول أنها نسخة مختلفة من شجرة البحث الثنائية. شجرة AVL تلبي خاصية شجرة ثنائية وكذلك من شجرة البحث الثنائية . إنها شجرة بحث ثنائية ذاتية التوازن تم اختراعها بواسطة أديلسون فيلسكي لينداس . هنا، التوازن الذاتي يعني موازنة ارتفاعات الشجرة الفرعية اليسرى والشجرة الفرعية اليمنى. ويتم قياس هذا التوازن من حيث عامل التوازن .
يمكننا اعتبار الشجرة بمثابة شجرة AVL إذا كانت الشجرة تخضع لشجرة البحث الثنائية بالإضافة إلى عامل التوازن. يمكن تعريف عامل التوازن بأنه الفرق بين ارتفاع الشجرة الفرعية اليسرى وارتفاع الشجرة الفرعية اليمنى . يجب أن تكون قيمة عامل الموازنة إما 0 أو -1 أو 1؛ لذلك، يجب أن يكون لكل عقدة في شجرة AVL قيمة عامل الموازنة إما 0 أو -1 أو 1.
لمعرفة المزيد عن شجرة AVL، انقر على الرابط أدناه:
https://www.javatpoint.com/avl-tree
الشجرة الحمراء السوداء هي شجرة البحث الثنائية. الشرط الأساسي للشجرة ذات اللون الأحمر والأسود هو أن نعرف شيئًا عن شجرة البحث الثنائية. في شجرة البحث الثنائية، يجب أن تكون قيمة الشجرة الفرعية اليسرى أقل من قيمة تلك العقدة، ويجب أن تكون قيمة الشجرة الفرعية اليمنى أكبر من قيمة تلك العقدة. كما نعلم أن التعقيد الزمني للبحث الثنائي في الحالة المتوسطة هو السجل2n، أفضل حالة هي O(1)، وأسوأ حالة هي O(n).
عند إجراء أي عملية على الشجرة، نريد أن تكون شجرتنا متوازنة بحيث تستغرق جميع العمليات مثل البحث والإدراج والحذف وما إلى ذلك وقتًا أقل، وستكون جميع هذه العمليات ذات تعقيد زمني قدره سجل2ن.
الشجرة الحمراء السوداء هي شجرة بحث ثنائية ذاتية التوازن. شجرة AVL هي أيضًا شجرة بحث ثنائية لموازنة الارتفاع لماذا نحتاج إلى شجرة حمراء وسوداء . في شجرة AVL، لا نعرف عدد الدورات المطلوبة لموازنة الشجرة، ولكن في الشجرة ذات اللون الأحمر والأسود، يلزم دورتان كحد أقصى لموازنة الشجرة. يحتوي على بت إضافي يمثل اللون الأحمر أو الأسود للعقدة لضمان توازن الشجرة.
إن بنية بيانات شجرة التباعد هي أيضًا شجرة بحث ثنائية يتم فيها وضع العنصر الذي تم الوصول إليه مؤخرًا في موضع جذر الشجرة عن طريق إجراء بعض عمليات التدوير. هنا، التفلطح يعني العقدة التي تم الوصول إليها مؤخرا. إنها التوازن الذاتي شجرة البحث الثنائية ليس لها شرط توازن صريح مثل AVL شجرة.
قد يكون من المحتمل أن يكون ارتفاع شجرة التباعد غير متوازن، أي أن ارتفاع كل من الشجرتين الفرعيتين اليمنى واليسرى قد يختلف، ولكن العمليات في شجرة التباعد تأخذ ترتيبًا هادئ الوقت حيث ن هو عدد العقد.
شجرة التباعد هي شجرة متوازنة ولكن لا يمكن اعتبارها شجرة متوازنة الارتفاع لأنه بعد كل عملية يتم إجراء دوران مما يؤدي إلى شجرة متوازنة.
جاءت بنية بيانات Treap من بنية بيانات الشجرة والكومة. لذلك، فهو يشتمل على خصائص هياكل بيانات الشجرة والكومة. في شجرة البحث الثنائية، يجب أن تكون كل عقدة على الشجرة الفرعية اليسرى مساوية أو أقل من قيمة العقدة الجذرية ويجب أن تكون كل عقدة على الشجرة الفرعية اليمنى مساوية أو أكبر من قيمة العقدة الجذرية. في بنية بيانات الكومة، تحتوي كل من الشجرتين الفرعيتين اليمنى واليسرى على مفاتيح أكبر من الجذر؛ لذلك يمكننا القول أن العقدة الجذرية تحتوي على أقل قيمة.
في بنية بيانات الخطوة، تحتوي كل عقدة على كليهما مفتاح و أولوية حيث يتم اشتقاق المفتاح من شجرة البحث الثنائية ويتم اشتقاق الأولوية من بنية بيانات الكومة.
ال فخ تتبع بنية البيانات خاصيتين مذكورتين أدناه:
- الطفل الأيمن للعقدة> = العقدة الحالية والطفل الأيسر للعقدة<=current node (binary tree)< li>
- يجب أن يكون أبناء أي شجرة فرعية أكبر من العقدة (الكومة)
B-tree متوازن م-واي شجرة حيث م يحدد ترتيب الشجرة. حتى الآن، نقرأ أن العقدة تحتوي على مفتاح واحد فقط ولكن يمكن أن تحتوي شجرة b على أكثر من مفتاح واحد، وأكثر من طفلين. يحافظ دائمًا على البيانات التي تم فرزها. في الشجرة الثنائية، من الممكن أن تكون العقد الورقية على مستويات مختلفة، ولكن في الشجرة b، يجب أن تكون جميع العقد الورقية على نفس المستوى.
إذا كان الترتيب m فإن العقدة لها الخصائص التالية:
- يمكن أن تحتوي كل عقدة في شجرة b على الحد الأقصى م أطفال
- بالنسبة للحد الأدنى من الأطفال، تحتوي العقدة الورقية على 0 أطفال، والعقدة الجذرية بها طفلان على الأقل، والعقدة الداخلية لها حد أدنى يبلغ م/2 أطفال. على سبيل المثال، قيمة m هي 5 مما يعني أن العقدة يمكن أن تحتوي على 5 أطفال والعقد الداخلية يمكن أن تحتوي على 3 أطفال كحد أقصى.
- تحتوي كل عقدة على مفاتيح بحد أقصى (m-1).
يجب أن تحتوي العقدة الجذرية على مفتاح واحد على الأقل ويجب أن تحتوي جميع العقد الأخرى على الأقل سقف م/2 ناقص 1 مفاتيح.