هياكل البيانات: شجرة ثنائية في جافا

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

فوائد الشجرة الثنائية

ما فائدة تخزين البيانات كشجرة بحث ثنائية؟ تخيل أن لدينا كتابًا مرجعيًا مكونًا من 100 صفحة ونحتاج إلى العثور على صفحة محددة تحتوي على البيانات التي نحتاجها. ونعرف أيضًا من المحتوى الصفحة المحددة التي نحتاجها. إذا اتبعنا المسار المعتاد، فسيتعين علينا قلب صفحة واحدة في كل مرة حتى نصل إلى الصفحة التي نحتاجها. أي أننا سنمر من 1 إلى 100 صفحة حتى نجد أنفسنا في المكان المناسب. على سبيل المثال، إذا كنا بحاجة إلى الصفحة 77، فسيكون لدينا 77 عملية بحث. إذا تحدثنا عن تعقيد الوقت، فسيكون O(N) . ولكن يمكن القيام بذلك بشكل أكثر كفاءة، أليس كذلك؟ دعونا نحاول أن نفعل نفس الشيء، ولكن باستخدام البحث الثنائي :

1. نقسم الدليل إلى قسمين، الأول - من 1 إلى 50، والثاني - 51-100. نحن نعرف بالضبط أيًا من هذه الأجزاء توجد صفحتنا: إذا أخذنا الصفحة 77 مرة أخرى، فهي في الجزء الثاني من الكتاب.
2. بعد ذلك، نعتبر الجزء الثاني ونقسمه إلى قسمين - من 51 إلى 75، من 76 إلى 100. في هذه الحالة، ستكون صفحتنا مرة أخرى في النصف الثاني، في النطاق 76-100.
3. بعد ذلك، نقسم هذه الفترة على 2 ونحصل على 76-88 و89-100. تتناسب الصفحة مع الفجوة الأولى، لذلك نتجاهل الثانية.
4. التالي هي الفواصل الزمنية: 76-81 و82-88، خذ الفترة الأولى.
5. 76-78 و79-81، خذ الأولى.
6. 76 و77-78، خذ الثانية.
7. 77 و 78، خذ الأول واحصل على صفحتنا - 77.

بدلاً من 77 خطوة، كنا بحاجة إلى 7 خطوات فقط! سيكون التعقيد الزمني لهذا البحث هو O(log(N)) .

قواعد بناء شجرة بحث ثنائية

يتم إنشاء شجرة البحث الثنائية وفقًا لقواعد معينة:

• تحتوي كل عقدة على طفلين على الأكثر؛
• كل قيمة أقل من قيمة العقدة تصبح الطفل الأيسر أو الطفل الأيسر؛
• كل قيمة أكبر من أو تساوي قيمة العقدة تصبح الطفل المناسب أو الطفل المناسب.

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

• جميع العقد ليس لها أكثر من ورثتين، مع استيفاء الشرط الأول؛
• إذا أخذنا في الاعتبار، على سبيل المثال، عقدة بقيمة 7 (أو أي شيء آخر)، فسنرى أن جميع قيم العناصر الموجودة في الشجرة الفرعية اليسرى ستكون أقل، وفي اليمين - أكثر. وهذا يعني استيفاء الشرطين 2 و 3.

دعونا نلقي نظرة على كيفية حدوث العمليات الأساسية - الإدراج والحذف والبحث.

البحث عن عنصر

عند البحث عن عنصر بقيمة معينة، نبدأ من العنصر الجذر:

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

على سبيل المثال، في شجرة البحث الثنائية الموضحة أعلاه، نريد العثور على العنصر ذو القيمة 5:

• ونقارنه بالعنصر الجذري، فنرى أن العنصر الجذري أكبر، فننتقل إلى الطفل الأيسر الذي قيمته 3؛
• نقارن بين العنصر الذي نبحث عنه والعنصر ذو القيمة 3، ونرى أن العنصر الذي نبحث عنه أكبر، لذلك نحتاج إلى السليل الأيمن للعنصر المعني، أي العنصر ذو القيمة 5؛
• نقارن هذا السليل مع الذي نبحث عنه ونرى أن القيم متساوية - تم العثور على العنصر.

إدخال عنصر

خوارزمية الإدراج بسيطة جدًا أيضًا:

1. نقارن العنصر الجديد بالعنصر الجذري (إذا لم يكن موجودًا، فإن العنصر الجديد هو العنصر الجذري).

2. إذا كان العنصر الجديد:

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

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

   على سبيل المثال، سنرغب في إدراج عنصر بقيمة 11 في الشجرة المذكورة أعلاه:

   • ونقارن مع العنصر الجذري 7 ونرى أن العنصر الجذري أصغر، فننتقل إلى الوريث الأيمن؛
   • العنصر التالي قيد النظر له قيمة 9، وهي أقل من 11 الجديدة، لذلك ننتقل إلى الوريث الصحيح؛
   • الوريث الصحيح له قيمة 10، وهي مرة أخرى أقل، لذلك ننتقل إلى العنصر الأول، وبما أنه غير موجود، يتم وضع عنصر جديد بقيمة 11 في هذا المكان.
   ↓

إزالة عنصر

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

1. العقدة المراد حذفها هي عقدة طرفية (ليس لها عناصر فرعية).

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

   ↓

2. العقدة التي يتم حذفها لها فرع واحد.

   في هذه الحالة، نحذف العقدة المحددة ونضع سليلها في مكانها (في جوهرها، نقوم ببساطة بقطع العقدة المحددة من السلسلة). على سبيل المثال، دعونا نزيل العقدة ذات القيمة 9 من الشجرة:

   ↓

3. العقدة التي يتم حذفها لها طفلان.

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

   مثال: في الشجرة أعلاه، أي عقدة يجب أن تكون الابن الأيسر للعقدة 3؟

   إذا فكرت في الأمر قليلاً، يصبح من الواضح أن هذه يجب أن تكون عقدة بقيمة 4. ولكن ماذا لو لم تكن الشجرة بهذه البساطة؟ إذا كانت تحمل مئات القيم، فهل سيكون من السهل معرفة من سيكون الخلف؟

   من الواضح أن لا. لذلك، نحن بحاجة إلى خوارزمية البحث الخاصة بجهاز الاستقبال الصغير:

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

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

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

   كيف ستبدو الشجرة بعد إزالة العقدة ذات القيمة 3:

   ↓

الآن حان الوقت للانتقال من الممارسة إلى النظرية. دعونا نلقي نظرة على كيف يمكننا رسم خريطة لبنية البيانات هذه في جافا. فئة عقدة واحدة:

class Node {
   private int value; // ключ узла
   private Node leftChild; // Левый узел потомок
   private Node rightChild; // Правый узел потомок

   public void printNode() { // Вывод значения узла в консоль
       System.out.println(" Выбранный узел имеет meaning :" + value);
   }

   public int getValue() {
       return this.value;
   }

   public void setValue(final int value) {
       this.value = value;
   }

   public Node getLeftChild() {
       return this.leftChild;
   }

   public void setLeftChild(final Node leftChild) {
       this.leftChild = leftChild;
   }

   public Node getRightChild() {
       return this.rightChild;
   }

   public void setRightChild(final Node rightChild) {
       this.rightChild = rightChild;
   }

   @Override
   public String toString() {
       return "Node{" +
               "value=" + value +
               ", leftChild=" + leftChild +
               ", rightChild=" + rightChild +
               '}';
   }
}

لا يوجد شيء معقد للغاية: كل عنصر له رابط لفرعه الأيسر والأيمن. والآن، ربما تكون الفئة الأكثر أهمية هي فئة الشجرة:

class Tree {
   private Node rootNode; // корневой узел

   public Tree() { // Пустое дерево
       rootNode = null;
   }

   public Node findNodeByValue(int value) { // поиск узла по значению
       Node currentNode = rootNode; // начинаем поиск с корневого узла
       while (currentNode.getValue() != value) { // поиск покуда не будет найден элемент or не будут перебраны все
           if (value < currentNode.getValue()) { // движение влево?
               currentNode = currentNode.getLeftChild();
           } else { //движение вправо
               currentNode = currentNode.getRightChild();
           }
           if (currentNode == null) { // если потомка нет,
               return null; // возвращаем null
           }
       }
       return currentNode; // возвращаем найденный элемент
   }

   public void insertNode(int value) { // метод вставки нового element
       Node newNode = new Node(); // создание нового узла
       newNode.setValue(value); // вставка данных
       if (rootNode == null) { // если корневой узел не существует
           rootNode = newNode;// то новый элемент и есть корневой узел
       }
       else { // корневой узел занят
           Node currentNode = rootNode; // начинаем с корневого узла
           Node parentNode;
           while (true) // мы имеем внутренний выход из цикла
           {
               parentNode = currentNode;
               if(value == currentNode.getValue()) {   // если такой элемент в дереве уже есть, не сохраняем его
                    return;    // просто выходим из метода
                }
                else  if (value < currentNode.getValue()) {   // движение влево?
                   currentNode = currentNode.getLeftChild();
                   if (currentNode == null){ // если был достигнут конец цепочки,
                       parentNode.setLeftChild(newNode); //  то вставить слева и выйти из методы
                       return;
                   }
               }
               else { // Или направо?
                   currentNode = currentNode.getRightChild();
                   if (currentNode == null) { // если был достигнут конец цепочки,
                       parentNode.setRightChild(newNode);  //то вставить справа
                       return; // и выйти
                   }
               }
           }
       }
   }

   public boolean deleteNode(int value) // Удаление узла с заданным ключом
   {
       Node currentNode = rootNode;
       Node parentNode = rootNode;
       boolean isLeftChild = true;
       while (currentNode.getValue() != value) { // начинаем поиск узла
           parentNode = currentNode;
           if (value < currentNode.getValue()) { // Определяем, нужно ли движение влево?
               isLeftChild = true;
               currentNode = currentNode.getLeftChild();
           }
           else { // or движение вправо?
               isLeftChild = false;
               currentNode = currentNode.getRightChild();
           }
           if (currentNode == null)
               return false; // yзел не найден
       }

       if (currentNode.getLeftChild() == null && currentNode.getRightChild() == null) { // узел просто удаляется, если не имеет потомков
           if (currentNode == rootNode) // если узел - корень, то дерево очищается
               rootNode = null;
           else if (isLeftChild)
               parentNode.setLeftChild(null); // если нет - узел отсоединяется, от родителя
           else
               parentNode.setRightChild(null);
       }
       else if (currentNode.getRightChild() == null) { // узел заменяется левым поддеревом, если правого потомка нет
           if (currentNode == rootNode)
               rootNode = currentNode.getLeftChild();
           else if (isLeftChild)
               parentNode.setLeftChild(currentNode.getLeftChild());
           else
               parentNode.setRightChild(currentNode.getLeftChild());
       }
       else if (currentNode.getLeftChild() == null) { // узел заменяется правым поддеревом, если левого потомка нет
           if (currentNode == rootNode)
               rootNode = currentNode.getRightChild();
           else if (isLeftChild)
               parentNode.setLeftChild(currentNode.getRightChild());
           else
               parentNode.setRightChild(currentNode.getRightChild());
       }
       else { // если есть два потомка, узел заменяется преемником
           Node heir = receiveHeir(currentNode);// поиск преемника для удаляемого узла
           if (currentNode == rootNode)
               rootNode = heir;
           else if (isLeftChild)
               parentNode.setLeftChild(heir);
           else
               parentNode.setRightChild(heir);
       }
       return true; // элемент успешно удалён
   }

   // метод возвращает узел со следующим meaningм после передаваемого аргументом.
   // для этого он сначала переходим к правому потомку, а затем
   // отслеживаем цепочку левых потомков этого узла.
   private Node receiveHeir(Node node) {
       Node parentNode = node;
       Node heirNode = node;
       Node currentNode = node.getRightChild(); // Переход к правому потомку
       while (currentNode != null) // Пока остаются левые потомки
       {
           parentNode = heirNode;// потомка задаём How текущий узел
           heirNode = currentNode;
           currentNode = currentNode.getLeftChild(); // переход к левому потомку
       }
       // Если преемник не является
       if (heirNode != node.getRightChild()) // правым потомком,
       { // создать связи между узлами
           parentNode.setLeftChild(heirNode.getRightChild());
           heirNode.setRightChild(node.getRightChild());
       }
       return heirNode;// возвращаем приемника
   }

   public void printTree() { // метод для вывода дерева в консоль
       Stack globalStack = new Stack(); // общий стек для значений дерева
       globalStack.push(rootNode);
       int gaps = 32; // начальное meaning расстояния между elementми
       boolean isRowEmpty = false;
       String separator = "-----------------------------------------------------------------";
       System.out.println(separator);// черта для указания начала нового дерева
       while (isRowEmpty == false) {
           Stack localStack = new Stack(); // локальный стек для задания потомков element
           isRowEmpty = true;

           for (int j = 0; j < gaps; j++)
               System.out.print(' ');
           while (globalStack.isEmpty() == false) { // покуда в общем стеке есть элементы
               Node temp = (Node) globalStack.pop(); // берем следующий, при этом удаляя его из стека
               if (temp != null) {
                   System.out.print(temp.getValue()); // выводим его meaning в консоли
                   localStack.push(temp.getLeftChild()); // соохраняем в локальный стек, наследники текущего element
                   localStack.push(temp.getRightChild());
                   if (temp.getLeftChild() != null ||
                           temp.getRightChild() != null)
                       isRowEmpty = false;
               }
               else {
                   System.out.print("__");// - если элемент пустой
                   localStack.push(null);
                   localStack.push(null);
               }
               for (int j = 0; j < gaps * 2 - 2; j++)
                   System.out.print(' ');
           }
           System.out.println();
           gaps /= 2;// при переходе на следующий уровень расстояние между elementми каждый раз уменьшается
           while (localStack.isEmpty() == false)
               globalStack.push(localStack.pop()); // перемещаем все элементы из локального стека в глобальный
       }
       System.out.println(separator);// подводим черту
   }
}

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

public class Application {
   public static void main(String[] args) {
       Tree tree = new Tree();
       // вставляем узлы в дерево:
       tree.insertNode(6);
       tree.insertNode(8);
       tree.insertNode(5);
       tree.insertNode(8);
       tree.insertNode(2);
       tree.insertNode(9);
       tree.insertNode(7);
       tree.insertNode(4);
       tree.insertNode(10);
       tree.insertNode(3);
       tree.insertNode(1);
       // отображение дерева:
       tree.printTree();

       // удаляем один узел и выводим оставшееся дерево в консоли
       tree.deleteNode(5);
       tree.printTree();

       // находим узел по значению и выводим его в консоли
       Node foundNode = tree.findNodeByValue(7);
       foundNode.printNode();
   }
}

عمليات البحث/الإدراج/الحذف في شجرة بحث ثنائية لها تعقيد زمني قدره O(log(N)) . لكن هذا هو السيناريو الأفضل. بشكل عام، يتراوح التعقيد الزمني للعمليات من O(log(N)) إلى O(N) . ذلك يعتمد على درجة انحطاط الشجرة.

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

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

في أي حالة يمكن أن تتدهور الشجرة؟

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