Маалымат структуралары: Javaдагы бинардык дарак

Салам Салам! Негизги бorмсиз күчтүү программист болуу кыйын. Жана бул жерде биз эне программалоо тorнин синтаксисин гана билбестен, жалпысынан программалоонун негиздерин жана түшүнүктөрүн да айтып жатабыз. Бул негиздер бири алгоритмдер жана маалымат структуралары болуп саналат. Эреже катары, кээ бирлери бул маселе боюнча көбүрөөк бorмдүү, кээ бирлери азыраак, бирок ар бир адам бorши керек болгон негизги маалыматтар бар. Маалымат структуралары үчүн маалымат базаларынын арасында, албетте, экorк издөө дарактарды түшүнүү керек. Чынында, бүгүн биз структуранын өзүн анын өзгөчөлүктөрү менен карап чыгабыз жана Java-да бинардык даракты кантип ишке ашырууга болорун билебиз . Биринчиден, келгиле, бинардык дарак деген эмне экенин аныктап көрөлү. Бинардык дарак – ар бир түйүн (ата-эне) эң көп дегенде эки балага (оң жана сол мураскор) ээ болгон маалымат структурасы . Практикада көбүнчө экorк дарактардын эки түрү колдонулат - бинардык издөө дарагы жана пирамида (үймөк). Бүгүн биз бинардык издөө дарагын карап чыгабыз.

Бинардык дарактын пайдасы

Маалыматтарды экorк издөө дарагы катары сактоонун артыкчылыгы эмнеде? Элестеткиле, бизде 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)) болот .

Бинардык издөө дарагын куруу эрежелери

бинардык издөө дарагы белгилүү эрежелерге ылайык курулган:

• ар бир түйүндө эң көп дегенде эки бала бар;
• түйүндүн маанисинен аз болгон ар бир маани сол бала же сол баланын баласы болуп калат;
• түйүндүн маанисинен чоң же ага барабар ар бир маани туура бала же туура баланын баласы болуп калат.

Мисалы, бизде 1ден 10го чейинки сандар сериясы бар. Келгиле, бул катар үчүн бинардык издөө дарагы кандай болоорун карап көрөлү: Келгиле, бул жерде бинардык дарактын бардык шарттары аткарылабы же жокпу, ойлонуп көрөлү:

• бардык түйүндөр экиден ашык эмес мураскору бар, биринчи шарт аткарылат;
• эгерде биз, мисалы, 7 мааниси бар түйүндү (же башка) карап көрсөк, биз сол поддарактагы элементтердин бардык баалуулуктары азыраак, ал эми оң жакта - көбүрөөк болорун көрөбүз. Бул 2 жана 3-шарттар аткарылганын билдирет.

Келгиле, негизги операциялар кандайча ишке ашарын карап көрөлү - киргизүү, жок кылуу, издөө.

Элемент издөө

Берилген мааниге ээ элементти издөөдө, биз негизги элементтен баштайбыз:

1. Эгерде ал керектүү мааниге барабар болсо, анда тамыр элементи каалаган нерсе болуп саналат, эгерде андай эмес болсо, анда биз тамыр менен керектүү маанилерди салыштырабыз.
2. Эгерде биз издеп жаткан элемент чоңураак болсо, биз оң балага, жок болсо, сол балага жылабыз.
3. Эгерде элемент табылбаса, 1 жана 2-кадамдарды, бирок элемент табылганга чейин балага (оң же сол) колдонуңуз.

Мисалы, жогоруда көрсөтүлгөн экorк издөө дарагында биз 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 мааниси бар түйүндү алып салгандан кийин дарак кандай болот:

   ↓

Эми практикадан теорияга өтүү мезгor келди. Келгиле, бул маалымат түзүмүн кантип 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();
   }
}

Экorк издөө дарагында издөө/киргизүү/жок кылуу операциялары O(log(N)) убакыт татаалдыгына ээ . Бирок бул эң жакшы сценарий. Жалпысынан алганда, операциялардын убакыт татаалдыгы O(log(N)) дан O(N) га чейин . Бул дарактын бузулуу даражасына жараша болот.

бузулган дарак деген эмне?

Бул эң сол түйүн (эң кичине сан) же эң чоң түйүн (эң чоң) абалына кошулганда элементтер түшкөн дарак. Бул, мисалы, бүт сол дарак ар бир денгээлде бош болсо, анда оң дарактар ​​гана бар болсо, анда дарак тизмеге (оңго баратат) бузулуп кетсе болот. Ооба, ушинтип бузулган дарак эффективдүү түрдө өзүнчө байланышкан тизмеге айланат, анда ар бир элемент анын жанындагыны гана билет. Бул учурда, бул структура боюнча бардык операциялар O(N) убакыттын татаалдыгына жакындайт .

Кандай учурда дарак бузулуп калышы мүмкүн?

Мисалы, сиз сорттолгон элементтердин тизмесин кошсоңуз. Эгерде тизме өсүү тартибинде иреттелсе, анда тамыр биринчи, тиешелүүлүгүнө жараша эң кичинеси болот. Андан кийинкиси туура баланын ордун алат. Ал эми кийинкиси экинчисинен чоңураак болуп, анын оң жагындагы мураскеринин ордун ээлейт жана башкалар... Тизме төмөндөө иретинде болсо, анда ошол эле нерсе болот, бирок эң сол элементтер менен. Мунун алдын алуу үчүн, бир катар элементтерди алгандан кийин, аларды жөн гана аралаштырууга болот. Ошондо сорттоо жок болот, ал эми сандар дарактын боюна аздыр-көптүр тегиз чачырап калат. Бүгүнкү күндө ушунча болду, көңүл бурганыңыз үчүн рахмат!