أشجار البحث الثنائية: شرح BST بأمثلة

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

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

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

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

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

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

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

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

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

خلق

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

بحث

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

البحث الأول (BFS)

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

بحث العمق الأول (DFS)

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

إدراج

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

حذف

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

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

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

سلف العقدة

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

خليفة العقدة

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

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

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

مدة العرض

هيكل البيانات: BST

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

أين   n  هو عدد العقد في BST. أسوأ حالة هي O (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; } 

أدخل العملية

Whenever an element is to be inserted, first locate its proper location. Start searching from the root node, then if the data is less than the key value, search for the empty location in the left subtree and insert the data. Otherwise, search for the empty location in the right subtree and insert the data.

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; } } } } } 

Delete Operation

void deleteNode(struct node* root, int data){ if (root == NULL) root=tempnode; if (data key) root->left = deleteNode(root->left, key); else if (key > root->key) root->right = deleteNode(root->right, key); else { if (root->left == NULL) { struct node *temp = root->right; free(root); return temp; } else if (root->right == NULL) { struct node *temp = root->left; free(root); return temp; } struct node* temp = minValueNode(root->right); root->key = temp->key; root->right = deleteNode(root->right, temp->key); } return root; } 

Binary search trees (BSTs) also give us quick access to predecessors and successors. Predecessors can be described as the node that would come right before the node you are currently at.

  • To find the predecessor of the current node, look at the rightmost/largest leaf node in the left subtree. Successors can be described as the node that would come right after the node you are currently at.
  • To find the successor of the current node, look at the leftmost/smallest leaf node in the right subtree.

Let's look at a couple of procedures operating on trees.

Since trees are recursively defined, it's very common to write routines that operate on trees that are themselves recursive.

So for instance, if we want to calculate the height of a tree, that is the height of a root node, We can go ahead and recursively do that, going through the tree. So we can say:

  • For instance, if we have a nil tree, then its height is a 0.
  • Otherwise, We're 1 plus the maximum of the left child tree and the right child tree.
  • So if we look at a leaf for example, that height would be 1 because the height of the left child is nil, is 0, and the height of the nil right child is also 0. So the max of that is 0, then 1 plus 0.

Height(tree) algorithm

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

Here is the code in 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); } } } 

We could also look at calculating the size of a tree that is the number of nodes.

  • Again, if we have a nil tree, we have zero nodes.
  • Otherwise, we have the number of nodes in the left child plus 1 for ourselves plus the number of nodes in the right child. So 1 plus the size of the left tree plus the size of the right tree.

Size(tree) algorithm

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

Here is the code in C++

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

Traversal

There are 3 kinds of traversals that are done typically over a binary search tree. All these traversals have a somewhat common way of going over the nodes of the tree.

In-order

This traversal first goes over the left subtree of the root node, then accesses the current node, followed by the right subtree of the current node. The code represents the base case too, which says that an empty tree is also a binary search tree.

void inOrder(struct node* root) { // Base case if (root == null) { return; } // Travel the left sub-tree first. inOrder(root.left); // Print the current node value printf("%d ", root.data); // Travel the right sub-tree next. inOrder(root.right); } 

Pre-order

This traversal first accesses the current node value, then traverses the left and right sub-trees respectively.

void preOrder(struct node* root) { if (root == null) { return; } // Print the current node value printf("%d ", root.data); // Travel the left sub-tree first. preOrder(root.left); // Travel the right sub-tree next. preOrder(root.right); } 

Post-order

This traversal puts the root value at last, and goes over the left and right sub-trees first. The relative order of the left and right sub-trees remain the same. Only the position of the root changes in all the above mentioned traversals.

void postOrder(struct node* root) { if (root == null) { return; } // Travel the left sub-tree first. postOrder(root.left); // Travel the right sub-tree next. postOrder(root.right); // Print the current node value printf("%d ", root.data); } 

Relevant videos on freeCodeCamp YouTube channel

And Binary Search Tree: Traversal and Height

Following are common types of Binary Trees:

Full Binary Tree/Strict Binary Tree: A Binary Tree is full or strict if every node has exactly 0 or 2 children.

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

In Full Binary Tree, number of leaf nodes is equal to number of internal nodes plus one.

Complete Binary Tree: A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible

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

Perfect Binary Tree A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at the same level.

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

Augmenting a BST

Sometimes we need to store some additional information with the traditional data structures to make our tasks easier. For example, consider a scenario where you are supposed to find the ith smallest number in a set. You can use brute force here but we can reduce the complexity of the problem to O(lg n) by augmenting a red-black or any self-balancing tree (where n is the number of elements in the set). We can also compute rank of any element in O(lg n) time. Let us consider a case where we are augmenting a red-black tree to store the additional information needed. Besides the usual attributes, we can store number of internal nodes in the subtree rooted at x(size of the subtree rooted at x including the node itself). Let x be any arbitrary node of a tree.

x.size = x.left.size + x.right.size + 1

أثناء زيادة الشجرة ، يجب أن نضع في اعتبارنا أننا يجب أن نكون قادرين على الحفاظ على المعلومات المعززة وكذلك القيام بعمليات أخرى مثل الإدراج والحذف والتحديث في O(lg n)الوقت المناسب.

منذ ذلك الحين ، نعلم أن قيمة x.left.size ستعطينا عدد العقد التي تتابع x في ترتيب اجتياز الشجرة. وبالتالي ، x.left.size + 1فإن رتبة x داخل الشجرة الفرعية متجذرة عند x.