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

يمكن برمجة البحث في شجرة البحث الثنائية عن مفتاح معين بشكل متكرر أو تكراري .

يبدأ البحث بفحص العقدة الجذرية . إذا كانت الشجرة فارغة (nil )، فهذا يعني أن المفتاح المطلوب غير موجود فيها. أما إذا كان المفتاح مساويًا لمفتاح الجذر، فإن البحث ينجح وتُعاد العقدة. إذا كان المفتاح أصغر من مفتاح الجذر، ينتقل البحث إلى الشجرة الفرعية اليسرى. وبالمثل، إذا كان المفتاح أكبر من مفتاح الجذر، ينتقل البحث إلى الشجرة الفرعية اليمنى. تُكرر هذه العملية حتى يُعثر على المفتاح أو تُصبح الشجرة الفرعية المتبقية فارغة.${\displaystyle {\text{nil}}}$إذا لم يتم العثور على المفتاح المطلوب بعد${\displaystyle {\text{nil}}}$إذا تم الوصول إلى الشجرة الفرعية، فإن المفتاح غير موجود في الشجرة. ^{[ 10 ] : 290-291}

Recursive-Tree-Search(x, key) إذا كان x = NIL أو key = x.key، فأرجع x. إذا كان key < x.key ، فأرجع Recursive -Tree-Search(x.left, key). وإلا، فأرجع Recursive-Tree-Search(x.right, key) .

Iterative-Tree-Search(x, key) while x ≠ NIL and key ≠ x.key do if key < x.key then x := x.left آخر x := x.right نهاية الشرط، كرر، أعد x

إذا كان x.right ≠ NIL ، فأرجع BST -Successor(x) نهاية الشرط  y := x.parent بينما y ≠ NIL و x = y.right نفّذ x := y y := y.parent كرر الإرجاع y

إذا كان x.left ≠ NIL ، فأرجع BST -Maximum(x.left) . y := x.parent بينما y ≠ NIL و x = y.left نفّذ x := y y := y.parent كرر الإرجاع y

BST-Maximum(x) while x.right ≠ NIL do x := x.right كرر العودة x

BST-Minimum(x) while x.left ≠ NIL do x := x.left كرر العودة x

تؤدي عمليات مثل الإضافة والحذف إلى تغيير تمثيل شجرة البحث الثنائية ديناميكيًا. يجب تعديل بنية البيانات بحيث تظل خصائص شجرة البحث الثنائية محفوظة. تُضاف العقد الجديدة كعقد طرفية في شجرة البحث الثنائية. ^{[ 10 ] : 294-295.} فيما يلي تطبيق تكراري لعملية الإضافة. ^{[ 10 ] : 294}

1 BST-Insert(T, z) 2 ص := لا شيء 3 x := T.root 4 بينما x ≠ NIL نفّذ 5 ص := س 6 إذا كان z.key < x.key 7 x := x.left 8 وإلا 9 x := x.right ١٠ نهاية إذا ١١ كرر 12 z.parent := y 13 إذا كانت y = NIL فإن 14 T.root := z 15 وإلا إذا كان مفتاح z < مفتاح y، 16 y.left := z 17 آخر 18 y.right := z 19 نهاية إذا

يحتفظ الإجراء بـ "مؤشر لاحق".${\displaystyle {\text{y}}}$بصفتي أحد الوالدين${\displaystyle {\text{x}}}$بعد التهيئة في السطر 2، تقوم حلقة while الممتدة على الأسطر من 4 إلى 11 بتحديث المؤشرات. إذا${\displaystyle {\text{y}}}$يكون${\displaystyle {\text{nil}}}$وبالتالي، فإن شجرة البحث الثنائية فارغة.${\displaystyle {\text{z}}}$يتم إدراجها كعقدة جذرية لشجرة البحث الثنائية${\displaystyle {\text{T}}}$إن لم يكن كذلك${\displaystyle {\text{nil}}}$تتم عملية الإدخال بمقارنة المفاتيح بمفاتيح النظام.${\displaystyle {\text{y}}}$على الأسطر من 15 إلى 19، ويتم إدراج العقدة وفقًا لذلك. ^{[ 10 ] : 295}

حذف عقدة، على سبيل المثال${\displaystyle {\text{Z}}}$، من شجرة البحث الثنائية${\displaystyle {\text{BST}}}$يحتوي على ثلاث حالات: ^{[ 10 ] : 295-297}

1. لو${\displaystyle {\text{Z}}}$هي عقدة طرفية، يتم استبدالها بـ${\displaystyle {\text{لا شيء}}}$كما هو موضح في (أ).
2. لو${\displaystyle {\text{Z}}}$له طفل واحد فقط، وهو عقدة الطفل لـ${\displaystyle {\text{Z}}}$يتم رفعه عن طريق تعديل العقدة الأصلية لـ${\displaystyle {\text{Z}}}$للإشارة إلى العقدة الفرعية، وبالتالي أخذ${\displaystyle {\text{Z}}}$موقعها في الشجرة، كما هو موضح في (ب) و (ج).
3. لو${\displaystyle {\text{Z}}}$لديه أطفال يمين ويسار، وهو الوريث بالترتيب لـ${\displaystyle {\text{Z}}}$، يقول${\displaystyle {\text{Y}}}$، يزيح${\displaystyle {\text{Z}}}$باتباع الحالتين التاليتين:
   1. لو${\displaystyle {\text{Y}}}$يكون${\displaystyle {\text{Z}}}$الطفل الأيمن، كما هو موضح في (د)،${\displaystyle {\text{Y}}}$يُزيح${\displaystyle {\text{Z}}}$و${\displaystyle {\text{Y}}}$يبقى الطفل الأيمن دون تغيير.
   2. لو${\displaystyle {\text{Y}}}$يكمن في الداخل${\displaystyle {\text{Z}}}$الشجرة الفرعية اليمنى، لكنها ليست كذلك.${\displaystyle {\text{Z}}}$الطفل الأيمن، كما هو موضح في (هـ)،${\displaystyle {\text{Y}}}$يتم استبدالها أولاً بابنها الأيمن، ثم تحل محلها${\displaystyle {\text{Z}}}$موقعه في الشجرة.
4. بدلاً من ذلك، يمكن أيضاً استخدام العنصر السابق في الترتيب.

تُنفذ الشفرة الزائفة التالية عملية الحذف في شجرة بحث ثنائية. ^{[ 10 ] : 296-298}

1 BST-Delete(BST, z) 2 إذا كان z.left = NIL ثم 3 عقد إزاحة (BST، z، z.right) 4- وإلا إذا كان z.right = NIL، فـ 5 Shift-Nodes(BST, z, z.left) 6 أخرى 7 y := BST-Successor(z) 8 إذا كان y.parent ≠ z ، 9 Shift-Nodes(BST, y, y.right) 10 y.right := z.right 11 y.right.parent := y 12 نهاية إذا 13 عقدة الإزاحة (BST، z، y) 14 y.left := z.left 15 y.left.parent := y 16 نهاية إذا

1. Shift-Nodes(BST, u, v) 2 إذا كان u.parent = NIL ثم 3 BST.root := v 4- وإلا إذا كان u = u.parent.left ، 5 u.parent.left := v 5 أخرى 6 u.parent.right := v 7 نهاية الشرط 8 إذا كان v ≠ NIL ثم 9 v.parent := u.parent 10 نهاية إذا

ال${\displaystyle {\text{BST-Delete}}}$يتناول الإجراء الحالات الخاصة الثلاث المذكورة أعلاه. يتناول السطران 2-3 الحالة 1، ويتناول السطران 4-5 الحالة 2، بينما يتناول السطران 6-16 الحالة 3. الدالة المساعدة${\displaystyle {\text{Shift-Nodes}}}$يُستخدم هذا في خوارزمية الحذف لغرض استبدال العقدة${\displaystyle {\text{u}}}$مع${\displaystyle {\text{v}}}$في شجرة البحث الثنائية${\displaystyle {\text{BST}}}$[ ^{10 ] : 298} تتولى هذه العملية حذف (واستبدال ⁾${\displaystyle {\text{u}}}$من${\displaystyle {\text{BST}}}$.

تُعتبر الشجرة متوازنة الارتفاع إذا كان ارتفاعا الشجرة الفرعية اليسرى والشجرة الفرعية اليمنى مرتبطين بمعامل ثابت. وقد طُرحت هذه الخاصية في شجرة AVL ، واستمرت في شجرة الأحمر والأسود . ^{[ 15 ] : 50-51} . يجب مراقبة ارتفاعات جميع العقد على المسار من الجذر إلى عقدة الورقة المُعدّلة، وربما تصحيحها، في كل عملية إدراج أو حذف في الشجرة. ^{[ 15 ] : 52}

في الشجرة المتوازنة الوزن، يكون معيار توازن الشجرة هو عدد أوراق الأشجار الفرعية. ويختلف وزن الأشجار الفرعية اليسرى واليمنى على الأكثر بمقدار${\displaystyle 1}$[ ^{16 ] [ 15 ] : 61 ومع ذلك، فإن} الفرق محصور بنسبة${\displaystyle \alpha }$من الأوزان، نظرًا لشرط التوازن القوي لـ${\displaystyle 1}$لا يمكن الحفاظ عليها مع${\displaystyle O(\log n)}$إعادة توزيع العمل أثناء عمليات الإضافة والحذف.${\displaystyle \alpha }$تُعطي الأشجار المتوازنة الوزن مجموعة كاملة من شروط التوازن، حيث تحتوي كل شجرة فرعية يسرى وأخرى يمنى على جزء على الأقل من${\displaystyle \alpha }$من الوزن الإجمالي للشجرة الفرعية. ^{[ 15 ] : 62}

توجد عدة أشجار بحث ثنائية متوازنة ذاتيًا، بما في ذلك شجرة T ، ^{[ 17 ]} وشجرة treap ، ^{[ 18 ]} وشجرة الأحمر والأسود ، ^{[ 19 ]} وشجرة B ، ^{[ 20 ]} وشجرة 2-3 ، ^{[ 21 ]} وشجرة Splay . ^{[ 22 ]}

تُستخدم أشجار البحث الثنائية في خوارزميات الفرز مثل فرز الشجرة ، حيث تُضاف جميع العناصر دفعة واحدة ويتم اجتياز الشجرة بترتيب تسلسلي. ^{[ 23 ]} كما تُستخدم أشجار البحث الثنائية في الفرز السريع . ^{[ 24 ]}

تُستخدم أشجار البحث الثنائية في تنفيذ قوائم الانتظار ذات الأولوية ، حيث تُستخدم مفاتيح العقدة كأولويات. وتتم إضافة عناصر جديدة إلى قائمة الانتظار وفقًا لعملية الإضافة العادية في أشجار البحث الثنائية، بينما تعتمد عملية الإزالة على نوع قائمة الانتظار ذات الأولوية: ^{[ 25 ]}

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