Mga Istraktura ng Data: Binary Tree sa Java

Hi Hi! Mahirap maging isang malakas na programmer nang walang pangunahing kaalaman. At dito ang ibig naming sabihin ay hindi lamang kaalaman sa syntax ng katutubong programming language, kundi pati na rin ang mga pangunahing kaalaman at konsepto ng programming sa pangkalahatan. Isa sa mga pundasyong ito ay mga algorithm at istruktura ng data. Bilang isang tuntunin, ang ilan ay mas may kaalaman sa isyung ito, ang ilan ay mas mababa, ngunit mayroong ilang pangunahing impormasyon na dapat malaman ng lahat. Kabilang sa mga database para sa mga istruktura ng data, tiyak na sulit na maunawaan ang mga binary search tree. Sa totoo lang, titingnan natin ngayon ang mismong istraktura kasama ang mga tampok nito at alamin kung paano mo maipapatupad ang isang binary tree sa Java . Una, alamin natin kung ano ang isang binary tree. Ang binary tree ay isang istraktura ng data kung saan ang bawat node (magulang) ay may hindi hihigit sa dalawang anak (kanan at kaliwang tagapagmana). Sa pagsasagawa, dalawang uri ng binary tree ang karaniwang ginagamit - binary search tree at pyramid (heap). Ngayon ay titingnan natin ang isang binary search tree.

Mga Benepisyo ng Binary Tree

Ano ang bentahe ng pag-iimbak ng data bilang isang binary search tree? Isipin na mayroon kaming 100-pahinang reference na libro at kailangan naming maghanap ng isang partikular na pahina na maglalaman ng data na kailangan namin. Alam din namin mula sa nilalaman kung aling partikular na pahina ang kailangan namin. Kung susundin natin ang karaniwang landas, kailangan nating buksan ang isang pahina nang paisa-isa hanggang makarating tayo sa kailangan natin. Ibig sabihin, dadaan tayo mula 1 hanggang 100 pages hanggang sa makita natin ang ating sarili sa tamang lugar. Halimbawa, kung kailangan namin ng pahina 77, magkakaroon kami ng 77 na paghahanap. Kung pag-uusapan natin ang pagiging kumplikado ng oras, ito ay magiging O(N) . Ngunit ito ay maaaring gawin nang mas mahusay, tama? Subukan nating gawin ang parehong bagay, ngunit gamit ang binary search :

1. Hinahati namin ang direktoryo sa dalawang bahagi, ang una - mula 1 hanggang 50, ang pangalawa - 51-100. Alam namin kung alin sa mga bahaging ito ang aming pahina: kung kukunin namin muli ang pahina 77, ito ay nasa ikalawang bahagi ng aklat.
2. Susunod, isinasaalang-alang namin ang pangalawang bahagi at hatiin ito sa dalawa - mula 51 hanggang 75, mula 76 hanggang 100. Sa kasong ito, ang aming pahina ay muli sa ikalawang kalahati, sa hanay na 76-100.
3. Susunod, hinati namin ang agwat na ito sa 2 at makakuha ng 76-88 at 89-100. Ang pahina ay umaangkop sa unang puwang, kaya itinatapon namin ang pangalawa.
4. Susunod ay ang mga pagitan: 76-81 at 82-88, kunin ang una.
5. 76-78 at 79-81, kunin ang una.
6. 76 at 77-78, kunin ang pangalawa.
7. 77 at 78, kunin ang una at kunin ang aming pahina - 77.

Sa halip na 77 hakbang, kailangan lang namin ng 7! Ang pagiging kumplikado ng oras ng paghahanap na ito ay magiging O(log(N)) .

Mga panuntunan para sa pagbuo ng isang binary search tree

Ang binary search tree ay binuo ayon sa ilang mga patakaran:

• bawat node ay may hindi hihigit sa dalawang anak;
• bawat value na mas mababa sa value ng node ay nagiging kaliwang anak o anak ng kaliwang bata;
• bawat halagang mas malaki sa o katumbas ng halaga ng node ay nagiging tamang bata o anak ng tamang bata.

Halimbawa, mayroon kaming isang serye ng mga numero mula 1 hanggang 10. Tingnan natin kung ano ang magiging hitsura ng binary search tree para sa seryeng ito: Pag-isipan natin kung ang lahat ng kundisyon ng isang binary tree ay natutugunan dito:

• lahat ng mga node ay may hindi hihigit sa dalawang tagapagmana, ang unang kondisyon ay natutugunan;
• kung isasaalang-alang natin, halimbawa, ang isang node na may halagang 7 (o anumang iba pa), makikita natin na ang lahat ng mga halaga ng mga elemento sa kaliwang subtree ay magiging mas kaunti, at sa kanan - higit pa. Nangangahulugan ito na ang mga kondisyon 2 at 3 ay natutugunan.

Tingnan natin kung paano nangyayari ang mga pangunahing operasyon - pagpasok, pagtanggal, paghahanap.

Maghanap ng isang elemento

Kapag naghahanap ng isang elemento na may ibinigay na halaga, magsisimula tayo sa root element:

1. Kung ito ay katumbas ng nais na halaga, ang elemento ng ugat ay ang nais; kung hindi, ihahambing natin ang mga halaga ng ugat at ang nais.
2. Kung mas malaki ang elementong hinahanap natin, lilipat tayo sa kanang bata; kung hindi, lilipat tayo sa kaliwang bata.
3. Kung hindi natagpuan ang elemento, ilapat ang mga hakbang 1 at 2, ngunit sa bata (kanan o kaliwa) hanggang sa matagpuan ang elemento.

Halimbawa, sa binary search tree na ipinapakita sa itaas, gusto naming hanapin ang elementong may value na 5:

• inihambing namin ito sa elemento ng ugat, nakita namin na ang elemento ng ugat ay mas malaki, kaya lumipat kami sa kaliwang bata, na may halaga na 3;
• ikinukumpara natin ang hinahanap natin at ang elementong may halagang 3, nakikita natin na mas malaki ang hinahanap natin, kaya kailangan natin ang tamang inapo ng elementong pinag-uusapan, ibig sabihin, ang elementong may halagang 5;
• Inihambing namin ang inapo na ito sa hinahanap namin at nakita namin na ang mga halaga ay pantay - natagpuan ang elemento.

Paglalagay ng elemento

Ang insertion algorithm ay napaka-simple din:

1. Inihahambing namin ang bago sa ugat (kung wala ito, ang bagong elemento ay ang ugat).

2. Kung may bagong elemento:

   • ay mas mababa, pagkatapos ay pumunta kami sa kaliwang tagapagmana, kung wala, ang bagong elemento ay pumapalit sa kaliwang tagapagmana, at ang algorithm ay nakumpleto;
   • ay mas malaki kaysa o katumbas ng ugat, pagkatapos ay lumipat tayo sa tamang tagapagmana. At katulad nito, kung ang elementong ito ay hindi umiiral, pagkatapos ay isang bagong elemento ang papalit sa tamang elemento at ang algorithm ay nakumpleto.

3. Para sa bagong elementong pinag-uusapan, na nasa kanan o kaliwa mula sa nakaraang hakbang, ulitin ang mga hakbang 1 at 2 hanggang sa mailagay ang ipinasok na elemento.

   Bilang halimbawa, gugustuhin naming ipasok sa puno na isinasaalang-alang sa itaas, isang elemento na may halagang 11:

   • inihambing natin ang elementong ugat 7 at nakikita na mas maliit ang elemento ng ugat, kaya nagpapatuloy tayo sa tamang tagapagmana;
   • ang susunod na elemento na isinasaalang-alang ay may halaga na 9, na mas mababa kaysa sa bagong 11, kaya lumipat kami sa tamang tagapagmana;
   • ang tamang tagapagmana ay may halaga na 10, na muli ay mas mababa, kaya pumunta kami sa unang elemento, at dahil wala ito, isang bagong elemento na may halaga na 11 ay inilalagay sa lugar na ito.
   ↓

Pag-alis ng isang elemento

Marahil, sa lahat ng mga operasyon na may binary search tree, ang pagtanggal ay ang pinakamahirap. Una sa lahat, mayroong paghahanap para sa elementong tatanggalin, pagkatapos mahanap kung aling yugto ang kasunod, na maaaring magkaroon ng tatlong variation:

1. Ang node na tatanggalin ay isang leaf node (walang mga anak).

   Marahil ang pinakasimpleng. Ang lahat ay nagmumula sa katotohanan na pinutol lamang natin ito mula sa puno, nang walang hindi kinakailangang pagmamanipula. Halimbawa, mula sa aming puno ay tinanggal namin ang node na may halagang 8:

   ↓

2. Ang node na tinatanggal ay may isang anak.

   Sa kasong ito, tinanggal namin ang napiling node at inilagay ang inapo nito sa lugar nito (sa esensya, pinutol lang namin ang napiling node mula sa chain). Bilang halimbawa, tanggalin natin ang isang node na may halagang 9 mula sa puno:

   ↓

3. Ang node na tinatanggal ay may dalawang anak.

   Ang pinaka-kagiliw-giliw na bahagi. Pagkatapos ng lahat, kung ang node na tinatanggal ay may dalawang anak nang sabay-sabay, hindi mo basta-basta maaaring palitan ito ng isa sa mga batang ito (lalo na kung ang bata ay may sariling mga anak).

   Halimbawa: Sa puno sa itaas, aling node ang dapat na kaliwang anak ng node 3?

   Kung iisipin mo ito ng kaunti, nagiging halata na dapat itong isang node na may halaga na 4. Ngunit paano kung ang puno ay hindi gaanong simple? Kung nagtataglay ito ng daan-daang halaga, magiging ganoon ba kadaling malaman kung sino ang magiging kahalili?

   Malinaw na hindi. Samakatuwid, kailangan namin ng sarili naming maliit na algorithm sa paghahanap ng receiver:

   1. Una kailangan nating pumunta sa kanang anak ng napiling node, na ang halaga ay dapat na mas malaki kaysa sa halaga ng node.
   2. Pagkatapos ay lumipat tayo sa kaliwang anak ng kanang bata (kung mayroon), pagkatapos ay sa kaliwang anak ng kaliwang bata, atbp., na sumusunod sa kadena ng mga kaliwang bata.
   3. Alinsunod dito, ang huling kaliwang bata sa landas na ito ang magiging kahalili ng orihinal na node.

   I-generalize natin nang kaunti ang maliit na algorithm na ito: sa subtree ng kanang anak ng source node, lahat ng node ay mas malaki kaysa sa tinatanggal, na mauunawaan mula sa mga pangunahing panuntunan ng binary search tree. Sa subtree na ito hinahanap namin ang pinakamaliit na halaga.

   Sa madaling salita, hinahanap namin ang pinakamaliit na node sa isang hanay ng mga node na mas malaki kaysa sa orihinal na node. Ang pinakamaliit na node sa mga mas malalaking node ang magiging pinakaangkop na kahalili.

   Ano ang magiging hitsura ng puno pagkatapos alisin ang node na may halaga 3:

   ↓

Ngayon ay oras na upang lumipat mula sa pagsasanay patungo sa teorya. Tingnan natin kung paano natin maipapakita ang istruktura ng data na ito sa Java. Isang klase ng node:

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

Walang masyadong kumplikado: ang bawat elemento ay may link sa kaliwa at kanang anak nito. At ngayon, marahil, ang pinakamahalagang klase ay ang klase ng puno:

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

Muli, walang masyadong kumplikado. Ang mga operasyon ng binary search tree na inilarawan kanina ay naroroon, kasama ang isang paraan para sa pagpapakita ng puno sa console. Well, ngayon tingnan natin ang puno na kumikilos:

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

Ang paghahanap/insert/delete na mga operasyon sa isang binary search tree ay may time complexity ng O(log(N)) . Ngunit iyon ang pinakamagandang senaryo ng kaso. Sa pangkalahatan, ang pagiging kumplikado ng oras ng mga operasyon ay mula sa O(log(N)) hanggang O(N) . Depende ito sa antas ng pagkabulok ng puno.

Ano ang degenerate tree?

Ito ang puno kung saan nahulog ang mga elemento kapag idinagdag sa posisyon ng pinakakaliwang node (pinakamaliit na bilang) o ang pinakamalaking node (pinakamalaking). Maaaring mangyari ito kung, halimbawa, ang buong kaliwang puno ay walang laman sa bawat antas, mayroon lamang mga tamang puno, kung saan ang puno ay bumagsak sa isang listahan (pumupunta sa kanan). Oo, ito ay kung paano ang isang bulok na puno ay epektibong nagiging isang solong naka-link na listahan, kung saan ang bawat elemento ay alam lamang ang tungkol sa susunod. Sa kasong ito, ang lahat ng mga operasyon sa istrukturang ito ay lumalapit sa pagiging kumplikado ng oras ng O(N) .

Sa anong kaso maaaring maging degenerate ang isang puno?

Halimbawa, kung nagdagdag ka ng listahan ng mga pinagsunod-sunod na elemento. Kung ang listahan ay pinagsunod-sunod sa pataas na pagkakasunud-sunod, kung gayon ang ugat ang magiging una, ayon sa pagkakabanggit, ang pinakamaliit. Ang susunod na susunod sa kanya ay kukunin ang posisyon ng tamang bata. At ang susunod ay magiging mas malaki kaysa sa pangalawa at kukuha ng posisyon ng kanang kahalili nito, at iba pa... Kung ang listahan ay nasa pababang pagkakasunud-sunod, kung gayon ang parehong bagay ang mangyayari, ngunit sa pinakakaliwang elemento. Upang maiwasan ito, pagkatapos makatanggap ng isang bilang ng mga elemento, maaari mo lamang ihalo ang mga ito. Pagkatapos ay mawawala ang pag-uuri, at ang mga numero ay magiging higit pa o hindi gaanong pantay na nakakalat sa buong puno. Iyon lang para sa araw na ito, salamat sa iyong pansin!