資料結構：Java 中的二元樹

嗨嗨！沒有基礎知識很難成為優秀的程式設計師。這裡我們不僅指本地程式語言的語法知識，也指一般程式設計的基礎知識和概念。這些基礎之一是演算法和資料結構。一般來說，有些人對這個問題了解較多，有些人較少，但有一些基本資訊是每個人都應該知道的。在資料結構的資料庫中，絕對值得了解二元搜尋樹。 實際上，今天我們將研究結構本身及其特性，並了解如何在 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。

我們只需要 7 步，而不是 77 步！此搜尋的時間複雜度將為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 的節點後，樹會是什麼樣子：

   ↓

現在是從實踐轉向理論的時候了。讓我們看看如何在 Java 中映射這個資料結構。單節點類別：

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)。

樹在什麼情況下會退化？

例如，如果您新增已排序元素的清單。如果列表按升序排序，則根將是第一個，即最小的。他之後的下一位將擔任右邊孩子的位置。後面的元素將比第二個元素大，並且將佔據其右後繼元素的位置，依此類推...如果列表按降序排列，那麼同樣的事情也會發生，但對於最左邊的元素。為了避免這種情況，在收到多個元素後，您可以簡單地將它們混合起來。然後排序就會消失，數字或多或少均勻地分散在整個樹上。今天就到這裡，謝謝大家的關注！