ساختارهای داده: درخت باینری در جاوا

سلام سلام! سخت است که یک برنامه نویس قوی بدون دانش اولیه باشید. و در اینجا منظور ما نه تنها دانش نحو زبان برنامه نویسی بومی، بلکه به طور کلی اصول و مفاهیم برنامه نویسی است. یکی از این مبانی الگوریتم ها و ساختارهای داده است. به عنوان یک قاعده، برخی در این موضوع بیشتر آگاه هستند، برخی کمتر، اما برخی اطلاعات اولیه وجود دارد که همه باید بدانند. در میان پایگاه های داده برای ساختارهای داده، قطعا ارزش درک درخت های جستجوی دودویی را دارد. در واقع، امروز ما خود ساختار را با ویژگی های آن بررسی خواهیم کرد و خواهیم فهمید که چگونه می توانید یک درخت باینری را در جاوا پیاده سازی کنید . ابتدا بیایید بفهمیم که درخت باینری چیست. درخت باینری ساختار داده ای است که در آن هر گره (والد) حداکثر دو فرزند (وارث راست و چپ) دارد. در عمل، معمولاً از دو نوع درخت باینری استفاده می شود - درخت جستجوی دودویی و هرم (هیپ). امروز به درخت جستجوی باینری نگاه خواهیم کرد.

مزایای درخت باینری

مزیت ذخیره سازی داده ها به عنوان درخت جستجوی باینری چیست؟ تصور کنید که ما یک کتاب مرجع 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) نزدیک می شود .

در چه صورت درخت ممکن است منحط شود؟

به عنوان مثال، اگر لیستی از عناصر مرتب شده را اضافه کنید. اگر لیست به ترتیب صعودی مرتب شود، ریشه اولین و به ترتیب کوچکترین خواهد بود. نفر بعدی بعد از او جایگاه فرزند مناسب را خواهد گرفت. و اونی که بعد میاد بزرگتر از دومی میشه و جایگاه جانشین سمت راستش رو میگیره و همینطور... اگه لیست به ترتیب نزولی باشه همین اتفاق میفته ولی با چپ ترین عناصر. برای جلوگیری از این امر، پس از دریافت تعدادی عنصر، می توانید به سادگی آنها را مخلوط کنید. سپس مرتب سازی ناپدید می شود و اعداد کم و بیش به طور مساوی در سراسر درخت پراکنده می شوند. این همه برای امروز است، از توجه شما متشکرم!