데이터 구조: Java의 이진 트리

안녕 안녕! 기본적인 지식 없이는 강력한 프로그래머가 되기가 어렵습니다. 여기서 우리는 기본 프로그래밍 언어의 구문에 대한 지식뿐만 아니라 일반적인 프로그래밍의 기본 및 개념도 의미합니다. 이러한 기초 중 하나는 알고리즘과 데이터 구조입니다. 일반적으로 일부는 이 문제에 대해 더 잘 알고 있고 일부는 덜 알고 있지만 모든 사람이 알아야 할 몇 가지 기본 정보가 있습니다. 데이터 구조에 대한 데이터베이스 중에서 이진 검색 트리를 이해하는 것은 확실히 가치가 있습니다. 실제로 오늘 우리는 구조 자체와 그 기능을 살펴보고 Java에서 이진 트리를 구현하는 방법을 알아 보겠습니다 . 먼저 이진트리가 무엇인지 알아봅시다. 이진 트리는 각 노드(부모)가 최대 2개의 자식(오른쪽 및 왼쪽 상속인)을 갖는 데이터 구조입니다 . 실제로는 이진 검색 트리 와 피라미드 (힙)라는 두 가지 유형의 이진 트리가 일반적으로 사용됩니다. 오늘은 이진 검색 트리에 대해 알아보겠습니다.

이진 트리의 이점

데이터를 이진 검색 트리로 저장하면 어떤 이점이 있나요? 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)) 입니다 .

이진 검색 트리 구성 규칙

이진 검색 트리는 특정 규칙에 따라 구축됩니다.

• 각 노드에는 최대 2개의 자식이 있습니다.
• 노드의 값보다 작은 모든 값은 왼쪽 자식 또는 왼쪽 자식의 자식이 됩니다.
• 노드의 값보다 크거나 같은 모든 값은 오른쪽 자식 또는 오른쪽 자식의 자식이 됩니다.

예를 들어, 1부터 10까지의 일련의 숫자가 있습니다. 이 계열의 이진 검색 트리가 어떻게 생겼는지 살펴보겠습니다. 여기서 이진 트리의 모든 조건이 충족되는지 생각해 보겠습니다.

• 모든 노드에는 상속인이 2명 이하인 경우 첫 번째 조건이 충족됩니다.
• 예를 들어 값이 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) 의 시간 복잡도에 접근합니다 .

어떤 경우에 나무가 퇴화될 수 있나요?

예를 들어 정렬된 요소 목록을 추가하는 경우입니다. 목록이 오름차순으로 정렬되면 루트가 첫 번째가 되고 각각 가장 작은 것이 됩니다. 그 다음 사람이 올바른 아이의 위치를 ​​​​차지할 것입니다. 그리고 그 뒤에 오는 항목은 두 번째 항목보다 크고 오른쪽 후속 항목의 위치를 ​​차지하게 됩니다. 목록이 내림차순으로 되어 있으면 동일한 일이 발생하지만 가장 왼쪽 요소에 대해 발생합니다. 이를 방지하려면 여러 요소를 받은 후 간단히 혼합하면 됩니다. 그러면 정렬이 사라지고 숫자가 트리 전체에 어느 정도 고르게 분산됩니다. 오늘은 여기까지입니다. 관심을 가져주셔서 감사합니다!