الفصل الثاني عشر
Binary Search Trees
مقدمة
في الفصل العاشر والحادي عشر اتعرضنا لاكتر من data structure , في الفصل العاشر اتعرضنا ل data structures بدائية أو بسيطة زي ال Array وال Stack وال Queue وال Linked List , وفي الفصل الحادي عشر اتعرضنا ل data structure أكثر تعقيدا وهي ال Hash Table , في الفصل ده ان شاء الله هنتعرض ل data structure شايفها أبسط من ال Hash Table وهي ال Binary Search Tree وهنختصرها ب BST , ال BST هي data structure بتدعم عمليات كتير , ممكن نقسم العمليات دي لقسمين كالعادة , أول قسم هو ال query operations ودي العمليات اللي بتستعلم عن البيانات بدون تعديل أي حاجة زي ال search وال maximum وال minimum وال successor وال predecessor , والقسم التاني هو ال maintaining operations ودي العمليات اللي بتعدل في البيانات الموجودة في ال tree زي ال insertion وال deletion , علشان ال BST بتدعم كل العمليات دي فبيعتبروها Dictionary و Priority Queue في نفس الوقت (ال Priority Queue اتشرحت في الفصل السادس) , لو فيه حاجة في العمليات دي غريبة عليك ارجع لمقدمة الباب التالت.
طبعا احنا عارفين ال Tree واتعرضنا ليها في الفصل السادس (Heapsort) , وفي نفس الفصل اتعرضنا لل Binary Tree كنوع من أنواع ال Tree data structure . علشان نفتكر مع بعض ال Tree هي ما إلا مجموعة nodes متصلة ببعض عن طريق pointers , الفرق بينها وبين ال Linked List هو في تركيب ال node , ال node في ال linked list عبارة عن ال key و pointer بيشاور على ال next node وممكن optionally يكون فيه pointer بيشاور على ال previous node في حالة انها doubly linked list , أما ال Tree ال node فيها عبارة عن ال key و pointer بيشاور على ال parent و pointer بيشاور على ال right child و pointer بيشاور على ال left child (ده في حالة انها Binary بيكون فيها 2 children), ال Tree ممكن تكون complete أو لا , لو ال Tree كانت complete فده معناه ان كل ال levels مكتملة (في الحالة دي بتبقى complete وكمان full) أو ال level الأخير بس(اللي فيه ال leaves) ناقص بعض ال nodes :
- يعني ال Tree دي complete و full لان كل ال levels مكتملة.
- وال Tree دي complete بس مش full لان كل ال levels مكتملة ماعدا ال level الاخير.
- وال Tree دي مش complete وبالتالي مش full لان ال level اللي قبل الاخير مش كامل.
المميز في ال BST انها بتقدر تنفذ كل العمليات دي في time متناسب مع ال height بتاعها يعني Θ(lgn) في ال average case , وال average case دي بتتحقق في حالة انها complete , احنا في الفصل ده هنشوف نوع من ال BST أو طريقة لبناء BST اسمها Randomly-Built BST ومن اسمها هي BST مبنية بشكل random , النوع ده من ال BST بيضمن انها تكون complete في ال expected case , في الفصول اللي جاية هنشوف أنواع بتضمن ده في ال worst case .
What is a binary search tree?
ال BST هي ببساطة Binary tree ولكن فيه property (خاصية) أو شرط علشان نقدر نقول ان ال Binary Tree دي هي BST , الخاصية دي بترجع لل key بتاع ال nodes , والخاصية دي اسمها binary-search-tree property وهي اللي بتسهل وتسرع تنفيذ عمليات ال Query , الخاصية هي ببساطة ان لكل node ال key بتاعها بيكون اكبر من او يساوى كل ال keys بتاع ال nodes اللي في ال left subtree وبيكون اصغر من او يساوي كل ال keys بتاع ال nodes اللي في ال right subtree .
في الصورة اللي قدامك 2 BST , لان الخاصية أو الشرط متحقق , على سبيل المثال ال BST اللي عالشمال (a) ال root node بتاعتها ال key بتاعها 5 وال keys اللي في ال left subtree هما 3 , 2, 5 وكلهم اصغر من او يساوي 5 وال keys اللي في ال right subtree هما 7, 8 وكلهم أكبر من أو يساوي 5 والخاصية متحققة مع كل ال nodes مش بس ال root . ولكن (a) هي أكثر كفاءة من (b) لان (a) تعتبر complete BST وبالتالي ال height بتاعها اقل وبالتالي وقت التنفيذ أقل لان وقت التنفيذ متناسب مع ال height .
الخاصية دي بتتيح لنا اننا نطبع ال keys بتاع ال BST مرتبة ب recursive procedure بسيط جدا اسمه inorder-tree-walk.
ال procedure ببساطة عبارة عن انك لكل node بشكل recursively بتطبع ال left subtree اللي انت متاكد ان كل ال keys اللي فيها أصغر من أو تساوي ال key بتاع ال node وبعدين تطبع ال key بتاع ال node وبعدين تطبع ال keys بتاع ال right subtree اللي انت متاكد ان كل ال keys اللي فيها أكبر من أو تساوي ال key بتاع ال node , طبعا مبتعملش حاجة في حالة انك وصلت ل node بتساوي NIL , ال procedure ده بيتنفذ في Θ(n) . على سبيل المثال لو طبقنا ال procedure ده على ال BSTs اللي في الصورة اللي فاتت هيطبع بالترتيب:
2
3
5
5
7
8
وده بيخلي ال BST ممكن تستخدم ك sorting algorithm بذاتها وهنشوف ده في نهاية الفصل ان شاء الله.
Querying a binary search tree
ال BST زي ماقلنا بتمكنا من اننا ننفذ عمليات Querying كتير زي ال Search وال Minimum وال Maximum وال Successor وال Predecessor , وكل العمليات دي بنقدر ننفذها في O(h) حيث h هو ال height بتاع ال Tree , في السكشن ده عايزين نشوف إزاي نقدر ننفذ العمليات دي في الوقت ده.
Search
نبدأ بال Search procedure , ميزة ال BST انك تقدر من خلال مقارنة ال key اللي انت بتدور عليه مع ال key بتاع اي node انك تحدد اذا كان ال key اللي انت بتدور عليه موجود في ال right أو ال left subtree وده بسبب خاصية ال BST , وده اللي هنعمله في procedure ال Search.
ال procedure بيستقبل كمدخلات ال root node بتاع ال Tree وهنسميه x وال key اللي انت عايز تبحث عنه وهنسميه k , وبيرجع إما node ال key بتاعها بيساوي k وهي اللي انت بتدور عليها في حالة انها موجودة أو NIL في حالة انها مش موجودة. ال procedure بسيط جدا , هو ما إلا لكل node بشكل recursively بيشوف نفسه هيتحرك في أنهي subtree الليمين ولا الشمال , بيقارن ال k بال key بتاع ال node لو لقي ال k أكبر يبقى هو لو موجود هيكون موجود في ال right subtree ولو أصغر يبقى لو هو موجود هيكون موجود في ال left subtree (وده بسبب وجود خاصية ال BST), وبيبدأ ينادي نفس ال procedure مع ال left أو ال right subtree بناءا على المقارنة دي , طبعا لازم يكون فيه case عندها نوقف ال recursion , ال case دي هي إما ان ال k بيساوي ال key بتاع ال node وبالتالي لقينا ال node اللي بندور عليها وعايزين نرجعها أو ان ال node دي ب NIL وده معناه اننا انهينا ال Tree ومش لاقيين ال key اللي بندور عليه وفي الحالة دي عايزين نرجع NIL , ففي الحالتين انا برجع قيمة ال node .
طبعا واضح جدا اننا بنفذ خطوة المقارنة وال call لنفس ال procedure مرة لكل level في ال tree , والعمليتين دول بياخدوا constant time فبالتالي ال procedure بيتنفذ في O(h) حيث h هو ال height بتاع ال Tree.
نفس ال procedure ممكن ننفذه iteratively بدل recursively باستخدام while loop بالشكل ده.
طبعا نفس المقارنة بس بدل مبن call ال procedure بنغير ال x لاما right[x] أو left[x] حسب نتيجة المقارنة ونختبر x الجديدة في ال iteration الجديدة في ال while loop. ال procedure ده يعتبر أكفأ من اللي فات على أي Processor لانه طبيعة ال recursion بيحتاج memory أكتر بسبب عدد ال functions اللي بيعملها push في ال stack ورا بعضها.
Minimum and Maximum
طبعا مفيش أسهل من إنك تجيب ال node اللي ال key بتاعها الأصغر (ال Minimum) أو الأكبر (ال Maximum) في ال Tree , لإن بسبب خاصية ال BST فال Minimum key هي أقصى node في شمال ال Tree , فممكن توصلها بانك تتابع ال left لغاية متوصل لاخر left في ال Tree اللي ال left بتاعه ب NIL , وفي حالة ال Maximum key فهتكون موجودة في أقصى يمين ال Tree.
طبعا ال 2 procedure بيستقبلو كمدخلات ال root node بتاع ال Tree وبيرجعوا ال Minimum وال Maximum.
Successor and Predecessor
ال successor ل node مثلا x هو ال node اللي لو ال nodes دي مرتبة حسب ال key هتكون بعدها مباشرة فالترتيب ده , أو ممكن تعرفها على إنها ال node صاحبة أصغر key أكبر من ال key[x] , وال predecessor هو العكس , لو ال nodes مرتبة هتكون قبلها مباشرة فالترتيب , أو ممكن تعرفها على إنها ال node صاحبة أكبر key أصغر من ال key[x] . علشان نجيب ال successor فيه 3 حالات لل node اللي انت عايز تجيبلها ال successor:
- إما إن ليها right child وبالتالي ال successor هو ال Minimum بتاع ال right subtree بتاعتها , وده بسبب خاصية ال BST , لإن ال left subtree كل ال keys اللي فيها أصغر من أو يساوي ال key بتاع ال node دي , وال right subtree بتاعتها كل ال keys اللي فبها أكبر من أو يساوي ال key بتاع ال node دي , فبالتالي لما تجيب ال Minimum بتاع ال right subtree فانت جبت ال node صاحبة أصغر key أكبر من ال key بتاع ال node دي.
- إما إن ال node ملهاش right child وبالتالي ال successor لو موجود هيكون موجود في ال parents بتاعة ال node دي , لإن ال left subtree عارفين ان ال keys اللي فيها كلها أصغر من أو تساوي ال key بتاع ال node الحالية , السؤال بقى أنهي parent فيهم؟ الإجابة هو أول parent في السلسة يكون ال left child بتاعه جزء من السلسة أو بمعنى تاني أول parent يكون ال node اللي انا بدور عال successor بتاعها موجودة في ال left subtree وده ليه إثبات رياضي.
- إما إنها ال Maximum وبالتالي مفيش node أكبر منها وده بتعرفه لما تفضل طالع لفوق ومتلاقيش node بالشرط اللي قلناه في الحالة 2.
ال procedure بصراحة أبسط من الشرح اللي فوق , ال procedure بيقبل كمدخلات ال node اللي عايز يجيب ال successor بتاعها ومسميها x:
- أول سطرين بيشوف لو فيه right child يبقى الحالة الأولى فبيرجع ال Minimum بتاع ال right subtree.
- من السطر 3 ل 7 بيبدأ يشوف الحالة 2 و 3: كل اللي بيعمله بيعرف متغير جديد اسمه y علشان يقدر يتحرك لفوق في ال tree ويكون ماسك ال parent وال child , وأول ميقابل parent y ال x child بتاعه هو ال left يطلع من ال while loop ويرجعه ودي الحالة التانية , وبيطلع من ال while loop برضه في حالة أنه وصل ل NIL ودي الحالة التالتة.
ال procedure بتاع ال predecessor مماثل جدا لل procedure بتاع ال successor , اللي هيتغير كالتالي , فيه 3 حالات برضه لل node x:
- إما إن ليها left child وبالتالي ال predecessor هو ال Maximum بتاع ال left subtree بتاعتها , وده بسبب خاصية ال BST , لإن ال right subtree كل ال keys اللي فيها أكبر من أو يساوي ال key بتاع ال node دي , وال left subtree بتاعتها كل ال keys اللي فبها أصغر من أو يساوي ال key بتاع ال node دي , فبالتالي لما تجيب ال Maximum بتاع ال left subtree فانت جبت ال node صاحبة أكبر key أصغر من ال key بتاع ال node دي.
- إما إن ال node ملهاش left child وبالتالي ال successor لو موجود هيكون موجود في ال parents بتاعة ال node دي , لإن ال right subtree عارفين ان ال keys اللي فيها كلها أكبر من أو تساوي ال key بتاع ال node الحالية , أنهي parent بقى؟ أول parent في السلسة يكون ال right child بتاعه جزء من السلسة أو بمعنى تاني أول parent يكون ال node اللي انا بدور عال successor بتاعها موجودة في ال right subtree.
- إما إنها ال Minimum وبالتالي مفيش node أصغر منها وده.
حاول تكتب انت ال procedure بتاع ال predecessor.
Maintaining a binary search tree(Insertion and Deletion)
زي ماقلنا ال BST بتدعم maintaining operations ودي العمليات اللي بتعدل في ال Tree مش بس تستعلم عن حاجة , ال Operations دول هما ال Insertion (الإضافة) وال Deletion (الحذف) , في ال Operations دي احنا لازم ننفذ العملية مع ثبوت خاصية ال BST بدون تغيير , وزي ماهنشوف في السكشن الجاي عملية الإضافة هي اللي هتمكنا من إننا نبني ال randomly-built BST .
Insertion
عملية ال Insertion بسيطة إلى حد ما مقارنة بال Deletion , علشان نضيف node في ال BST إحنا محتاجين نتحرك في ال Tree من فوق لتحت كل مرة بناخد قرار اذا كنا هنتحرك في ال right subtree ولا ال left subtree بناءا على مقارنة ال key بتاع ال node اللي عايزين نضيفها مع ال key بتاع ال node الحالية , لغاية منوصل ل NIL وده يكون المكان اللي عايزين نضيف فيه ال node الجديدة , أول منوصل لل node دي محتاجين يكون معانا reference لل parent بتاعها علشان نضيف ال node الجديدة ليه إما في ال left child أو ال right child , ونضيف ال parent ده لل pointer اللي بيشاور على ال parent في ال node الجديدة.
ال procedure بتاعنا إسمه Tree_Insert وبيستقبل كمدخلات ال Tree اللي عايزين نضيف فيها واسمها T وال node اللي عايزين نضيفها واسمها z:
- في أول سطرين بيعرف متغيرين وبيدي واحد منهم قيمة ال root node بتاع ال Tree واسمه x والتاني بيديه NIL أو ال parent بتاع ال x بس بما ان x هو ال root node دلوقتي فال parent بتاعه ب NIL , ودول ال variables اللي هيتحرك بيهم في ال Tree من فوق لتحت , ولازم متغيرين مش واحد لانه في النهاية هيوصل ب x ل NIL فمش هيكون معاه ال parent بتاعه لو مكنش عرف y.
- في السطر 3 - 7 بيتحرك في ال Tree لغاية ميوصل ب x ل NIL , وكل مرة يعدل ال y يخليها ال parent بتاع x ويخلي x اما ال right او ال left بتاع ال x حسب نتيجة ال comparison.
- في السطر 8 - 13 بيضيف ال node الجديدة z في المكان اللي بيشاور عليه x , في السطر 8 بيخلي ال parent بتاع ال node الجديدة ب y , وبعدين بيتأكد ان y مش ب NIL لانها لو ب NIL يبقى ال Tree فاضية وبالتالي ال node الجديدة هنخليها ال root node وخلاص , بعد كدة بيقارن ال key بتاع ال node الجديدة مع ال key بتاع y ومن خلال المقارنة اما ال node الجديدة بتروح في ال left child او ال right child.
الشكل ده بيوضح ازاي بيضيف ال node اللي ال key بتاعها 13 في ال Tree اللي قدامك , أول خطوة بيقارن ال 13 مع ال key بتاع ال root اللي هو 12 فيتحرك يمين , بعدين يقارن ال 13 مع ال key بتاع ال right اللي هو 18 فيتحرك شمال , بعدين يقارن ال 13 مع ال key بتاع ال left اللي هو 15 فيتحرك شمال , يلاقي NIL فيضيف العنصر مكان ال node دي.
Deletion
عملية ال Deletion عملية أعقد شوية من ال Insertion لإن فيه 3 حالات لل node اللي انت عايز تحذفها:
- إما إنها ملهاش أي childre يعني leaf فبالتالي ال Deletion ما إلا هتخلي ال pointer اللي كان بيشاور عليها في ال parent بتاعها ب NIL.
- إما إنها ليها child واحد سواء left أو right فبالتالي هتشيل ال node من النص وتوصل ال parent بتاعها بال child بتاعها وبكدة تكون حذفتها من ال Tree.
- إما إن ليها 2 children ودي الحالة الصعبة اللي محتاجة تفكير , المشكلة هنا انك لو حذفتها دي ليها 2 children هتوديهم فين؟ هتحتاج تعديل كتير في ال Tree علشان تفضل متمسكة بخاصية ال BST , الحل الأبسط هو إنك تسيب ال node اللي انت عايز تحذفها وتحذف ال successor بتاعها , وده لإن حذف ال successor أسهل بما إنك متأكد إنه أما ملهش children خالص إما ملهش غير child واحد وفي ال right لإن لو ليه left ال left ده هيكون أصغر منه وبالتالي كان هيبقى هو ال successor , بعد متحذف ال successor تاخد البيانات وتعمل بيها override للبيانات بتاع ال node اللي انت كنت عايز تحذفها.
ال procedure اسمه Tree-Deletion وبيستقبل كمدخلات ال Tree اللي عايز تحذف منها واسمها T وال node اللي انت عايز تحذفها واسمها z:
- في السطر 1 - 3 بيحدد ال node اللي هيحذفها ويخزنها في متغير اسمه y , اللي هي لو احنا في الحالة الأولى أو التانية (يعني لو ملهاش children أو ليها child واحد) هتكون z أما لو احنا في الحالة التالتة فهتكون ال successor بتاع z.
- في السطر 4 - 6 بيحدد ال child اللي مش NIL لل node اللي هيحذفها ويخزنها في متغير اسمه x.
- في السطر 7 - 8 لو ال node y اللي هو عايز يحذفها ليها child (يعني الحالة التانية أو التالتة) فهيخلي ال parent بتاع ال child ده بعد مكان y يبقى ال parent بتاع y علشان هو يحذف y.
- في السطر 9 - 13 في الأول (سطر 9 - 10) بيتأكد ان y مش ال root لانها لو ال root فهو كل اللي محتاجه انه يخلي ال root ب NIL , اما لو مش ال root (سطر 11 - 13) فهو هيخلي ال pointer اللي كان بيشاور على y يشاور في ال parent بتاعه يشاور على ال child بتاع y , فهو كدة عمل link من ال parent بتاع ال y لل child بتاعه فيقدر يحذف ال y بأمان.
- في السطر 14 - 16 بيشوف لو هو في الحالة التالتة (بيعرفها بان y تكون مبتساويش z اللي هو عايز يحذفها أصلا) بيعمل override للبيانات بتاع y (ال node اللي حذفها اللي هي ال successor) على البيانات بتاع z اللي هو عايز يحذفها فعلا.
- في السطر 17 بيرجع ال node اللي هو حذفها.
الشكل ده بيوضح تنفيذ عملية ال Deletion في ال 3 حالات , الشكل a بيمثل الحالة الأولى , الشكل b بيمثل الحالة التانية , الشكل c بيمثل الحالة التالتة.
Using binary search tree to sort data
في السكشن ده عايزين نشوف ازاي لو معانا بيانات متخزنة في أي data structure ناخد البيانات دي ونبني بيها BST وكمان ازاي ممكن نستخدم ال BST دي ك sorting algorithm.
- في الأول لو معانا أي بيانات متخزنة فأي data structure ممكن نعدي عليها ونعمل insert لكل عنصر في ال BST باستخدام ال Tree-Insert procedure وبالتالي ننتهي بان البيانات اتخزنت في BST والخاصية بتاع ال BST موجودة لان ال Tree-Insert procedure بيحافظ عليها.
- بعد بناء ال BST بالطريقة دي عندك ال inorder-tree-walk procedure بيقدر بسهولة يعدي على ال Tree nodes بالترتيب فبالتالي معاك ال nodes مرتبة. في الحقيقة الطريقة دي تكافئ ال quicksort algorithm لانها بتنفذ نفس ال comparisons اللي بيعملها ال quicksort.
Implementation
- ده implementation بسيط لل BST بلغة ال C:
- وده implementation بسيط ل Binary Search Algorithm بلغة ال C:
References
- Full vs. Complete binary tree
تعليقات
إرسال تعليق