Деректер құрылымдары: 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 қадам қажет болды! Бұл іздеудің уақыт күрделілігі 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) уақытының күрделілігіне жақындайды .

Қандай жағдайда ағаш азып кетуі мүмкін?

Мысалы, сұрыпталған элементтер тізімін қоссаңыз. Егер тізім өсу ретімен сұрыпталса, онда түбір бірінші, тиісінше ең кішісі болады. Одан кейінгісі дұрыс баланың орнын алады. Ал кейін келетіні екіншісінен үлкенірек болады және оның оң жақ мұрагерінің орнын алады және т.б.... Егер тізім кему ретімен болса, онда дәл солай болады, бірақ ең сол жақтағы элементтермен. Бұған жол бермеу үшін бірқатар элементтерді алғаннан кейін оларды жай ғана араластыруға болады. Содан кейін сұрыптау жойылады және сандар ағаштың бойына азды-көпті біркелкі шашыраңқы болады. Бүгінгі күн осымен бітті, назарларыңызға рахмет!