Maglumatlaryň gurluşlary: Java-da ikilik agajy

Salam Salam! Esasy bilimsiz güýçli programmist bolmak kyn. Bu ýerde diňe bir ene programmirleme diliniň sintaksisini bilmek bilen çäklenmän, umuman programmirlemegiň esaslaryny we düşünjelerini hem göz öňünde tutýarys. Bu esaslaryň biri algoritmler we maglumatlar gurluşlarydyr. Düzgün bolşy ýaly, käbirleri bu meselede has bilimli, käbirleri az, ýöne her kimiň bilmeli käbir esasy maglumatlary bar. Maglumat gurluşlary üçin maglumat bazalarynyň arasynda ikilik gözleg agaçlaryna düşünmek hökman. Aslynda, bu gün gurluşyň aýratynlyklary bilen seredip, Java-da ikilik agajyny nädip durmuşa geçirip boljakdygyny öwreneris . Ilki bilen ikilik agajynyň nämedigini anyklalyň. Ikilik agajy, her düwüniň (ene-atanyň) iň azyndan iki çagasy bolan (sag we çep mirasçy) maglumat gurluşydyr . Iş ýüzünde ikilik agaçlarynyň iki görnüşi köplenç ulanylýar - ikilik gözleg agajy we piramida (üýşmek). Bu gün ikilik gözleg agajyna serederis.

Ikilik agajynyň peýdalary

Ikilik gözleg agajy hökmünde maglumatlary saklamagyň artykmaçlygy näme? 100 sahypalyk salgylanma kitabymyzyň bardygyny göz öňüne getiriň we bize zerur maglumatlary öz içine alýan belli bir sahypa tapmalydyrys. Şeýle hem mazmundan haýsy anyk sahypa gerekdigini bilýäris. Adaty ýoldan ýöresek, zerur bir ýere barýançak bir gezekde bir sahypany öwürmeli bolarys. .Agny, özümizi dogry ýerde tapýançak 1-den 100 sahypa çenli geçeris. Mysal üçin, 77-nji sahypa gerek bolsa, 77 gözlegimiz bolar. Wagt çylşyrymlylygy hakda aýtsak, O (N) bolar . Emma muny has netijeli edip bolar, şeýlemi? Edil şol bir zady etmäge synanyşalyň, ýöne ikilik gözlegini ulanyp :

1. Katalogy iki bölege bölýäris, birinjisi - 1-den 50-ä, ikinjisi - 51-100. Sahypamyzyň bu bölekleriň haýsydygyny anyk bilýäris: ýene 77-nji sahypany alsak, kitabyň ikinji bölüminde.
2. Ondan soň, ikinji bölümi göz öňünde tutýarys we ikä bölýäris - 51-den 75-e, 76-dan 100-e çenli. Bu ýagdaýda sahypamyz ikinji ýarymda, 76-100 aralygynda bolar.
3. Ondan soň bu aralygy 2-ä bölýäris we 76-88 we 89-100 alarys. Sahypa birinji boşluga gabat gelýär, şonuň üçin ikinjisini taşlaýarys.
4. Indiki aralyklar: 76-81 we 82-88, birinjisini alyň.
5. 76-78 we 79-81, birinjisini alyň.
6. 76 we 77-78, ikinjisini alyň.
7. 77 we 78, birinjisini alyň we sahypamyzy alyň - 77.

77 ädimiň ýerine diňe 7 gerekdi! Bu gözlegiň wagt çylşyrymlylygy O (log (N)) bolar .

Ikilik gözleg agajy gurmagyň düzgünleri

Ikilik gözleg agajy käbir düzgünlere laýyklykda gurulýar:

• her düwüniň azyndan iki çagasy bar;
• düwüniň bahasyndan pes bolan her bir baha çep çaga ýa-da çep çaganyň çagasy bolýar;
• düwüniň bahasyndan uly ýa-da deň bolan her bir baha dogry çaga ýa-da dogry çaganyň çagasyna öwrülýär.

Mysal üçin, 1-den 10-a çenli sanlarymyz bar. Geliň, bu seriýa üçin ikilik gözleg agajynyň nähili boljakdygyny göreliň: Geliň, ikilik agajynyň ähli şertleriniň ýerine ýetirilendigi barada pikir edeliň:

• ähli düwünleriň iki mirasdüşeri ýok, birinji şert ýerine ýetirilýär;
• meselem, 7 (ýa-da başga) bahasy bolan düwün göz öňünde tutsak, çep aşaky elementdäki elementleriň ähli bahalarynyň az, sagda bolsa has köp boljakdygyny göreris. Bu 2-nji we 3-nji şertleriň ýerine ýetirilendigini aňladýar.

Esasy amallaryň nähili bolýandygyna seredeliň - goýmak, pozmak, gözlemek.

Bir element gözläň

Berlen bahaly element gözlänimizde kök elementinden başlaýarys:

1. Islenýän baha deň bolsa, kök elementi islenýär, ýok bolsa, kökiň we islenýäniň bahalaryny deňeşdirýäris.
2. Gözleýän elementimiz has uly bolsa, sag çaga geçýäris, ýok bolsa, çep çaga geçýäris.
3. Eger element tapylmasa, 1-nji we 2-nji ädimleri ulanyň, ýöne element tapylýança çaga (sag ýa-da çep) ulanyň.

Mysal üçin, ýokarda görkezilen ikilik gözleg agajynda 5 bahasy bolan elementi tapmak isleýäris:

• kök elementi bilen deňeşdirýäris, kök elementiniň has uludygyny görýäris, şonuň üçin 3 bahasy bolan çep çaga geçýäris;
• gözleýän zadymyzy we elementi 3 bahasy bilen deňeşdirýäris, gözleýänimiziň has uludygyny görýäris, şonuň üçin sorag edilýän elementiň dogry nesli, ýagny 5 bahasy bolan element gerek;
• Bu nesli gözleýän adamymyz bilen deňeşdirýäris we bahalaryň deňdigini görýäris - element tapylýar.

Bir element goýmak

Goýmak algoritmi hem gaty ýönekeý:

1. Täzesini kök bilen deňeşdirýäris (ýok bolsa, täze element kök).

2. Täze element bolsa:

   • az, soň çep mirasdüşeriň ýanyna barýarys; ýok bolsa, täze element çep mirasdüşeriň ýerini alýar we algoritm tamamlanýar;
   • kökünden uludyr ýa-da deňdir, soň sag mirasdüşere geçeris. Şonuň ýaly-da, bu element ýok bolsa, täze element dogry elementiň ýerini alar we algoritm tamamlanar.

3. Öňki ädimden sag ýa-da çep bolan täze element üçin, goýlan element ýerine ýetýänçä 1-nji we 2-nji ädimleri gaýtalaň.

   Mysal üçin, ýokarda seredilen agaja, 11 bahasy bolan elementi goýmak isleýäris:

   • kök elementi 7 bilen deňeşdirýäris we kök elementiniň kiçidigini görýäris, şonuň üçin sag mirasdüşere geçýäris;
   • seredilýän indiki elementiň 9 bahasy bar, bu täze 11-den pes däl, şonuň üçin sag mirasdüşere geçýäris;
   • dogry mirasdüşeriň 10 bahasy bar, bu ýene-de az, şonuň üçin birinji elemente geçýäris we ol ýerde ýoklugy sebäpli bu ýerde 11 bahasy bolan täze element ýerleşdirilýär.
   ↓

Bir elementi aýyrmak

Ikilik gözleg agaçlary bilen geçirilen ähli amallardan öçürmek iň kyn zat bolsa gerek. Ilki bilen, elementiň öçürilmegi üçin gözleg bar, ondan soň üç üýtgeşiklige eýe bolup biljek bir basgançak bar:

1. Öçürilmeli düwün ýaprak düwünidir (çagasy ýok).

   Iň ýönekeý bolmagy mümkin. Bularyň hemmesi, gereksiz manipulýasiýa etmezden, ony agaçdan kesendigimize degişlidir. Mysal üçin, agajymyzdan 8 bahasy bilen düwün aýyrýarys:

   ↓

2. Öçürilýän düwüniň bir çagasy bar.

   Bu ýagdaýda saýlanan düwünleri pozýarys we onuň neslini onuň ýerine goýýarys (aslynda, saýlanan düwünleri zynjyrdan kesýäris). Mysal üçin, agaçdan 9 bahasy bolan düwün aýyralyň:

   ↓

3. Öçürilýän düwüniň iki çagasy bar.

   Iň gyzykly bölüm. Galyberse-de, öçürilýän düwün birbada iki çagasy bar bolsa, ony diňe şu çagalaryň biri bilen çalşyp bilmersiňiz (esasanam çaganyň öz çagalary bar bolsa).

   Mysal: aboveokardaky agaçda haýsy düwün 3 düwüniň çep çagasy bolmaly?

   Biraz pikirlenip görseň, munuň 4 bahaly düwün bolmalydygy äşgär bolýar, ýöne agaç beýle ýönekeý bolmasa näme etmeli? Hundredsüzlerçe gymmatlyklary saklaýan bolsa, mirasdüşeriň kimdigini anyklamak aňsat bolarmy?

   Nook. Şonuň üçin bize kiçijik kabul edijiniň gözleg algoritmi gerek:

   1. Ilki bilen, düwüniň bahasyndan uly bolmaly saýlanan düwüniň sag çagasyna gitmeli.
   2. Soňra çep çagalaryň zynjyryna eýerip, sag çaganyň çep çagasyna (biri bar bolsa), çep çaganyň çep çagasyna we ş.m.
   3. Şoňa laýyklykda bu ýolda soňky çep çaga asyl düwüniň mirasdüşeri bolar.

   Geliň, bu kiçijik algoritmi biraz umumylaşdyralyň: çeşme düwüniniň sag çagasynyň aşaky böleginde, düwünleriň ikisiniň gözleg agajynyň esasy düzgünlerinden düşünip boljak pozulýanlardan has uludyr. Bu subtree-de iň kiçi bahany gözleýäris.

   Başgaça aýdylanda, asyl düwünden has uly düwünler toplumynda iň kiçi düwün gözleýäris. Ulylaryň arasynda bu kiçijik düwün iň amatly mirasdüşer bolar.

   3 bahasy bolan düwün aýrylandan soň agajyň görnüşi:

   ↓

Indi praktikadan teoriýa geçmegiň wagty geldi. Java-da bu maglumat gurluşyny nädip karta edip biljekdigimize göz aýlalyň. Neke düwün synpy:

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

Gaty çylşyrymly zat ýok: her elementiň çep we sag çagasy bilen baglanyşygy bar. Indi, ähtimal, iň möhüm synp agaç synpydyr:

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

Againene-de gaty çylşyrymly zat ýok. Öň beýan edilen ikilik gözleg agajynyň amallary, üstesine-de agajy konsolda görkezmegiň usuly bar. Bolýar, indi hereket edýän agaja göz aýlalyň:

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

Ikilik gözleg agajynda gözlemek / goýmak / aýyrmak amallary O (log (N)) çylşyrymlylygyna eýe . That'söne bu iň gowy senari. Umuman, amallaryň wagt çylşyrymlylygy O (log (N)) -dan O (N) aralygynda bolýar . Bu agajyň ýaramazlaşma derejesine baglydyr.

Eneraramaz agaç näme?

Bu, iň çep düwün (iň kiçi san) ýa-da iň uly düwün (iň uly) ýagdaýyna goşulanda elementleriň düşen agajydyr. Bu, meselem, çep agaçlaryň her derejesinde boş bolsa, diňe sag agaçlar bar bolsa, bu ýagdaýda agaç sanawda (sag tarapda) peselse bolup biler. Hawa, şeýdip, bozulan agaç täsirli birleşdirilen sanawa öwrülýär, onda her element diňe gapdalyndakylary bilýär. Bu ýagdaýda bu gurluşdaky ähli amallar O (N) wagt çylşyrymlylygyna ýakynlaşýar .

Haýsy ýagdaýda agaç ýaramazlaşyp biler?

Mysal üçin, sortlanan elementleriň sanawyny goşsaňyz. Sanaw ýokarlanýan tertipde tertiplenen bolsa, kök degişlilikde iň kiçi bolar. Ondan soňky biri dogry çaganyň ornuny alar. Ondan soň gelýän bolsa ikinjisinden has uly bolar we dogry mirasdüşerini alar we ş.m. ... Sanaw aşak tertipde bolsa, şol bir zat bolar, ýöne iň çep elementler bilen. Munuň öňüni almak üçin, birnäçe elementi alanyňyzdan soň, olary garyşdyryp bilersiňiz. Soňra sortlamak ýok bolar we sanlar agajyň hemme ýerine deň derejede dargap başlar. Bularyň hemmesi şu gün üçin, üns bereniňiz üçin sag boluň!