شجرة ثلاثية

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

تُستخدم الأشجار الثلاثية لتنفيذ أشجار البحث الثلاثية والأكوام الثلاثية .

• الحافة الموجهة - الرابط من الأصل إلى الفرع.
• الجذر - العقدة التي ليس لها آباء. يوجد على الأكثر عقدة جذر واحدة في الشجرة الجذرية.
• العقدة الورقية - أي عقدة ليس لها أبناء.
• العقدة الأبوية - أي عقدة متصلة بحافة موجهة بعقدتها الفرعية أو عقدها الفرعية.
• العقدة الفرعية - أي عقدة متصلة بعقدة أصلية بواسطة حافة موجهة.
• العمق - طول المسار من الجذر إلى العقدة. تُسمى مجموعة جميع العقد عند عمق معين أحيانًا مستوى من مستويات الشجرة. تقع عقدة الجذر عند العمق صفر.
• الارتفاع - طول المسار من الجذر إلى أعمق عقدة في الشجرة. الشجرة (ذات الجذر) التي تحتوي على عقدة واحدة فقط (الجذر) يكون ارتفاعها صفرًا. في الرسم التوضيحي، يبلغ ارتفاع الشجرة 2.
• الأشقاء - العقد التي تشترك في نفس العقدة الأبوية.
• تُعتبر العقدة p سلفًا للعقدة q إذا كانت موجودة على المسار من q إلى الجذر. وتُسمى العقدة q حينها سليلًا للعقدة p.
• حجم العقدة هو عدد الفروع التابعة لها، بما في ذلك العقدة نفسها .

• الحد الأقصى لعدد العقد

- يترك${\displaystyle h}$يكون ارتفاع الشجرة الثلاثية.

- يترك${\displaystyle M(h)}$ليكن الحد الأقصى لعدد العقد في شجرة ثلاثية ذات ارتفاع${\displaystyle h}$

ح	م ( ح )
0	1
1	4
2	13
3	40

–${\displaystyle M(h)=1+3+9+\cdots +3^{h}=\sum _{i=0}^{h}3^{i}={\frac {3^{h+1}-1}{2}}}$

– كل شجرة بارتفاع h لديها على الأكثر${\displaystyle {\frac {3^{h+1}-1}{2}}}$العقد.

• إذا تم اعتبار خوارزمية البحث بالعرض أولاً (BFS) للبحث في بنية بيانات الشجرة الثلاثية، فإن :  
  • إذا كانت العقدة${\displaystyle N}$يحتل شجرة${\displaystyle [k]}$ثم يتم تخزين الطفل الأيسر في الشجرة${\displaystyle [3k-1]}$
  • يتم تخزين بيانات الطفل الأوسط في TREE${\displaystyle [3k]}$
  • يتم تخزين الطفل الأيمن في الشجرة${\displaystyle [3k+1]}$

هنا،${\displaystyle [k]}$يشير إلى موضع العقدة بناءً على التسلسل في اجتياز الشجرة باستخدام خيار خوارزمية البحث بالعرض أولاً (BFS).

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

 في / \ كن من / \ / \ كما هو أو \\ \\ \\ / \\ ثم انتقل إلى

يحاول البحث الرقمي تخزين السلاسل حرفًا حرفًا. الصورة التالية عبارة عن شجرة تمثل نفس المجموعة المكونة من 12 كلمة؛

 _ _ _ _ _ _ _ _ _ _ _ _ _ / / / \ \ \ / / / \ \ \ أبهيوت / \ / \ | / | \ /|\ | steyenstfnro كما في يكون بواسطة هو في هو من على أو إلى

تُعرض كل كلمة مُدخلة أسفل العقدة التي تُمثلها. في شجرة تُمثل الكلمات ذات الأحرف الصغيرة، تحتوي كل عقدة على 26 فرعًا. عمليات البحث سريعة جدًا: يبدأ البحث عن "IS" من الجذر، ثم يسلك فرع "I"، ثم فرع "S"، وينتهي عند العقدة المطلوبة. عند كل عقدة، يتم الوصول إلى عنصر من عناصر المصفوفة، والتحقق من قيمته (ليست فارغة)، ثم يسلك أحد الفروع.

 أنا / | \ / | \ bso / | \ / \ | \ aehntnt | \ | / \ | سيفرو \ ت

الصورة أعلاه هي شجرة بحث ثلاثية متوازنة لنفس مجموعة الكلمات الاثنتي عشرة. تُعرض المؤشرات الدنيا والعليا بخطوط مائلة، بينما تُعرض المؤشرات المتساوية بخطوط عمودية. يبدأ البحث عن الكلمة "IS" من الجذر، وينتقل نزولًا عبر الفرع المتساوي إلى العقدة ذات القيمة "S"، ويتوقف هناك بعد مقارنتين. أما البحث عن "AX" فيُجري ثلاث مقارنات مع الحرف الأول "A" ومقارنتين مع الحرف الثاني "X" قبل الإبلاغ عن أن الكلمة غير موجودة في الشجرة. ^{[ 1 ]}

• شجرة البحث الثلاثية
• شجرة ثنائية ثلاثية
• كومة ثلاثية
• تم وصف شجرتين ثلاثيتين لانهائيتين تحتويان على جميع الثلاثيات الفيثاغورية الأولية في قسم "شجرة الثلاثيات الفيثاغورية الأولية " وفي قسم "صيغ توليد الثلاثيات الفيثاغورية" . تحتوي العقدة الجذرية في كلتا الشجرتين على الثلاثية [3، 4، 5]. ^{[ 2 ]}
• اختيار الجذر الأمثل : يقترح هايز أن نظام الشجرة الثلاثية هو عامل التفرع الأمثل لنظام قائمة الهاتف

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