Сохторҳои маълумот: дарахти дуӣ дар 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.

Ба ҷои 77 қадам, ба мо танҳо 7 қадам лозим буд! Мушкorи вақти ин ҷустуҷӯ 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) наздик мешаванд .

Дар кадом ҳолат дарахт метавонад хароб шавад?

Масалан, агар шумо рӯйхати унсурҳои мураттабшударо илова кунед. Агар рӯйхат бо тартиби афзоиш мураттаб карда шавад, он гоҳ реша аввал, мутаносибан хурдтарин хоҳад буд. Нафари баъд аз ӯ вазифаи фарзанди дурустро мегирад. Ва он ки пас аз он меояд, аз дуюм калонтар мешавад ва мавќеи вориси рости худро мегирад ва ѓайра... Агар рўйхат бо тартиби камшавї бошад, њамон чиз рўй медињад, вале бо унсурњои чаптарин. Барои пешгирӣ кардани ин, пас аз гирифтани як қатор элементҳо, шумо метавонед онҳоро танҳо омехта кунед. Он гоҳ навъбандӣ аз байн меравад ва рақамҳо дар тамоми дарахт каму беш баробар пароканда мешаванд. Ин ҳама барои имрӯз аст, ташаккур барои таваҷҷӯҳатон!