Data Strukturları: Java-da Binar Ağac

Salam Salam! Əsas bilik olmadan güclü proqramçı olmaq çətindir. Və burada biz təkcə doğma proqramlaşdırma dilinin sintaksisi haqqında bilikləri deyil, həm də ümumilikdə proqramlaşdırmanın əsaslarını və konsepsiyalarını nəzərdə tuturuq. Bu əsaslardan biri alqoritmlər və məlumat strukturlarıdır. Bir qayda olaraq, bəziləri bu məsələdə daha çox məlumatlıdır, bəziləri daha azdır, lakin hər kəsin bilməli olduğu bəzi əsas məlumatlar var. Məlumat strukturları üçün verilənlər bazaları arasında ikili axtarış ağaclarını başa düşməyə dəyər. Əslində, bu gün biz strukturun özünə xüsusiyyətləri ilə baxacağıq və Java-da ikili ağacı necə həyata keçirə biləcəyinizi öyrənəcəyik . Əvvəlcə ikili ağacın nə olduğunu anlayaq. İkili ağac, hər bir node (valideyn) ən çox iki uşağı (sağ və sol varis) olan məlumat strukturudur . Təcrübədə ikili ağacların iki növü çox istifadə olunur - binar axtarış ağacı və piramida (yığın). Bu gün biz ikili axtarış ağacına baxacağıq.

İkili Ağacın Faydaları

Məlumatların ikili axtarış ağacı kimi saxlanmasının üstünlüyü nədir? Təsəvvür edin ki, 100 səhifəlik istinad kitabımız var və bizə lazım olan məlumatları ehtiva edən xüsusi bir səhifə tapmalıyıq. Hansı konkret səhifəyə ehtiyacımız olduğunu məzmundan da bilirik. Adi yolla getsək, lazım olana çatana qədər hər dəfə bir səhifə çevirməli olacağıq. Yəni, özümüzü doğru yerdə tapana qədər 1-dən 100-ə qədər səhifəni keçəcəyik. Məsələn, bizə 77-ci səhifə lazımdırsa, onda 77 axtarışımız olacaq. Zamanın mürəkkəbliyindən danışsaq, O(N) olacaq . Ancaq bunu daha səmərəli etmək olar, elə deyilmi? Gəlin eyni şeyi etməyə çalışaq, lakin ikili axtarışdan istifadə edərək :

1. Kataloqu iki hissəyə bölürük, birincisi - 1-dən 50-yə qədər, ikincisi - 51-100. Səhifəmizin bu hissələrdən hansında olduğunu dəqiq bilirik: 77-ci səhifəni yenidən götürsək, kitabın ikinci hissəsindədir.
2. Sonra ikinci hissəni nəzərdən keçiririk və onu ikiyə bölürük - 51-dən 75-ə, 76-dan 100-ə qədər. Bu halda səhifəmiz yenidən ikinci yarıda, 76-100 diapazonunda olacaq.
3. Sonra bu intervalı 2-yə bölüb 76-88 və 89-100 alırıq. Səhifə birinci boşluğa uyğun gəlir, ona görə də ikincini atırıq.
4. Sonrakı intervallardır: 76-81 və 82-88, birincisini götürün.
5. 76-78 və 79-81, birincisini götürün.
6. 76 və 77-78, ikincisini götürün.
7. 77 və 78, birincini götür və səhifəmizi əldə et - 77.

77 addım əvəzinə bizə yalnız 7 lazım idi! Bu axtarışın vaxt mürəkkəbliyi O(log(N)) olacaq .

İkili axtarış ağacının qurulması qaydaları

İkili axtarış ağacı müəyyən qaydalara uyğun qurulur:

• hər node ən çox iki uşağı var;
• qovşağın dəyərindən az olan hər bir dəyər sol uşaq və ya sol uşağın uşaq olur;
• qovşağın dəyərindən böyük və ya ona bərabər olan hər bir dəyər doğru uşaq və ya doğru uşağın övladı olur.

Məsələn, bizdə 1-dən 10-a kimi bir sıra ədədlər var.Görək bu seriya üçün ikili axtarış ağacı necə olacaq: Gəlin burada ikili ağacın bütün şərtlərinin yerinə yetirilib-yetirilmədiyini düşünək:

• bütün qovşaqların ikidən çox varisləri yoxdur, birinci şərt yerinə yetirilir;
• məsələn, 7 (və ya hər hansı digər) dəyəri olan bir qovşağı nəzərdən keçirsək, sol alt ağacdakı elementlərin bütün dəyərlərinin daha az, sağda isə daha çox olacağını görərik. Bu o deməkdir ki, 2 və 3-cü şərtlər yerinə yetirilir.

Əsas əməliyyatların necə baş verdiyinə baxaq - daxil etmə, silmə, axtarış.

Element axtarın

Verilmiş dəyəri olan elementi axtararkən kök elementdən başlayırıq:

1. İstədiyiniz dəyərə bərabərdirsə, kök element arzu olunandır, yoxsa, kökün və istədiyinizin dəyərlərini müqayisə edirik.
2. Axtardığımız element daha böyükdürsə, sağ uşağı, yoxsa, sol uşağı keçirik.
3. Element tapılmadıqda, 1 və 2-ci addımları tətbiq edin, lakin element tapılana qədər uşağa (sağ və ya sol) tətbiq edin.

Məsələn, yuxarıda göstərilən ikili axtarış ağacında biz 5 dəyəri olan elementi tapmaq istəyirik:

• kök elementi ilə müqayisə edirik, görürük ki, kök element daha böyükdür, ona görə də 3 dəyəri olan sol uşaq tərəfə keçirik;
• axtardığımızla 3 qiyməti olan elementi müqayisə edirik, görürük ki, axtardığımız daha böyükdür, ona görə də bizə sözügedən elementin düzgün nəsli lazımdır, yəni dəyəri 5 olan element;
• Bu nəslini axtardığımızla müqayisə edirik və dəyərlərin bərabər olduğunu görürük - element tapılır.

Elementin daxil edilməsi

Daxil etmə alqoritmi də çox, çox sadədir:

1. Yenisini kök elementlə müqayisə edirik (əgər mövcud deyilsə, yeni element kökdür).

2. Yeni element varsa:

   • azdırsa, onda sol varisə gedirik, yoxdursa, sol varisin yerini yeni element tutur və alqoritm tamamlanır;
   • kökdən böyük və ya bərabərdirsə, onda sağ varisə keçirik. Və eynilə, əgər bu element yoxdursa, onda doğru elementin yerini yeni element tutacaq və alqoritm tamamlanacaq.

3. Əvvəlki addımın sağında və ya solunda olan sözügedən yeni element üçün daxil edilmiş element yerində olana qədər 1 və 2-ci addımları təkrarlayın.

   Nümunə olaraq, yuxarıda nəzərdən keçirilən ağaca 11 dəyəri olan bir element daxil etmək istəyəcəyik:

   • kök element 7 ilə müqayisə edirik və kök elementin daha kiçik olduğunu görürük, ona görə də sağ varisə keçirik;
   • baxılan növbəti element yeni 11-dən az olan 9 dəyərinə malikdir, buna görə də sağ varisə keçirik;
   • sağ varisin 10 dəyəri var, bu da yenə azdır, ona görə də birinci elementə keçirik və orada olmadığı üçün bu yerə 11 dəyəri olan yeni element qoyulur.
   ↓

Elementin çıxarılması

Ola bilsin ki, ikili axtarış ağacları ilə edilən bütün əməliyyatlardan silmə ən çətin olanıdır. Əvvəla, silinəcək element üçün axtarış aparılır, bundan sonra üç variasiya ola biləcək bir mərhələ gəlir:

1. Silinəcək qovşaq yarpaq qovşağıdır (uşaqları yoxdur).

   Bəlkə də ən sadə. Hamısı onu lazımsız manipulyasiya etmədən sadəcə ağacdan kəsdiyimizdən irəli gəlir. Məsələn, ağacımızdan 8 dəyəri olan düyünü çıxarırıq:

   ↓

2. Silinən qovşağın bir uşağı var.

   Bu halda biz seçilmiş qovşağı silib onun yerinə onun nəslini qoyuruq (əslində biz sadəcə seçilmiş düyünü zəncirdən kəsirik). Nümunə olaraq, 9 dəyəri olan bir nodu ağacdan çıxaraq:

   ↓

3. Silinən qovşağın iki uşağı var.

   Ən maraqlı hissə. Axı, silinən node bir anda iki uşağı varsa, onu sadəcə bu uşaqlardan biri ilə əvəz edə bilməzsiniz (xüsusilə də uşağın öz uşaqları varsa).

   Nümunə: Yuxarıdakı ağacda hansı qovşaq 3-cü qovşağın sol uşağı olmalıdır?

   Bir az düşünsəniz, bunun 4 dəyəri olan bir qovşaq olması lazım olduğu aydın olur. Bəs ağac o qədər də sadə deyilsə? Yüzlərlə dəyərə malikdirsə, varisin kim olacağını anlamaq bu qədər asan olacaqmı?

   Aydındır ki, yox. Buna görə də, öz kiçik qəbuledici axtarış alqoritmimizə ehtiyacımız var:

   1. Əvvəlcə seçilmiş nodeun sağ uşağına getməliyik, onun dəyəri node dəyərindən böyük olmalıdır.
   2. Sonra sağ uşağın sol uşağına (əgər varsa), sonra sol uşağın sol uşağına və s., sol uşaqların zəncirini izləyirik.
   3. Müvafiq olaraq, bu yolda son sol uşaq orijinal node varisi olacaq.

   Bu kiçik alqoritmi bir az ümumiləşdirək: mənbə qovşağının sağ uşaq alt ağacında bütün qovşaqlar silinəndən daha böyükdür ki, bu da binar axtarış ağacının əsas qaydalarından başa düşülə bilər. Bu alt ağacda biz ən kiçik dəyəri axtarırıq.

   Başqa sözlə, biz orijinal qovşaqdan daha böyük qovşaqlar dəstində ən kiçik qovşağı axtarırıq. Böyüklər arasında bu ən kiçik qovşaq ən uyğun davamçı olacaq.

   3 dəyəri olan qovşağı çıxardıqdan sonra ağac necə görünəcək:

   ↓

İndi təcrübədən nəzəriyyəyə keçməyin vaxtıdır. Gəlin Java-da bu məlumat strukturunun xəritəsini necə çəkə biləcəyimizə nəzər salaq. Tək düyün sinfi:

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

Çox mürəkkəb bir şey yoxdur: hər bir elementin sol və sağ uşağı ilə əlaqəsi var. İndi, bəlkə də, ən vacib sinif ağac sinfidir:

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

Yenə də çox mürəkkəb bir şey yoxdur. Daha əvvəl təsvir edilən ikili axtarış ağacı əməliyyatları, üstəlik ağacın konsolda göstərilməsi üçün bir üsul mövcuddur. Yaxşı, indi hərəkətdə olan ağaca nəzər salaq:

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

İkili axtarış ağacında axtarış/daxil etmə/silmə əməliyyatları O(log(N)) zaman mürəkkəbliyinə malikdir . Ancaq bu, ən yaxşı ssenaridir. Ümumiyyətlə, əməliyyatların vaxt mürəkkəbliyi O(log(N)) ilə O(N) arasında dəyişir . Bu ağacın degenerasiya dərəcəsindən asılıdır.

Degenerativ ağac nədir?

Bu, ən sol düyün (ən kiçik ədəd) və ya ən böyük node (ən böyük) mövqeyinə əlavə edildikdə elementlərin düşdüyü ağacdır. Bu, məsələn, bütün sol ağac hər səviyyədə boş olduqda baş verə bilər, yalnız sağ ağaclar var, bu halda ağac siyahıya çevrilir (sağa gedir). Bəli, beləcə degenerasiyaya uğramış ağac effektiv şəkildə tək-tək bağlı siyahıya çevrilir, burada hər bir element yalnız yanındakı biri haqqında bilir. Bu halda, bu struktur üzrə bütün əməliyyatlar O(N) zaman mürəkkəbliyinə yaxınlaşır .

Hansı halda ağac degenerasiya ola bilər?

Məsələn, sıralanmış elementlərin siyahısını əlavə etsəniz. Siyahı artan qaydada sıralanırsa, kök müvafiq olaraq birinci, ən kiçik olacaqdır. Ondan sonrakı doğru uşaq mövqeyini tutacaq. Və sonra gələn ikincidən böyük olacaq və onun sağ varisi mövqeyini tutacaq və s. Bunun qarşısını almaq üçün bir sıra elementləri aldıqdan sonra onları sadəcə qarışdıra bilərsiniz. Sonra çeşidləmə yox olacaq və nömrələr ağac boyunca az və ya çox bərabər şəkildə səpələnmiş olacaq. Bu gün üçün hamısı budur, diqqətinizə görə təşəkkür edirik!