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

في علم الحاسوب ، الشجرة الثنائية هي بنية بيانات شجرية، حيث يحتوي كل عقدة على طفلين على الأكثر ، يُشار إليهما بالطفل الأيسر والطفل الأيمن . أي أنها شجرة من الرتبة k حيث $k = 2.$ ويمكن تعريفها تعريفًا تكراريًا باستخدام نظرية المجموعات ، حيث تُعرَّف الشجرة الثنائية بأنها ثلاثية ( L , S , R ) ، حيث L و R شجرتان ثنائيتان أو المجموعة الفارغة ، و S مجموعة أحادية (مجموعة مكونة من عنصر واحد) تحتوي على الجذر. ^{[ 1 ]}^{[ 2 ]}

من منظور نظرية الرسوم البيانية ، تُعرف الأشجار الثنائية، كما هو مُعرّف هنا، بأنها أشجار متفرعة . ^{[ 3 ]} وبالتالي، يُمكن تسمية الشجرة الثنائية أيضًا بالشجرة المتفرعة ، ^{[ 3 ]} وهو مصطلح ظهر في بعض كتب البرمجة المبكرة ^{[ 4 ]} قبل شيوع مصطلحات علوم الحاسوب الحديثة. من الممكن أيضًا تفسير الشجرة الثنائية على أنها رسم بياني غير موجه ، بدلًا من رسم بياني موجه ، وفي هذه الحالة تكون الشجرة الثنائية شجرة مُرتبة ذات جذر . ^[⁵^] يستخدم بعض المؤلفين مصطلح "شجرة ثنائية ذات جذر" بدلًا من "شجرة ثنائية" للتأكيد على أن الشجرة ذات جذر، ولكن كما هو مُعرّف أعلاه، فإن الشجرة الثنائية تكون دائمًا ذات جذر. ^[⁶^]

في الرياضيات، يختلف تعريف الشجرة الثنائية اختلافًا كبيرًا بين الباحثين. فبعضهم يستخدم التعريف الشائع في علوم الحاسوب، ^{[ 7 ]} بينما يُعرّفها آخرون بأنها كل شجرة غير طرفية لها فرعان فقط، ولا يُحددون بالضرورة الفرعين الأيمن والأيسر. ^{[ 8 ]}

في مجال الحوسبة، يمكن استخدام الأشجار الثنائية بطريقتين مختلفتين تمامًا:

أولًا، كوسيلة للوصول إلى العقد بناءً على قيمة أو تصنيف مرتبط بكل عقدة. ^{[ 9 ]} تُستخدم الأشجار الثنائية المصنفة بهذه الطريقة لتنفيذ أشجار البحث الثنائية والأكوام الثنائية ، وتُستخدم للبحث والفرز بكفاءة. يُعدّ تصنيف العقد غير الجذرية كعقدة فرعية يسرى أو يمنى، حتى في حالة وجود عقدة فرعية واحدة فقط ، أمرًا مهمًا في بعض هذه التطبيقات، وخاصةً في أشجار البحث الثنائية. ^{[ 10 ]} مع ذلك، فإن ترتيب عقد معينة في الشجرة ليس جزءًا من المعلومات المفاهيمية. على سبيل المثال، في شجرة بحث ثنائية عادية، يعتمد موضع العقد بشكل شبه كامل على ترتيب إضافتها، ويمكن إعادة ترتيبها (على سبيل المثال عن طريق الموازنة ) دون تغيير معناها.
ثانيًا، كتمثيل للبيانات ذات بنية تشعبية ذات صلة. في مثل هذه الحالات، يُعدّ الترتيب المحدد للعُقد أسفل و/أو على يسار أو يمين عُقد أخرى جزءًا من المعلومات (أي أن تغييره سيغير المعنى). ومن الأمثلة الشائعة على ذلك ترميز هوفمان والمخططات التفرعية . ويُعدّ التقسيم اليومي للوثائق إلى فصول وأقسام وفقرات، وما إلى ذلك، مثالًا مشابهًا باستخدام الأشجار من الرتبة n بدلًا من الأشجار الثنائية.

التعريفات

التعريف التكراري

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

قد يكون النهج البسيط وغير الرسمي لوصف الشجرة الثنائية كما يلي:

تحتوي الشجرة الثنائية على عقدة جذرية، والتي تحتوي على 0 أو 2 عقدة فرعية (والتي بدورها قد تحتوي على 0 أو 2 عقد فرعية، وهكذا).

بصورة أكثر رسمية:

(الحالة الأساسية) توجد شجرة كاملة تتكون من عقدة واحدة؛
(خطوة تكرارية) إذا كانت T1 _و T2 _شجرتين ثنائيتين كاملتين، لا تشتركان في أي عقدة، وكانت r عقدة لا تنتمي إلى T1 _أو T2 _، فإن الثلاثية المرتبة (r، T1 _، T2 ₎ هي شجرة ثنائية كاملة. ^{[ 11 ]}

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

تعريف الشجرة الموسعة المتكررة

يبدأ تعريف الشجرة الموسع بافتراض أن الشجرة يمكن أن تكون فارغة.

(الحالة الأساسية) مجموعة العقد الفارغة هي شجرة ثنائية موسعة.
(خطوة تكرارية) إذا كانت T1 _و T2 _شجرتين ثنائيتين ممتدتين، لا تشتركان في أي عقدة، وكانت r عقدة لا تنتمي إلى أي منهما، فإن الثلاثية المرتبة (r, T1 _, T2 ₎ هي شجرة ثنائية ممتدة. ^{[ 12 ]}^{[ 11 ]}

ولإكمال التعريف من وجهة نظر الرسم البياني، ينبغي توسيع كلا تعريفَي الشجرة بتعريف لمجموعات الفروع المقابلة. وبشكل غير رسمي، يمكن وصف مجموعة الفروع بأنها مجموعة جميع الأزواج المرتبة من العقد (r، s)، حيث $r$ هي عقدة جذرية لأي شجرة فرعية تظهر في التعريف، و $s$ هي عقدة جذرية لأي من شجرتيها الفرعيتين T1 _و T2 ₍ في حال لم تكن الشجرة الفرعية المعنية فارغة).

هناك طريقة أخرى لتصور هذا البناء (وفهم المصطلحات) وهي اعتبار نوع مختلف من العقد بدلاً من المجموعة الفارغة - على سبيل المثال، العقد المربعة إذا كانت العقد العادية عبارة عن دوائر. ^{[ 13 ]}

استخدام مفاهيم نظرية الرسم البياني

الشجرة الثنائية هي شجرة جذرية ، وهي أيضًا شجرة مرتبة (تُعرف أيضًا بالشجرة المستوية)، حيث لا يزيد عدد أبناء كل عقدة فيها عن اثنين. تُضفي الشجرة الجذرية بطبيعتها مفهوم المستويات (المسافة من الجذر)؛ وبالتالي، لكل عقدة، يمكن تعريف مفهوم الأبناء على أنهم العقد المتصلة بها في مستوى أدنى. يُمكّن ترتيب هؤلاء الأبناء (مثلاً، برسمهم على مستوى) من التمييز بين الابن الأيسر والابن الأيمن. ^{[ 14 ]} لكن هذا لا يُميّز بين عقدة لها ابن أيسر فقط، وعقدة لها ابن أيمن فقط.

يمكن التمييز اللازم بتقسيم الحواف أولًا؛ أي تعريف الشجرة الثنائية على أنها ثلاثية (V, E1 _, E2 ₎ ، حيث (V, E1 _∪ E2 ₎ شجرة جذرية (أو ما يُعادلها من التفرع الشجري)، و _E1 ∩ E2 _فارغة ، مع اشتراط أن يكون لكل عقدة j ∈ {1, 2} ابن واحد على الأكثر من Ej. [15] وهناك _طريقة أخرى ^{غير رسمية للتمييز} ، وهي القول، نقلاً عن موسوعة الرياضيات ، أن "لكل عقدة ابنًا أيسر، أو ابنًا أيمن، أو لا هذا ولا ذاك، أو كليهما"، مع تحديد أن هذه "جميعها أشجار ثنائية مختلفة". ^{[ 7 ]}

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

مصطلحات الأشجار ليست موحدة بشكل جيد، وبالتالي قد تختلف بين الأمثلة في الأدبيات المتاحة.

أتحتويالشجرةالثنائية الجذرية على عقدة جذرية، ولكل عقدة طفلان على الأكثر.

أالشجرة الثنائية الكاملة (يُشار إليها أحيانًا بالشجرةالثنائيةالصحيحة،^{أو [ 16 ]} أوالشجرة الثنائيةالصارمة^{) [}¹⁷^]^[¹⁸^] هي شجرة يكون لكل عقدة فيها إما صفر أو اثنين من الأبناء. وهناك طريقة أخرى لتعريف الشجرة الثنائية الكاملة وهيالتعريف التكراري. الشجرة الثنائية الكاملة هي إما:^[¹²^]
- رأس واحد (عقدة واحدة كعقدة جذرية).
- شجرة تحتوي عقدتها الجذرية على شجرتين فرعيتين، وكلاهما شجرتان ثنائيتان كاملتان.
أالشجرة الثنائية الكاملة هي شجرة ثنائية يكون فيها لكل عقدة داخلية ولدان،ولكلورقة نفسالعمقأو نفسالمستوى(يُعرَّف مستوى العقدة بأنه عدد الحواف أو الروابط من العقدة الجذرية إلى العقدة).^{[ 19 ]} الشجرة الثنائية الكاملة هي شجرة ثنائية تامة.
أالشجرة الثنائية الكاملة هي شجرة ثنائية تكون فيها جميع المستويات،باستثناء المستوى الأخير ربما، ممتلئة تمامًا، وتكون جميع العقد في المستوى الأخير في أقصى اليسار. يمكن أن تحتوي على ما بين 1 و2^عقدة في المستوى الأخيرh.^{[ 20 ]} لذلك، تكون الشجرة المثالية دائمًا كاملة، ولكن الشجرة الكاملة ليست مثالية دائمًا. يستخدم بعض المؤلفين مصطلح "كاملة"للإشارة إلىالمثاليةكما هو مُعرَّف أعلاه، وفي هذه الحالة يُطلقون على هذا النوع من الأشجار (مع مستوى أخير قد لا يكون ممتلئًا) اسمالشجرة الثنائيةشبهالكاملة.^[²¹^]^[²²^] يمكن تمثيل الشجرة الثنائية الكاملة بكفاءة باستخدام مصفوفة.^[²⁰^]

الشجرة الثنائية الكاملة اللانهائية هي شجرة ذات ${\aleph _{0}}$ المستويات، حيث يكون عدد العقد الموجودة في كل مستوى d مساويًا لـ 2d . ^العدد الأصلي لمجموعة جميع المستويات هو ${\aleph _{0}}$ (عدد لانهائي قابل للعد). العدد الأصلي لمجموعة جميع المسارات (الأوراق، إن صح التعبير) غير قابل للعد، وله عدد أصلي مماثل لعدد المتصل .
الشجرة الثنائية المتوازنة هي بنية شجرة ثنائية لا يزيد فيها الفرق في ارتفاع الشجرتين الفرعيتين اليمنى واليسرى لكل عقدة (عدد الحواف من العقدة العلوية إلى أبعد عقدة في الشجرة الفرعية) عن 1 (أو لا يزيد الانحراف عن 1). ^{[ 23 ]} يمكن أيضًا النظر في الأشجار الثنائية التي لا تكون فيها أي ورقة أبعد بكثير عن الجذر من أي ورقة أخرى. (تسمح مخططات التوازن المختلفة بتعريفات مختلفة لمصطلح "أبعد بكثير". ^{[ 24 ]} )
الشجرة المنحلة (أو الشاذة ) هي شجرة يكون لكل عقدة أصلية فيها عقدة فرعية واحدة فقط. ^{[ 25 ]} وهذا يعني أن الشجرة ستتصرف كبنية بيانات قائمة مرتبطة . في هذه الحالة، تتضاءل ميزة استخدام الشجرة الثنائية بشكل كبير، لأنها في جوهرها قائمة مرتبطة ذات تعقيد زمني O( n ) ( حيث n هو عدد العقد، وO() هو رمز Big O )، كما أنها تشغل مساحة بيانات أكبر من القائمة المرتبطة نظرًا لوجود مؤشرين لكل عقدة، بينما يُتوقع عادةً أن يكون تعقيد البحث عن البيانات في شجرة ثنائية متوازنة O( _log₂n) .

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

عدد العقد $n$ في شجرة ثنائية كاملة هو على الأقل $2h+1$ وعلى الأكثر $2^{h+1}-1$ (أي عدد العقد في شجرة ثنائية مثالية )، حيث $h$ هو ارتفاع الشجرة. الشجرة التي تتكون من عقدة جذر واحدة فقط يكون ارتفاعها صفرًا. يتم الحصول على أقل عدد من العقد بإضافة عقدتين فرعيتين فقط لكل ارتفاع إضافي. $2h+1$ (1 لحساب العقدة الجذرية). يتم الحصول على الحد الأقصى لعدد العقد عن طريق ملء العقد بالكامل في كل مستوى، أي أنها شجرة مثالية. بالنسبة للشجرة المثالية، يكون عدد العقد هو $1+2+4+\ldots +2^{h}=2^{h+1}-1$ ، حيث أن المساواة الأخيرة مأخوذة من مجموع المتسلسلة الهندسية .
عدد العقد الورقية $l$ في شجرة ثنائية مثالية هو $l=(n+1)/2$ (حيث $n$ هو عدد العقد في الشجرة) لأن $n={{2}^{h+1}}-1$ (باستخدام الخاصية المذكورة أعلاه) وعدد الأوراق هو $2^{h}$ لذا $n=2\cdot {{2}^{h}}-1=2l-1\to l=\left(n+1\right)/2$ وهذا يعني أيضاً أن $n=2l-1$ بالنسبة لارتفاع الشجرة $h$ ، $l=(2^{h+1}-1+1)/2=2^{h}$ .
لأي شجرة ثنائية غير فارغة مع $l$ العقد الورقية و $i_{2}$ العقد من الدرجة 2 (العقد الداخلية ذات عقدتين فرعيتين)، $l=i_{2}+1$ [ ²⁶^] البرهان هو التالي. بالنسبة لشجرة ثنائية مثالية، يكون العدد الإجمالي للعقد ^هو $n=2^{h+1}-1$ (الشجرة الثنائية المثالية هي أيضًا شجرة ثنائية كاملة) و $l=2^{h}$ ، لذا $i=nl=(2^{h+1}-1)-2^{h}=2^{h}-1=l-1\to l=i+1$ لإنشاء شجرة ثنائية كاملة من شجرة ثنائية مثالية، تُزال عقدتان شقيقتان واحدة تلو الأخرى. ينتج عن ذلك إزالة عقدتين ورقيتين، وإزالة عقدة داخلية واحدة، ثم تصبح العقدة الداخلية المُزالة عقدة ورقية. لذا، تُزال عقدة ورقية واحدة وعقدة داخلية واحدة مع كل إزالة لعقدتين شقيقتين. ونتيجة لذلك، $l=i+1$ ينطبق هذا أيضًا على الشجرة الثنائية الكاملة. لإنشاء شجرة ثنائية بعقدة ورقية بدون شقيقها، تُزال عقدة ورقية واحدة من الشجرة الثنائية الكاملة، ثم تُزال عقدة ورقية واحدة، ثم تُزال عقدة داخلية واحدة مع طفلين. $l=i+1$ وينطبق هذا أيضاً. تشمل هذه العلاقة الآن جميع الأشجار الثنائية غير الفارغة.
مع عدد معين من العقد $n$ ، يكون الحد الأدنى لارتفاع الشجرة الممكن هو $h_{\min }=\log _{2}(n+1)-1$ والتي تُعتبر الشجرة معها شجرة كاملة متوازنة أو شجرة مثالية. مع ارتفاع معين $h$ ، لا يمكن أن يتجاوز عدد العقد $2^{h+1}-1$ كما هو الحال مع عدد العقد في الشجرة المثالية. وبالتالي $n\leq 2^{h+1}-1\to h\geq \log _{2}(n+1)-1$ .
يبلغ ارتفاع الشجرة الثنائية ذات $l ورقة على الأقل$ $h_{m}=\log _{2}(l)$ عند ارتفاع معين $h$ ، لا يمكن أن يتجاوز عدد الأوراق عند ذلك الارتفاع $2^{h}$ كما هو الحال مع عدد الأوراق على ارتفاع معين في شجرة مثالية. $l\leq 2^{h}\to h\geq \log _{2}(l)$ .
في شجرة ثنائية غير فارغة، إذا كان $n$ هو العدد الإجمالي للعقد و $e$ هو العدد الإجمالي للحواف، فإن $e=n-1$ وهذا واضح لأن كل عقدة تتطلب حافة واحدة باستثناء العقدة الجذرية.
عدد الروابط الفارغة (أي، الأبناء الغائبين للعقد) في شجرة ثنائية مكونة من $n$ عقدة هو $(n + 1)$ .
عدد العقد الداخلية في شجرة ثنائية كاملة مكونة من $n$ عقدة هو $\lfloor n/2\rfloor$ .

التوافقية

في علم التوافيق ، تُدرس مسألة حساب عدد الأشجار الثنائية الكاملة ذات حجم مُحدد. في هذه الحالة، لا تُرفق أي قيم بعُقد الأشجار (إذ سيؤدي ذلك إلى ضرب عدد الأشجار الممكنة بمعامل يُمكن تحديده بسهولة)، ويتم التمييز بين الأشجار فقط من خلال بنيتها؛ ومع ذلك، يتم التمييز بين الابن الأيسر والابن الأيمن لأي عقدة (إذا كانت شجرتين مختلفتين، فإن تبديلهما سينتج شجرة مختلفة عن الشجرة الأصلية). يُفترض أن حجم الشجرة هو عدد n من العُقد الداخلية (التي لها ابنان)؛ أما العُقد الأخرى فهي عُقد طرفية، ويبلغ عددها $n + 1.$ عدد هذه الأشجار الثنائية ذات الحجم n يساوي عدد طرق وضع سلسلة من $n + 1$ رمزًا (تمثل الأوراق) مفصولة بـ n من المعاملات الثنائية (تمثل العُقد الداخلية) بين قوسين، وذلك لتحديد التعبيرات الفرعية لكل معامل. على سبيل المثال، عندما $n = 3،$ يجب وضع سلسلة مثل $X*X*X*X$ ، وهو أمر ممكن بخمس طرق:

((X*X)*X)*X,\qquad (X*(X*X))*X,\qquad (X*X)*(X*X),\qquad X*((X*X)*X),\qquad X*(X*(X*X)).

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

توجد شجرة ثنائية فريدة بحجم 0 (تتكون من ورقة واحدة)، وتتميز أي شجرة ثنائية أخرى بزوج من أبنائها الأيسر والأيمن؛ إذا كان حجم هذين الابنين i و j على التوالي، فإن حجم الشجرة الكاملة هو $i + j + 1.$ لذلك، فإن العدد $C_{n}$ للوصف التكراري التالي للأشجار الثنائية ذات الحجم n $C_{0}=1$ ، و $\textstyle C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i}$ لأي عدد صحيح موجب n . ويترتب على ذلك أن $C_{n}$ هو العدد الكاتالوني للفهرس n . ^{[ 18 ]}

لا ينبغي الخلط بين السلاسل النصية المذكورة أعلاه والمحاطة بأقواس ومجموعة الكلمات ذات الطول 2^ n في لغة دايك ، والتي تتكون فقط من أقواس بطريقة متوازنة. يخضع عدد هذه السلاسل النصية للوصف التكراري نفسه (تُحدد كل كلمة من كلمات دايك ذات الطول 2^ n بواسطة الكلمة الفرعية دايك المحصورة بين القوسين '(' و')'، بالإضافة إلى الكلمة الفرعية دايك المتبقية بعد القوس الأخير، والتي يبلغ طولها 2 ^i و2^ j، حيث $i + j + 1 = n$ ). وبالتالي، فإن هذا العدد هو أيضًا عدد كاتالان. $C_{n}$ [ ²⁷^] لذلك هناك أيضًا خمس كلمات من لغة ديك بطول 6 ^:

()()(), () (()), (())(), (()()), ((()))

لا تتوافق كلمات دايك هذه مع الأشجار الثنائية بنفس الطريقة. بدلاً من ذلك، ترتبط ببعضها البعض من خلال التناظر التقابلي المُعرَّف بشكل متكرر التالي: كلمة دايك التي تساوي السلسلة الفارغة تُقابل الشجرة الثنائية ذات الحجم 0 والتي تحتوي على ورقة واحدة فقط. يمكن كتابة أي كلمة دايك أخرى على النحو التالي: ( $w_{1}$ ) $w_{2}$ ، أين $w_{1}$ ، $w_{2}$ هي نفسها كلمات ديك (ربما فارغة) حيث تتطابق الأقواس المكتوبة. ثم يتم تعريف التقابل بجعل الكلمات $w_{1}$ و $w_{2}$ تتوافق مع الأشجار الثنائية التي تمثل الأبناء الأيسر والأيمن للجذر.

يمكن أيضًا تعريف التطابق الثنائي على النحو التالي: قم بإحاطة كلمة Dyck بزوج إضافي من الأقواس، بحيث يمكن تفسير النتيجة على أنها تعبير قائمة Lisp (مع القائمة الفارغة () كذرة واحدة فقط)؛ ثم يكون تعبير الزوج المنقط لتلك القائمة المناسبة تعبيرًا مقوسًا بالكامل (مع NIL كرمز و '.' كعامل) يصف الشجرة الثنائية المقابلة (وهي في الواقع التمثيل الداخلي للقائمة المناسبة).

إن القدرة على تمثيل الأشجار الثنائية كسلاسل من الرموز والأقواس تعني أن الأشجار الثنائية يمكن أن تمثل عناصر الصهارة الحرة على مجموعة أحادية.

طرق تخزين الأشجار الثنائية

يمكن إنشاء الأشجار الثنائية من العناصر الأساسية للغة البرمجة بعدة طرق.

العقد والمراجع

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

تُهدر هذه الطريقة لتخزين الأشجار الثنائية قدراً كبيراً من الذاكرة، حيث ستكون المؤشرات فارغة (أو تشير إلى العنصر الحارس) لأكثر من نصف الوقت؛ ويُعد تمثيل الشجرة الثنائية المترابطة بديلاً أكثر تحفظاً . ^{[ 28 ]}

في اللغات التي تستخدم الاتحادات الموسومة ، مثل ML ، غالبًا ما تكون عقدة الشجرة اتحادًا موسومًا لنوعين من العقد، أحدهما ثلاثي يتكون من البيانات والابن الأيسر والابن الأيمن، والآخر عقدة "ورقية" لا تحتوي على بيانات وتعمل بشكل مشابه للقيمة الفارغة في اللغات التي تستخدم المؤشرات. على سبيل المثال، يُعرّف سطر الكود التالي في OCaml (إحدى لهجات ML) شجرة ثنائية تخزن حرفًا في كل عقدة. ^{[ 29 ]}

نوع شجرة_الأحرف = فارغ | عقدة من حرف * شجرة_الأحرف * شجرة_الأحرف

المصفوفات

يمكن أيضًا تخزين الأشجار الثنائية بترتيب البحث العرضي أولًا كبنية بيانات ضمنية في المصفوفات ، وإذا كانت الشجرة ثنائية كاملة، فإن هذه الطريقة لا تهدر أي مساحة. في هذا الترتيب المضغوط، إذا كان للعقدة فهرس i ، فسيتم العثور على أبنائها عند الفهارس i. $2i+1$ (بالنسبة للطفل الأيسر) و $2i+2$ (لليمين)، بينما يوجد الأصل (إن وجد) في الفهرس $\left\lfloor {\frac {i-1}{2}}\right\rfloor$ (بافتراض أن الجذر له فهرس صفر). بدلاً من ذلك، مع مصفوفة مفهرسة من 1، يتم تبسيط التنفيذ حيث يتم العثور على العناصر الفرعية في $2i$ و $2i+1$ ، والوالد موجود في $\lfloor i/2\rfloor$ [ ³⁰^]

تتميز هذه الطريقة بتخزين أكثر إحكامًا وموقع مرجعي أفضل ، لا سيما أثناء اجتياز الترتيب المسبق. وغالبًا ما تُستخدم مع الأكوام الثنائية . ^{[ 31 ]}

الترميزات

ترميزات موجزة

تُعرَّف بنية البيانات المختصرة بأنها تلك التي تشغل مساحة قريبة من الحد الأدنى الممكن، وفقًا للحدود الدنيا لنظرية المعلومات . عدد الأشجار الثنائية المختلفة على $n$ العقدة هي $\mathrm {C} _{n}$ ، ال $n$ العدد الكاتالوني (بافتراض أننا نعتبر الأشجار ذات البنية المتطابقة متطابقة). بالنسبة للأعداد الكبيرة $n$ هذا يتعلق $4^{n}$ وبالتالي نحتاج على الأقل إلى حوالي $\log _{2}4^{n}=2n$ عدد البتات اللازمة لترميزها. وبالتالي، فإن الشجرة الثنائية المختصرة ستشغل 2n + o( n ) بت (حيث يمثل 'o()' رمز Little-o ).

إحدى الطرق البسيطة لتحقيق هذا الشرط هي زيارة عُقد الشجرة بترتيب ما قبل الترتيب، وإخراج القيمة "1" للعقدة الداخلية و"0" للعقدة الورقية. ^{[ 32 ]} إذا كانت الشجرة تحتوي على بيانات، فيمكننا ببساطة تخزينها في مصفوفة متتالية بترتيب ما قبل الترتيب. تُحقق هذه الدالة ذلك:

دالة EncodeSuccinct( العقدة n، بنية سلسلة البتات ، بيانات المصفوفة ) { إذا كانت n = nil ثم أضف 0 إلى البنية؛ آخر أضف 1 إلى البنية؛ أضف n.data إلى البيانات؛ EncodeSuccinct(n.left, structure, data); EncodeSuccinct(n.right, structure, data); }

يحتوي هيكل السلسلة فقط $2n+1$ أجزاء في النهاية، حيث $n$ يمثل عدد العقد (الداخلية)؛ ولا نحتاج حتى إلى تخزين طولها. ولإثبات عدم فقدان أي معلومات، يمكننا تحويل الناتج إلى الشجرة الأصلية على النحو التالي:

دالة DecodeSuccinct( بنية سلسلة بت ، بيانات مصفوفة ) { قم بإزالة الجزء الأول من البنية وضعه في b إذا كانت b = 1، ثم أنشئ عقدة جديدة n قم بإزالة العنصر الأول من البيانات وضعه في n.data n.left = DecodeSuccinct(structure, data) n.right = DecodeSuccinct(structure, data) أرجع n وإلا أرجع nil }

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

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

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

ليكن T عقدة في شجرة مرتبة، وليكن B صورة T في الشجرة الثنائية المقابلة. عندئذٍ، يمثل الابن الأيسر لـ B الابن الأول لـ T ، بينما يمثل الابن الأيمن لـ B الشقيق التالي لـ T.

على سبيل المثال، الشجرة المرتبة على اليسار والشجرة الثنائية على اليمين متطابقتان:

في الشجرة الثنائية المصورة، تمثل الحواف السوداء على اليسار الطفل الأول ، بينما تمثل الحواف الزرقاء على اليمين الشقيق التالي .

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

العمليات المشتركة

تُعد عمليات تدوير الأشجار عمليات داخلية شائعة جدًا في الأشجار الثنائية ذاتية التوازن .

توجد مجموعة متنوعة من العمليات المختلفة التي يمكن إجراؤها على الأشجار الثنائية. بعضها عمليات تغيير ، بينما البعض الآخر ببساطة يعيد معلومات مفيدة حول الشجرة.

الإدخال

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

العقد الورقية

لإضافة عقدة جديدة بعد العقدة الورقية A، تقوم A بتعيين العقدة الجديدة كواحدة من أبنائها وتقوم العقدة الجديدة بتعيين العقدة A كوالد لها.

العقد الداخلية

تُعدّ عملية الإضافة على العقد الداخلية أكثر تعقيدًا بعض الشيء من إضافتها على العقد الطرفية. لنفترض أن العقدة الداخلية هي العقدة A، وأن العقدة B هي ابن A. (إذا كانت الإضافة لإضافة ابن أيمن، فإن B هي الابن الأيمن لـ A، وينطبق الأمر نفسه على إضافة ابن أيسر). تُسند A ابنها إلى العقدة الجديدة، وتُسند العقدة الجديدة والدها إلى A. ثم تُسند العقدة الجديدة ابنها إلى B، وتُسند B والدها إلى العقدة الجديدة.

الحذف

الحذف هو العملية التي يتم من خلالها إزالة عقدة من الشجرة. ولا يمكن إزالة سوى عقد معينة في الشجرة الثنائية بشكل قاطع. ^{[ 33 ]}

عقدة تحتوي على صفر أو واحد من الأبناء

لنفترض أن العقدة المراد حذفها هي العقدة A. إذا لم يكن لدى A أي أبناء، يتم الحذف بتعيين قيمة الابن لوالد A إلى null . أما إذا كان لدى A ابن واحد، فيتم تعيين قيمة والد ابن A إلى والد A، وتعيين قيمة ابن والد A إلى ابن A.

عقدة بها طفلان

في الشجرة الثنائية، لا يمكن حذف عقدة لها ولدان بشكل قاطع. ^{[ 33 ]} ومع ذلك، في بعض الأشجار الثنائية (بما في ذلك أشجار البحث الثنائية ) يمكن حذف هذه العقد ، ولكن مع إعادة ترتيب بنية الشجرة.

اجتياز

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

النظام السابق

في الترتيب المسبق، نزور دائمًا العقدة الحالية؛ ثم نجتاز بشكل متكرر الشجرة الفرعية اليسرى للعقدة الحالية، ثم نجتاز بشكل متكرر الشجرة الفرعية اليمنى للعقدة الحالية. يُعدّ اجتياز الترتيب المسبق اجتيازًا مُرتبًا طوبولوجيًا ، لأن معالجة العقدة الأبوية تتم قبل معالجة أي من عقدها الفرعية.

بالترتيب

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

بعد الطلب

في الترتيب اللاحق، نجتاز دائمًا الشجرة الفرعية اليسرى للعقدة الحالية بشكل متكرر؛ ثم نجتاز الشجرة الفرعية اليمنى للعقدة الحالية بشكل متكرر، ثم نزور العقدة الحالية. يمكن أن يكون اجتياز الترتيب اللاحق مفيدًا للحصول على التعبير اللاحق لشجرة التعبير الثنائية . ^{[ 34 ]}

ترتيب العمق أولاً

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

ترتيب العرض أولاً

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

في الشجرة الثنائية الكاملة، يُمكن استخدام مؤشر عرض العقدة ( i − ( ^2d − 1)) كتعليمات اجتياز من الجذر. يتم قراءة البيانات بتًا بتًا من اليسار إلى اليمين، بدءًا من البت d − 1، حيث d هي المسافة بين العقدة والجذر ( d = ⌊log ₂ ( i + 1)⌋)، والعقدة المعنية ليست الجذر نفسه ( d > 0). عندما يكون مؤشر العرض محجوبًا عند البت d − 1، فإن قيم البت 0 و 1 تعنيان الانتقال إلى اليسار أو اليمين، على التوالي. تستمر العملية بفحص البت التالي إلى اليمين تباعًا حتى لا يتبقى أي بت. يشير البت الأخير إلى الاجتياز النهائي من والد العقدة المطلوبة إلى العقدة نفسها. يوجد توازن بين الوقت والمساحة عند تكرار الشجرة الثنائية الكاملة بهذه الطريقة، وبين امتلاك كل عقدة مؤشرًا (أو مؤشرات) إلى عقدها الشقيقة (أو عقدها الشقيقة).

مراجع

الاقتباسات

↑ روان غارنييه؛ جون تايلور (2009). الرياضيات المتقطعة: البراهين، والهياكل، والتطبيقات، الطبعة الثالثة . مطبعة سي آر سي. ص 620. ISBN 978-1-4398-1280-8.
↑ ستيفن س. سكينا (2009). دليل تصميم الخوارزميات . سبرينغر ساينس آند بيزنس ميديا. ص 77. ISBN 978-1-84800-070-4.
1 2 كنوت (1997). فن برمجة الحاسوب، المجلد 1، الطبعة الثالثة . بيرسون للتعليم. ص 363. ISBN 0-201-89683-4.
↑ إيفان فلوريس (1971). نظام برمجة الحاسوب/360 . برنتيس هول. ص 39.
↑ كينيث روزن (2011). الرياضيات المتقطعة وتطبيقاتها، الطبعة السابعة . ماكجرو هيل ساينس. ص 749. ISBN 978-0-07-338309-5.
↑ ديفيد ر. مازور (2010). التوافقية: جولة إرشادية . الجمعية الرياضية الأمريكية. ص 246. ISBN 978-0-88385-762-5.
1 2 "الشجرة الثنائية" ، موسوعة الرياضيات ، مطبعة EMS ، 2001 [1994]متوفر أيضًا في المطبوعات بعنوان: ميشيل هازوينكل (1997). موسوعة الرياضيات. الملحق الأول . سبرينغر ساينس آند بيزنس ميديا. ص 124. ISBN 978-0-7923-4709-5.
↑ إل آر فولدز (1992). تطبيقات نظرية الرسم البياني . سبرينغر ساينس آند بيزنس ميديا. ص 32. ISBN 978-0-387-97599-3.
↑ ديفيد ماكينسون (2009). المجموعات والمنطق والرياضيات للحوسبة . سبرينغر ساينس آند بيزنس ميديا. ص 199. ISBN 978-1-84628-845-6.
↑ جوناثان ل. غروس (2007). الأساليب التوافقية مع تطبيقات الحاسوب . مطبعة سي آر سي. ص 248. ISBN 978-1-58488-743-0.
1 2 لونغ، تشنغجيانغ (26 أكتوبر 2018)، المحاضرة 22: التعريفات المتكررة والاستقراء البنيوي (PDF)
1 2 كينيث روزن (2011). الرياضيات المتقطعة وتطبيقاتها، الطبعة السابعة . ماكجرو هيل ساينس. الصفحات 352-353 . ISBN 978-0-07-338309-5.
↑ تي تشيانغ هو؛ مان تاك شينغ (2002). الخوارزميات التوافقية . منشورات كوريير دوفر. ص 162. ISBN 978-0-486-41962-6.
↑ ليه-هسينغ هسو؛ تشنغ-كوان لين (2008). نظرية الرسم البياني وشبكات الربط البيني . مطبعة سي آر سي. ص 66. ISBN 978-1-4200-4482-9.
↑ ج. فلوم؛ م. غروه (2006). نظرية التعقيد البارامتري . سبرينغر. ص 245. ISBN 978-3-540-29953-0.
↑ تاماسيا، مايكل تي. جودريتش، روبرتو (2011). تصميم الخوارزميات : الأسس والتحليل وأمثلة من الإنترنت ( الطبعة الثانية). نيودلهي: وايلي-إنديا. ص 76. ISBN 978-81-265-0986-7.{{cite book}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
↑ "شجرة ثنائية كاملة" . المعهد الوطني للمعايير والتكنولوجيا .
1 2 ريتشارد ستانلي، التوافقية العددية، المجلد 2، ص 36
↑ "شجرة ثنائية مثالية" . المعهد الوطني للمعايير والتكنولوجيا (NIST ).
1 2 "شجرة ثنائية كاملة" . المعهد الوطني للمعايير والتكنولوجيا.
↑ "شجرة ثنائية شبه كاملة" . مؤرشف من الأصل بتاريخ 2016-03-04 . تم الاطلاع عليه بتاريخ 2015-12-11 .
↑ "شجرة ثنائية شبه كاملة" (ملف PDF) . مؤرشف (ملف PDF) من الأصل بتاريخ 2022-10-09.
↑ آرون م. تيننباوم وآخرون. هياكل البيانات باستخدام لغة C، برنتيس هول، 1990 ISBN 0-13-199746-7
↑ بول إي. بلاك (محرر)، مدخل بنية البيانات في قاموس الخوارزميات وهياكل البيانات . المعهد الوطني الأمريكي للمعايير والتكنولوجيا . 15 ديسمبر 2004. نسخة إلكترونية . تاريخ الوصول: 19 ديسمبر 2010.
↑ بارمار، أناند ك. (22 يناير 2020). "أنواع مختلفة من الأشجار الثنائية مع رسوم توضيحية ملونة" . ميديوم . تم الاسترجاع في 24 يناير 2020 .
↑ ميهتا، دينش؛ سرتاج ساهني (2004). دليل هياكل البيانات وتطبيقاتها . تشابمان وهول . ISBN 1-58488-435-5.
↑ كنوت، دونالد إي. فن برمجة الحاسوب، المجلد 4أ : الخوارزميات التوافقية، الجزء 1 .
↑ د. سامانتا (2004). هياكل البيانات الكلاسيكية . دار نشر PHI Learning Pvt. Ltd.، الصفحات 264-265 . ISBN 978-81-203-1874-8.
↑ مايكل ل. سكوت (2009). براغماتية لغات البرمجة ( الطبعة الثالثة). مورغان كوفمان. ص 347. ISBN 978-0-08-092299-7.
↑ مقدمة في الخوارزميات . كورمن، توماس هـ. ( الطبعة الثانية). كامبريدج، ماساتشوستس: مطبعة معهد ماساتشوستس للتكنولوجيا. 2001. ص 128. ISBN 0-262-03293-7. OCLC 46792720 . {{cite book}}صيانة CS1: أخرى ( رابط )
↑ لاكسو، ميكو. "قائمة الانتظار ذات الأولوية والكومة الثنائية" . جامعة آلتو . تم الاسترجاع 2023-10-11 .
↑ ديمين، إريك. "6.897: هياكل البيانات المتقدمة، ربيع 2003، المحاضرة 12" (ملف PDF) . مختبر علوم الحاسوب والذكاء الاصطناعي بمعهد ماساتشوستس للتكنولوجيا. مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 24 نوفمبر 2005. تم الاطلاع عليه بتاريخ 14 أبريل 2022 .
1 2 دونغ إكس. نغوين (2003). "بنية الشجرة الثنائية" . rice.edu . تم الاطلاع عليه في 28 ديسمبر 2010 .
↑ ويتمان، تود (13 فبراير 2015). "المحاضرة 18: اجتياز الأشجار" (ملف PDF) . مؤرشف من الأصل (ملف PDF) بتاريخ 13 فبراير 2015. تم الاطلاع عليه بتاريخ 29 أبريل 2023 .

فهرس

دونالد كنوث . فن برمجة الحاسوب، المجلد الأول: الخوارزميات الأساسية ، الطبعة الثالثة. أديسون-ويسلي، 1997. ISBN 0-201-89683-4القسم 2.3، وخاصة الأقسام الفرعية 2.3.1–2.3.2 (الصفحات 318–348).

روابط خارجية

الأشجار الثنائية. مؤرشفة بتاريخ 23 سبتمبر 2020 في قاعدة بيانات FindStat عبر Wayback Machine .
برهان الشجرة الثنائية بالاستقراء ( مؤرشف بتاريخ 7 أبريل 2019 في أرشيف الإنترنت )
شجرة بحث ثنائية متوازنة على مصفوفة: كيفية إنشاء قائمة Ahnentafel من الأسفل إلى الأعلى، أو شجرة بحث ثنائية متوازنة على مصفوفة
الأشجار الثنائية وتطبيقها مع أمثلة برمجية عملية
مُصوِّر الشجرة الثنائية والرسم البياني
تطبيق جافا سكريبت لشجرة ثنائية مع شفرة المصدر
منظر علوي للشجرة الثنائية
منظر سفلي للشجرة الثنائية
منظر جانبي لشجرة ثنائية

[GarnierTaylor2009-1] روان غارنييه؛ جون تايلور (2009). الرياضيات المتقطعة: البراهين، والهياكل، والتطبيقات، الطبعة الثالثة . مطبعة سي آر سي. ص 620. ISBN 978-1-4398-1280-8.

[Skiena2009-2] ستيفن س. سكينا (2009). دليل تصميم الخوارزميات . سبرينغر ساينس آند بيزنس ميديا. ص 77. ISBN 978-1-84800-070-4.

[Knuth1997-3] 1 2 كنوت (1997). فن برمجة الحاسوب، المجلد 1، الطبعة الثالثة . بيرسون للتعليم. ص 363. ISBN 0-201-89683-4.

[Flores1971-4] إيفان فلوريس (1971). نظام برمجة الحاسوب/360 . برنتيس هول. ص 39.

[5] كينيث روزن (2011). الرياضيات المتقطعة وتطبيقاتها، الطبعة السابعة . ماكجرو هيل ساينس. ص 749. ISBN 978-0-07-338309-5.

[Mazur2010-6] ديفيد ر. مازور (2010). التوافقية: جولة إرشادية . الجمعية الرياضية الأمريكية. ص 246. ISBN 978-0-88385-762-5.

[oem-7] 1 2 "الشجرة الثنائية" ، موسوعة الرياضيات ، مطبعة EMS ، 2001 [1994]متوفر أيضًا في المطبوعات بعنوان: ميشيل هازوينكل (1997). موسوعة الرياضيات. الملحق الأول . سبرينغر ساينس آند بيزنس ميديا. ص 124. ISBN 978-0-7923-4709-5.

[Foulds1992-8] إل آر فولدز (1992). تطبيقات نظرية الرسم البياني . سبرينغر ساينس آند بيزنس ميديا. ص 32. ISBN 978-0-387-97599-3.

[Makinson2009b-9] ديفيد ماكينسون (2009). المجموعات والمنطق والرياضيات للحوسبة . سبرينغر ساينس آند بيزنس ميديا. ص 199. ISBN 978-1-84628-845-6.

[Gross2007-10] جوناثان ل. غروس (2007). الأساليب التوافقية مع تطبيقات الحاسوب . مطبعة سي آر سي. ص 248. ISBN 978-1-58488-743-0.

[Long2018-11] 1 2 لونغ، تشنغجيانغ (26 أكتوبر 2018)، المحاضرة 22: التعريفات المتكررة والاستقراء البنيوي (PDF)

[Rosen2011-12] 1 2 كينيث روزن (2011). الرياضيات المتقطعة وتطبيقاتها، الطبعة السابعة . ماكجرو هيل ساينس. الصفحات 352-353 . ISBN 978-0-07-338309-5.

[HuShing2002-13] تي تشيانغ هو؛ مان تاك شينغ (2002). الخوارزميات التوافقية . منشورات كوريير دوفر. ص 162. ISBN 978-0-486-41962-6.

[HsuLin2008-14] ليه-هسينغ هسو؛ تشنغ-كوان لين (2008). نظرية الرسم البياني وشبكات الربط البيني . مطبعة سي آر سي. ص 66. ISBN 978-1-4200-4482-9.

[FlumGrohe2006-15] ج. فلوم؛ م. غروه (2006). نظرية التعقيد البارامتري . سبرينغر. ص 245. ISBN 978-3-540-29953-0.

[16] تاماسيا، مايكل تي. جودريتش، روبرتو (2011). تصميم الخوارزميات : الأسس والتحليل وأمثلة من الإنترنت ( الطبعة الثانية). نيودلهي: وايلي-إنديا. ص 76. ISBN 978-81-265-0986-7.{{cite book}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )

[17] "شجرة ثنائية كاملة" . المعهد الوطني للمعايير والتكنولوجيا .

[:0-18] 1 2 ريتشارد ستانلي، التوافقية العددية، المجلد 2، ص 36

[19] "شجرة ثنائية مثالية" . المعهد الوطني للمعايير والتكنولوجيا (NIST ).

[complete_binary_tree-20] 1 2 "شجرة ثنائية كاملة" . المعهد الوطني للمعايير والتكنولوجيا.

[almost_complete_binary_tree-21] "شجرة ثنائية شبه كاملة" . مؤرشف من الأصل بتاريخ 2016-03-04 . تم الاطلاع عليه بتاريخ 2015-12-11 .

[nearly_complete_binary_tree-22] "شجرة ثنائية شبه كاملة" (ملف PDF) . مؤرشف (ملف PDF) من الأصل بتاريخ 2022-10-09.

[23] آرون م. تيننباوم وآخرون. هياكل البيانات باستخدام لغة C، برنتيس هول، 1990 ISBN 0-13-199746-7

[24] بول إي. بلاك (محرر)، مدخل بنية البيانات في قاموس الخوارزميات وهياكل البيانات . المعهد الوطني الأمريكي للمعايير والتكنولوجيا . 15 ديسمبر 2004. نسخة إلكترونية . تاريخ الوصول: 19 ديسمبر 2010.

[25] بارمار، أناند ك. (22 يناير 2020). "أنواع مختلفة من الأشجار الثنائية مع رسوم توضيحية ملونة" . ميديوم . تم الاسترجاع في 24 يناير 2020 .

[26] ميهتا، دينش؛ سرتاج ساهني (2004). دليل هياكل البيانات وتطبيقاتها . تشابمان وهول . ISBN 1-58488-435-5.

[27] كنوت، دونالد إي. فن برمجة الحاسوب، المجلد 4أ : الخوارزميات التوافقية، الجزء 1 .

[Samanta2004-28] د. سامانتا (2004). هياكل البيانات الكلاسيكية . دار نشر PHI Learning Pvt. Ltd.، الصفحات 264-265 . ISBN 978-81-203-1874-8.

[Scott2009-29] مايكل ل. سكوت (2009). براغماتية لغات البرمجة ( الطبعة الثالثة). مورغان كوفمان. ص 347. ISBN 978-0-08-092299-7.

[30] مقدمة في الخوارزميات . كورمن، توماس هـ. ( الطبعة الثانية). كامبريدج، ماساتشوستس: مطبعة معهد ماساتشوستس للتكنولوجيا. 2001. ص 128. ISBN 0-262-03293-7. OCLC 46792720 . {{cite book}}صيانة CS1: أخرى ( رابط )

[31] لاكسو، ميكو. "قائمة الانتظار ذات الأولوية والكومة الثنائية" . جامعة آلتو . تم الاسترجاع 2023-10-11 .

[32] ديمين، إريك. "6.897: هياكل البيانات المتقدمة، ربيع 2003، المحاضرة 12" (ملف PDF) . مختبر علوم الحاسوب والذكاء الاصطناعي بمعهد ماساتشوستس للتكنولوجيا. مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 24 نوفمبر 2005. تم الاطلاع عليه بتاريخ 14 أبريل 2022 .

[rice-33] 1 2 دونغ إكس. نغوين (2003). "بنية الشجرة الثنائية" . rice.edu . تم الاطلاع عليه في 28 ديسمبر 2010 .

[34] ويتمان، تود (13 فبراير 2015). "المحاضرة 18: اجتياز الأشجار" (ملف PDF) . مؤرشف من الأصل (ملف PDF) بتاريخ 13 فبراير 2015. تم الاطلاع عليه بتاريخ 29 أبريل 2023 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[

[

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

غير رسمية للتمييز

أو [ 16 ]

) [

[ 19 ]

[ 20 ]

[

[

[ 23 ]

[ 24 ]

[ 25 ]

26

27

[ 28 ]

[ 29 ]

30

[ 31 ]

[ 32 ]

[ 33 ]

[ 34 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗