Cấu trúc dữ liệu: Cây nhị phân trong Java

Xin chào Xin chào! Thật khó để trở thành một lập trình viên giỏi nếu không có kiến ​​thức cơ bản. Và ở đây chúng tôi không chỉ muốn nói đến kiến ​​thức về cú pháp của ngôn ngữ lập trình gốc mà còn cả các nguyên tắc cơ bản và khái niệm về lập trình nói chung. Một trong những nền tảng này là thuật toán và cấu trúc dữ liệu. Theo quy định, một số người hiểu biết nhiều hơn về vấn đề này, một số ít hơn, nhưng có một số thông tin cơ bản mà mọi người nên biết. Trong số các cơ sở dữ liệu về cấu trúc dữ liệu, chắc chắn cần phải hiểu cây tìm kiếm nhị phân. Trên thực tế, hôm nay chúng ta sẽ xem xét cấu trúc với các tính năng của nó và tìm hiểu cách bạn có thể triển khai cây nhị phân trong Java . Đầu tiên, chúng ta hãy tìm hiểu cây nhị phân là gì. Cây nhị phân là một cấu trúc dữ liệu trong đó mỗi nút (mẹ) có tối đa hai con (người thừa kế bên phải và bên trái). Trong thực tế, hai loại cây nhị phân thường được sử dụng là cây tìm kiếm nhị phân và kim tự tháp (heap). Hôm nay chúng ta sẽ xem xét cây tìm kiếm nhị phân.

Lợi ích của cây nhị phân

Ưu điểm của việc lưu trữ dữ liệu dưới dạng cây tìm kiếm nhị phân là gì? Hãy tưởng tượng rằng chúng ta có một cuốn sách tham khảo 100 trang và chúng ta cần tìm một trang cụ thể chứa dữ liệu chúng ta cần. Chúng tôi cũng biết từ nội dung trang cụ thể nào chúng tôi cần. Nếu đi theo con đường thông thường, chúng ta sẽ phải lật từng trang một cho đến khi đến được trang mình cần. Tức là chúng ta sẽ xem từ 1 đến 100 trang cho đến khi tìm đúng chỗ. Ví dụ ta cần trang 77 thì ta sẽ có 77 lượt tìm kiếm. Nếu chúng ta nói về độ phức tạp về thời gian thì nó sẽ là O(N) . Nhưng điều này có thể được thực hiện hiệu quả hơn, phải không? Hãy thử làm điều tương tự nhưng sử dụng tìm kiếm nhị phân :

1. Chúng tôi chia thư mục thành hai phần, phần thứ nhất - từ 1 đến 50, phần thứ hai - 51-100. Chúng tôi biết chính xác trang của chúng tôi nằm ở phần nào: nếu chúng tôi xem lại trang 77, nó sẽ nằm ở phần thứ hai của cuốn sách.
2. Tiếp theo, chúng tôi xem xét phần thứ hai và chia nó thành hai - từ 51 đến 75, từ 76 đến 100. Trong trường hợp này, trang của chúng tôi sẽ lại ở nửa sau, trong khoảng 76-100.
3. Tiếp theo, chúng ta chia khoảng này cho 2 và nhận được 76-88 và 89-100. Trang này vừa với khoảng trống đầu tiên, vì vậy chúng tôi loại bỏ khoảng trống thứ hai.
4. Tiếp theo là các khoảng: 76-81 và 82-88, lấy khoảng đầu tiên.
5. 76-78 và 79-81, lấy cái đầu tiên.
6. 76 và 77-78, lấy cái thứ hai.
7. 77 và 78, lấy cái đầu tiên và lấy trang của chúng tôi - 77.

Thay vì 77 bước, chúng ta chỉ cần 7! Độ phức tạp về thời gian của tìm kiếm này sẽ là O(log(N)) .

Quy tắc xây dựng cây tìm kiếm nhị phân

Cây tìm kiếm nhị phân được xây dựng theo những quy tắc nhất định:

• mỗi nút có nhiều nhất hai nút con;
• mọi giá trị nhỏ hơn giá trị của nút sẽ trở thành con trái hoặc con của con trái;
• mọi giá trị lớn hơn hoặc bằng giá trị của nút sẽ trở thành con bên phải hoặc con của con bên phải.

Ví dụ: chúng ta có một chuỗi số từ 1 đến 10. Hãy xem cây tìm kiếm nhị phân cho chuỗi này sẽ trông như thế nào: Hãy suy nghĩ xem liệu tất cả các điều kiện của cây nhị phân có được đáp ứng ở đây hay không:

• tất cả các nút có không quá hai người thừa kế, điều kiện đầu tiên được đáp ứng;
• Ví dụ: nếu chúng ta xem xét một nút có giá trị 7 (hoặc bất kỳ giá trị nào khác), chúng ta sẽ thấy rằng tất cả các giá trị của các phần tử trong cây con bên trái sẽ ít hơn và ở bên phải - nhiều hơn. Điều này có nghĩa là điều kiện 2 và 3 được đáp ứng.

Hãy xem các thao tác cơ bản diễn ra như thế nào - chèn, xóa, tìm kiếm.

Tìm kiếm một phần tử

Khi tìm kiếm một phần tử có giá trị nhất định, chúng ta bắt đầu từ phần tử gốc:

1. Nếu nó bằng giá trị mong muốn thì phần tử gốc là phần tử mong muốn, nếu không, chúng ta so sánh giá trị của phần tử gốc và phần tử mong muốn.
2. Nếu phần tử chúng ta đang tìm kiếm lớn hơn, chúng ta chuyển sang phần tử con bên phải; nếu không, chúng ta chuyển sang phần tử con bên trái.
3. Nếu không tìm thấy phần tử, hãy áp dụng bước 1 và 2 nhưng với phần tử con (phải hoặc trái) cho đến khi tìm thấy phần tử.

Ví dụ: trong cây tìm kiếm nhị phân hiển thị ở trên, chúng tôi muốn tìm phần tử có giá trị 5:

• ta so sánh với phần tử gốc, thấy phần tử gốc lớn hơn nên chuyển sang phần tử con bên trái, phần tử này có giá trị là 3;
• chúng tôi so sánh phần tử chúng tôi đang tìm kiếm và phần tử có giá trị 3, chúng tôi thấy rằng phần tử chúng tôi đang tìm kiếm lớn hơn, vì vậy chúng tôi cần phần tử con bên phải của phần tử được đề cập, cụ thể là phần tử có giá trị 5;
• Chúng tôi so sánh hậu duệ này với hậu duệ mà chúng tôi đang tìm kiếm và thấy rằng các giá trị bằng nhau - phần tử được tìm thấy.

Chèn một phần tử

Thuật toán chèn cũng rất, rất đơn giản:

1. Chúng ta so sánh phần tử mới với phần tử gốc (nếu nó không tồn tại thì phần tử mới là phần tử gốc).

2. Nếu một phần tử mới:

   • nhỏ hơn thì chuyển sang thừa kế bên trái, nếu không có thì phần tử mới thay thế cho thừa kế bên trái và thuật toán hoàn thành;
   • lớn hơn hoặc bằng gốc thì ta chuyển sang thừa kế bên phải. Và tương tự, nếu phần tử này không tồn tại thì phần tử mới sẽ thay thế phần tử bên phải và thuật toán hoàn thành.

3. Đối với phần tử mới được đề cập, nằm ở bên phải hoặc bên trái so với bước trước, hãy lặp lại bước 1 và 2 cho đến khi phần tử được chèn vào đúng vị trí.

   Ví dụ: chúng ta muốn chèn vào cây được xem xét ở trên một phần tử có giá trị 11:

   • ta so sánh với phần tử gốc 7 và thấy phần tử gốc nhỏ hơn nên chuyển sang phần tử thừa kế bên phải;
   • phần tử tiếp theo đang được xem xét có giá trị là 9, nhỏ hơn 11 mới, vì vậy chúng ta chuyển sang phần tử thừa kế bên phải;
   • người thừa kế bên phải có giá trị là 10, giá trị này lại ít hơn, vì vậy chúng ta chuyển sang phần tử đầu tiên và vì nó không có ở đó nên một phần tử mới có giá trị 11 được đặt ở vị trí này.
   ↓

Loại bỏ một phần tử

Có lẽ, trong tất cả các thao tác với cây tìm kiếm nhị phân, việc xóa là khó khăn nhất. Trước hết, có một cuộc tìm kiếm phần tử cần xóa, sau khi tìm ra giai đoạn tiếp theo, giai đoạn này có thể có ba biến thể:

1. Nút cần xóa là nút lá (không có nút con).

   Có lẽ đơn giản nhất. Tất cả bắt nguồn từ thực tế là chúng ta chỉ cần cắt nó ra khỏi cây mà không cần thao tác không cần thiết. Ví dụ: khỏi cây của chúng tôi, chúng tôi xóa nút có giá trị 8:

   ↓

2. Nút bị xóa có một nút con.

   Trong trường hợp này, chúng tôi xóa nút đã chọn và đặt nút con của nó vào vị trí của nó (về bản chất, chúng tôi chỉ cần cắt nút đã chọn khỏi chuỗi). Ví dụ: hãy xóa nút có giá trị 9 khỏi cây:

   ↓

3. Nút bị xóa có hai nút con.

   Phần thú vị nhất. Rốt cuộc, nếu nút bị xóa có hai nút con cùng một lúc, bạn không thể đơn giản thay thế nó bằng một trong những nút con này (đặc biệt nếu nút đó có con riêng của nó).

   Ví dụ: Trong cây trên, nút nào sẽ là nút con bên trái của nút 3?

   Nếu bạn suy nghĩ một chút, bạn sẽ thấy rõ ràng rằng đây phải là một nút có giá trị là 4. Nhưng nếu cái cây không đơn giản như vậy thì sao? Nếu nó chứa hàng trăm giá trị, liệu ai sẽ là người kế vị dễ dàng đến thế?

   Rõ ràng là không. Vì vậy, chúng ta cần thuật toán tìm kiếm máy thu nhỏ của riêng mình:

   1. Đầu tiên chúng ta phải đi tới nút con bên phải của nút đã chọn, giá trị của nút này phải lớn hơn giá trị của nút.
   2. Sau đó chúng ta chuyển sang con trái của con phải (nếu có), rồi đến con trái của con trái, v.v., theo chuỗi con trái.
   3. Theo đó, nút con cuối cùng còn lại trên đường dẫn này sẽ là nút kế thừa của nút ban đầu.

   Chúng ta hãy khái quát hóa thuật toán nhỏ này một chút: trong cây con của nút con bên phải của nút nguồn, tất cả các nút đều lớn hơn nút bị xóa, điều này có thể hiểu được từ các quy tắc cơ bản của cây tìm kiếm nhị phân. Trong cây con này, chúng tôi đang tìm kiếm giá trị nhỏ nhất.

   Nói cách khác, chúng ta đang tìm nút nhỏ nhất trong tập hợp các nút lớn hơn nút ban đầu. Nút nhỏ nhất này trong số các nút lớn hơn sẽ là nút kế thừa phù hợp nhất.

   Cây sẽ trông như thế nào sau khi loại bỏ nút có giá trị 3:

   ↓

Bây giờ là lúc chuyển từ thực hành sang lý thuyết. Chúng ta hãy xem cách chúng ta có thể hiển thị cấu trúc dữ liệu này trong Java. Lớp nút đơn:

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 +
               '}';
   }
}

Không có gì quá phức tạp: mỗi phần tử có một liên kết đến phần con bên trái và bên phải của nó. Và bây giờ, có lẽ lớp quan trọng nhất là lớp cây:

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);// подводим черту
   }
}

Một lần nữa, không có gì quá phức tạp. Các hoạt động của cây tìm kiếm nhị phân được mô tả trước đó đều có sẵn, cùng với một phương pháp hiển thị cây trong bảng điều khiển. Bây giờ chúng ta hãy quan sát hoạt động của cây:

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();
   }
}

Các thao tác tìm kiếm/chèn/xóa trong cây tìm kiếm nhị phân có độ phức tạp về thời gian là O(log(N)) . Nhưng đó là trường hợp tốt nhất. Nói chung, độ phức tạp về thời gian của các hoạt động nằm trong khoảng từ O(log(N)) đến O(N) . Nó phụ thuộc vào mức độ thoái hóa của cây.

Cây thoái hóa là gì?

Đây là cây trong đó các phần tử rơi xuống khi được thêm vào vị trí của nút ngoài cùng bên trái (số nhỏ nhất) hoặc nút lớn nhất (lớn nhất). Điều này có thể xảy ra nếu, ví dụ, toàn bộ cây bên trái trống ở mỗi cấp, chỉ có cây bên phải, trong trường hợp đó cây thoái hóa thành một danh sách (đi về bên phải). Đúng, đây là cách một cây suy biến trở thành một danh sách liên kết đơn một cách hiệu quả, trong đó mỗi phần tử chỉ biết về phần tử tiếp theo. Trong trường hợp này, tất cả các hoạt động trên cấu trúc này đều có độ phức tạp về thời gian là O(N) .

Trong trường hợp nào cây có thể bị thoái hóa?

Ví dụ: nếu bạn thêm danh sách các phần tử được sắp xếp. Nếu danh sách được sắp xếp theo thứ tự tăng dần thì gốc sẽ là đầu tiên, tương ứng là nhỏ nhất. Người tiếp theo sau anh ta sẽ đảm nhận vị trí con bên phải. Và cái đến sau sẽ lớn hơn cái thứ hai và sẽ chiếm vị trí của người kế thừa bên phải của nó, v.v.... Nếu danh sách theo thứ tự giảm dần thì điều tương tự cũng sẽ xảy ra, nhưng với các phần tử ngoài cùng bên trái. Để tránh điều này, sau khi nhận được một số phần tử, bạn chỉ cần trộn chúng lại với nhau. Sau đó, việc phân loại sẽ biến mất và các con số ít nhiều sẽ nằm rải rác khắp cây. Đó là tất cả cho ngày hôm nay, cảm ơn bạn đã quan tâm!