数据结构：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)。

树在什么情况下会退化？

例如，如果您添加已排序元素的列表。如果列表按升序排序，则根将是第一个，即最小的。他之后的下一位将担任右边孩子的位置。后面的元素将比第二个元素大，并且将占据其右后继元素的位置，依此类推...如果列表按降序排列，那么同样的事情也会发生，但对于最左边的元素。为了避免这种情况，在收到多个元素后，您可以简单地将它们混合起来。然后排序就会消失，数字或多或少均匀地分散在整个树上。今天就到这里，谢谢大家的关注！