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

الشجرة هي بنية بيانات تتكون من عقد لها الخصائص التالية:

  1. كل شجرة لها عقدة جذر (في الأعلى) لها بعض القيمة.
  2. تحتوي العقدة الجذرية على صفر أو أكثر من العقد الفرعية.
  3. تحتوي كل عقدة فرعية على صفر أو أكثر من العقد الفرعية ، وهكذا. هذا يخلق شجرة فرعية في الشجرة. كل عقدة لها شجرة فرعية خاصة بها تتكون من أطفاله وأطفالهم ، إلخ. وهذا يعني أن كل عقدة بمفردها يمكن أن تكون شجرة.

تضيف شجرة البحث الثنائية (BST) هاتين الخاصيتين:

  1. تحتوي كل عقدة على طفلين بحد أقصى.
  2. لكل عقدة ، تكون قيم العقد الهابطة اليسرى أقل من العقدة الحالية ، والتي بدورها أقل من العقد الهابطة اليمنى (إن وجدت).

تم بناء BST على فكرة خوارزمية البحث الثنائي ، والتي تسمح بالبحث السريع ، وإدراج وإزالة العقد. تعني طريقة إعدادها ، في المتوسط ​​، أن كل مقارنة تسمح للعمليات بتخطي حوالي نصف الشجرة ، بحيث يستغرق كل بحث أو إدراج أو حذف وقتًا يتناسب مع لوغاريتم عدد العناصر المخزنة في الشجرة ، O(log n).

ومع ذلك ، في بعض الأحيان يمكن أن تحدث أسوأ الحالات ، عندما تكون الشجرة غير متوازنة ويكون التعقيد الزمني O(n)لجميع هذه الوظائف الثلاث. هذا هو السبب في أن الأشجار ذاتية التوازن (AVL ، أحمر-أسود ، إلخ) أكثر فاعلية من BST الأساسي.

مثال سيناريو الحالة الأسوأ: يمكن أن يحدث هذا عندما تستمر في إضافة العقد التي تكون دائمًا أكبر من العقدة من قبل (هي الأصل) ، يمكن أن يحدث الشيء نفسه عندما تضيف دائمًا عقدًا ذات قيم أقل من العقد الأصلية.

العمليات الأساسية على BST

  • إنشاء: لإنشاء شجرة فارغة.
  • إدراج: أدخل عقدة في الشجرة.
  • البحث: يبحث عن عقدة في الشجرة.
  • حذف: يحذف عقدة من الشجرة.

خلق

في البداية يتم إنشاء شجرة فارغة بدون أي عقد. تتم تهيئة المتغير / المعرف الذي يجب أن يشير إلى عقدة الجذر NULLبقيمة.

بحث

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

إدراج

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

حذف

هناك 3 حالات يمكن أن تحدث عندما تحاول حذف عقدة. إذا كان لديه،

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

التعقيد الزمني لإنشاء شجرة O(1). يعتمد التعقيد الزمني للبحث عن عقدة أو إدخالها أو حذفها على ارتفاع الشجرة h، وبالتالي فإن الحالة الأسوأ هي O(h).

سلف العقدة

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

خليفة العقدة

يمكن وصف الوريقات على أنها العقدة التي ستأتي مباشرة بعد العقدة التي أنت فيها حاليًا. للعثور على وريث العقدة الحالية ، انظر إلى العقدة الطرفية اليسرى / الأصغر في الشجرة الفرعية اليمنى.

أنواع خاصة من BT

  • كومة
  • شجرة حمراء سوداء
  • شجرة ب
  • شجرة سبلاي
  • شجرة N-ary
  • Trie (شجرة الجذر)

مدة العرض

هيكل البيانات: صفيف

  • أداء أسوأ حالة: O(log n)
  • أفضل أداء: O(1)
  • متوسط ​​الأداء: O(log n)
  • أسوأ حالة تعقيد الفضاء: O(1)

أين nهو عدد العقد في BST.

تنفيذ BST

فيما يلي تعريف لعقدة BST بها بعض البيانات ، بالإشارة إلى عقدتها الفرعية اليمنى واليسرى.

struct node { int data; struct node *leftChild; struct node *rightChild; };

عملية البحث

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

struct node* search(int data){ struct node *current = root; printf("Visiting elements: "); while(current->data != data){ if(current != NULL) { printf("%d ",current->data); //go to left tree if(current->data > data){ current = current->leftChild; }//else go to right tree else { current = current->rightChild; } //not found if(current == NULL){ return NULL; } } } return current; }

أدخل العملية

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

void insert(int data) { struct node *tempNode = (struct node*) malloc(sizeof(struct node)); struct node *current; struct node *parent; tempNode->data = data; tempNode->leftChild = NULL; tempNode->rightChild = NULL; //if tree is empty if(root == NULL) { root = tempNode; } else { current = root; parent = NULL; while(1) { parent = current; //go to left of the tree if(data data) { current = current->leftChild; //insert to the left if(current == NULL) { parent->leftChild = tempNode; return; } }//go to right of the tree else { current = current->rightChild; //insert to the right if(current == NULL) { parent->rightChild = tempNode; return; } } } } } 

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

  • للعثور على العقدة السابقة للعقدة الحالية ، انظر إلى العقدة الطرفية الموجودة في أقصى اليمين / أكبر عقدة في الشجرة الفرعية اليسرى. يمكن وصف الوريقات على أنها العقدة التي ستأتي مباشرة بعد العقدة التي أنت فيها حاليًا.
  • للعثور على وريثة العقدة الحالية ، انظر إلى العقدة الطرفية الموجودة في أقصى اليسار / أصغر عقدة في الشجرة الفرعية اليمنى.

لنلقِ نظرة على بعض الإجراءات التي تعمل على الأشجار.

نظرًا لأن الأشجار يتم تعريفها بشكل متكرر ، فمن الشائع جدًا كتابة إجراءات تعمل على الأشجار التي هي نفسها متكررة.

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

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

لذلك إذا نظرنا إلى ورقة على سبيل المثال ، فإن هذا الارتفاع سيكون 1 لأن ارتفاع الطفل الأيسر يساوي صفرًا ، وارتفاع صفر الطفل الأيمن هو أيضًا 0. لذا فإن الحد الأقصى لذلك هو 0 ، ثم 1 زائد 0.

خوارزمية الارتفاع (الشجرة)

if tree = nil: return 0 return 1 + Max(Height(tree.left),Height(tree.right))

هذا هو الكود في C ++

int maxDepth(struct node* node) { if (node==NULL) return 0; else { int rDepth = maxDepth(node->right); int lDepth = maxDepth(node->left); if (lDepth > rDepth) { return(lDepth+1); } else { return(rDepth+1); } } } 

يمكننا أيضًا النظر في حساب حجم الشجرة الذي يمثل عدد العقد.

  • مرة أخرى ، إذا كان لدينا شجرة لا شيء ، فلدينا صفر عقد.

خلاف ذلك ، لدينا عدد العقد في الطفل الأيسر زائد 1 لأنفسنا بالإضافة إلى عدد العقد في الطفل الأيمن. إذن 1 زائد حجم الشجرة اليسرى زائد حجم الشجرة اليمنى.

خوارزمية الحجم (الشجرة)

if tree = nil return 0 return 1 + Size(tree.left) + Size(tree.right)

هذا هو الكود في C ++

int treeSize(struct node* node) { if (node==NULL) return 0; else return 1+(treeSize(node->left) + treeSize(node->right)); }

مقاطع الفيديو ذات الصلة على قناة freeCodeCamp على YouTube

  • شجرة البحث الثنائية
  • شجرة البحث الثنائية: الاجتياز والارتفاع

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

الشجرة الثنائية الكاملة / الشجرة الثنائية الصارمة: الشجرة الثنائية ممتلئة أو صارمة إذا كانت كل عقدة بها 0 أو طفلان بالضبط.

 18 / \ 15 30 / \ / \ 40 50 100 40

في شجرة ثنائية كاملة ، عدد العقد الطرفية يساوي عدد العقد الداخلية زائد واحد.

شجرة ثنائية كاملة: تكون الشجرة الثنائية شجرة ثنائية كاملة إذا تم ملء جميع المستويات بالكامل باستثناء المستوى الأخير المحتمل والمستوى الأخير به جميع المفاتيح المتبقية قدر الإمكان

 18 / \ 15 30 / \ / \ 40 50 100 40 / \ / 8 7 9