Ma'lumotlar tuzilmalari: Java-da ikkilik daraxt

Salom salom! Asosiy bilimsiz kuchli dasturchi bo'lish qiyin. Va bu erda biz nafaqat ona dasturlash tili sintaksisini bilish, balki umuman dasturlash asoslari va tushunchalarini ham nazarda tutamiz. Ushbu asoslardan biri algoritmlar va ma'lumotlar tuzilmalari. Qoidaga ko'ra, ba'zilari bu masala bo'yicha ko'proq ma'lumotga ega, ba'zilari kamroq, lekin har bir kishi bilishi kerak bo'lgan ba'zi asosiy ma'lumotlar mavjud. Ma'lumotlar tuzilmalari uchun ma'lumotlar bazalari orasida, albatta, ikkilik qidiruv daraxtlarini tushunishga arziydi. Aslida, bugun biz strukturaning o'zini uning xususiyatlari bilan ko'rib chiqamiz va Java-da ikkilik daraxtni qanday amalga oshirish mumkinligini bilib olamiz . Birinchidan, keling, ikkilik daraxt nima ekanligini aniqlaylik. Ikkilik daraxt - bu har bir tugun (ota-ona) ko'pi bilan ikkita bolaga (o'ng va chap merosxo'r) ega bo'lgan ma'lumotlar strukturasidir . Amalda, odatda, ikki turdagi ikkilik daraxtlar qo'llaniladi - binar qidiruv daraxti va piramida (uyma). Bugun biz ikkilik qidiruv daraxtini ko'rib chiqamiz.

Ikkilik daraxtning afzalliklari

Ikkilik qidiruv daraxti sifatida ma'lumotlarni saqlashning afzalligi nimada? Tasavvur qiling-a, bizda 100 sahifalik ma'lumotnoma bor va biz kerakli ma'lumotlarni o'z ichiga olgan ma'lum bir sahifani topishimiz kerak. Shuningdek, biz qaysi sahifaga kerakligini tarkibdan bilamiz. Agar biz odatdagi yo'ldan borsak, biz kerakli sahifaga yetguncha bir vaqtning o'zida bir sahifani aylantirishimiz kerak bo'ladi. Ya'ni, biz o'zimizni kerakli joyda topmagunimizcha 1 dan 100 sahifagacha o'tamiz. Misol uchun, agar bizga 77-sahifa kerak bo'lsa, bizda 77 ta qidiruv bo'ladi. Vaqt murakkabligi haqida gapiradigan bo'lsak, u O (N) bo'ladi . Lekin buni samaraliroq qilish mumkin, shunday emasmi? Keling, xuddi shu narsani qilishga harakat qilaylik, lekin ikkilik qidiruvdan foydalanib :

1. Biz katalogni ikki qismga ajratamiz, birinchisi - 1 dan 50 gacha, ikkinchisi - 51-100. Biz sahifamizning qaysi qismlarida ekanligini aniq bilamiz: agar biz yana 77-sahifani olsak, u kitobning ikkinchi qismida.
2. Keyinchalik, biz ikkinchi qismni ko'rib chiqamiz va uni ikkiga ajratamiz - 51 dan 75 gacha, 76 dan 100 gacha. Bunday holda, bizning sahifamiz yana ikkinchi yarmida, 76-100 oralig'ida bo'ladi.
3. Keyinchalik, biz bu intervalni 2 ga bo'lamiz va 76-88 va 89-100 ni olamiz. Sahifa birinchi bo'shliqqa to'g'ri keladi, shuning uchun biz ikkinchisini tashlaymiz.
4. Keyingi intervallar: 76-81 va 82-88, birinchisini oling.
5. 76-78 va 79-81, birinchisini oling.
6. 76 va 77-78, ikkinchisini oling.
7. 77 va 78, birinchisini oling va bizning sahifamizga ega bo'ling - 77.

77 qadam o'rniga bizga faqat 7 qadam kerak edi! Ushbu qidiruvning vaqt murakkabligi O(log(N)) bo'ladi .

Ikkilik qidiruv daraxtini qurish qoidalari

Ikkilik qidiruv daraxti ma'lum qoidalarga muvofiq qurilgan:

• har bir tugunning ko'pi bilan ikkita bolasi bor;
• tugun qiymatidan kichik bo'lgan har bir qiymat chap bolaga yoki chap bolaga aylanadi;
• tugun qiymatidan katta yoki unga teng bo'lgan har bir qiymat to'g'ri bolaga yoki to'g'ri bolaning farzandiga aylanadi.

Masalan, bizda 1 dan 10 gacha raqamlar qatori bor. Keling, bu qator uchun binar qidiruv daraxti qanday ko'rinishini ko'rib chiqamiz: Keling, bu erda ikkilik daraxtning barcha shartlari bajarilganmi yoki yo'qligini o'ylab ko'raylik:

• barcha tugunlarda ikkitadan ortiq merosxo'r bo'lmaydi, birinchi shart bajariladi;
• agar biz, masalan, 7 (yoki boshqa har qanday boshqa) qiymatiga ega bo'lgan tugunni ko'rib chiqsak, chap pastki daraxtdagi elementlarning barcha qiymatlari kamroq, o'ngda esa ko'proq bo'lishini ko'ramiz. Bu 2 va 3 shartlar bajarilganligini anglatadi.

Keling, asosiy operatsiyalar qanday sodir bo'lishini ko'rib chiqaylik - kiritish, o'chirish, qidirish.

Elementni qidiring

Berilgan qiymatga ega elementni qidirishda biz asosiy elementdan boshlaymiz:

1. Agar u qidirilayotgan qiymatga teng bo'lsa, ildiz elementi qidirilayotgan elementdir, agar bo'lmasa, biz ildiz va qidirilayotgan qiymatlarni taqqoslaymiz.
2. Agar biz izlayotgan element kattaroq bo'lsa, biz o'ng bolaga, agar bo'lmasa, chap bolaga o'tamiz.
3. Agar element topilmasa, 1 va 2-bosqichlarni qo'llang, lekin element topilguncha bolaga (o'ng yoki chap) qo'llang.

Masalan, yuqorida ko'rsatilgan ikkilik qidiruv daraxtida biz 5 qiymatiga ega elementni topmoqchimiz:

• biz uni ildiz elementi bilan solishtiramiz, biz ildiz elementi kattaroq ekanligini ko'ramiz, shuning uchun biz chap bolaga o'tamiz, bu qiymat 3 ga teng;
• biz izlayotgan elementni va qiymati 3 bo'lgan elementni solishtiramiz, biz izlayotgan element kattaroq ekanligini ko'ramiz, shuning uchun bizga ko'rib chiqilayotgan elementning to'g'ri avlodi, ya'ni qiymati 5 bo'lgan element kerak;
• Biz bu avlodni biz izlayotgan narsa bilan taqqoslaymiz va qiymatlar teng ekanligini ko'ramiz - element topilgan.

Elementni kiritish

Qo'shish algoritmi ham juda, juda oddiy:

1. Biz yangisini ildiz bilan taqqoslaymiz (agar u mavjud bo'lmasa, yangi element ildiz hisoblanadi).

2. Agar yangi element:

   • kamroq bo'lsa, biz chap merosxo'rga o'tamiz, agar yo'q bo'lsa, yangi element chap merosxo'r o'rnini egallaydi va algoritm tugallanadi;
   • ildizdan katta yoki teng bo'lsa, biz o'ng merosxo'rga o'tamiz. Va shunga o'xshab, agar bu element mavjud bo'lmasa, unda to'g'ri element o'rnini yangi element egallaydi va algoritm tugallanadi.

3. Oldingi bosqichdan o'ng yoki chapda bo'lgan yangi element uchun kiritilgan element joyiga kelguncha 1 va 2-bosqichlarni takrorlang.

   Misol tariqasida, biz yuqorida ko'rib chiqilgan daraxtga 11 qiymatiga ega elementni kiritishni xohlaymiz:

   • biz ildiz elementi 7 bilan solishtiramiz va ildiz elementi kichikroq ekanligini ko'ramiz, shuning uchun biz o'ng merosxo'rga o'tamiz;
   • ko'rib chiqilayotgan keyingi element 9 qiymatiga ega, bu yangi 11 dan kamroq, shuning uchun biz o'ng merosxo'rga o'tamiz;
   • o'ng merosxo'r 10 qiymatiga ega, bu yana kamroq, shuning uchun biz birinchi elementga o'tamiz va u erda yo'qligi sababli, bu joyga 11 qiymatiga ega yangi element qo'yiladi.
   ↓

Elementni olib tashlash

Ehtimol, ikkilik qidiruv daraxtlari bilan barcha operatsiyalarni o'chirish eng qiyin. Avvalo, o'chirilishi kerak bo'lgan elementni qidirish mavjud, shundan so'ng uchta o'zgarish bo'lishi mumkin bo'lgan bosqich boshlanadi:

1. O'chiriladigan tugun barg tugunidir (bolalar yo'q).

   Ehtimol, eng oddiy. Bularning barchasi keraksiz manipulyatsiyalarsiz, shunchaki daraxtdan kesib tashlaganimizdan kelib chiqadi. Masalan, daraxtimizdan 8 qiymatiga ega tugunni olib tashlaymiz:

   ↓

2. O'chirilayotgan tugunning bitta farzandi bor.

   Bunday holda, biz tanlangan tugunni o'chirib tashlaymiz va uning o'rniga uning avlodini qo'yamiz (mohiyatida biz tanlangan tugunni zanjirdan kesib tashlaymiz). Misol tariqasida daraxtdan 9 qiymatiga ega tugunni olib tashlaymiz:

   ↓

3. O'chirilayotgan tugunning ikkita farzandi bor.

   Eng qiziqarli qismi. Axir, agar o'chirilayotgan tugun bir vaqtning o'zida ikkita bolaga ega bo'lsa, uni oddiygina ushbu bolalardan biri bilan almashtira olmaysiz (ayniqsa, bolaning o'z farzandlari bo'lsa).

   Misol: Yuqoridagi daraxtda qaysi tugun 3-tugunning chap bolasi bo'lishi kerak?

   Agar siz bu haqda bir oz o'ylab ko'rsangiz, bu 4 qiymatiga ega bo'lgan tugun bo'lishi kerakligi ayon bo'ladi. Ammo daraxt juda oddiy bo'lmasa-chi? Agar u yuzlab qadriyatlarga ega bo'lsa, merosxo'r kim bo'lishini aniqlash oson bo'ladimi?

   Yo'qligi aniq. Shuning uchun bizga o'zimizning kichik qabul qiluvchini qidirish algoritmimiz kerak:

   1. Avval tanlangan tugunning o'ng bolasiga o'tishimiz kerak, uning qiymati tugun qiymatidan kattaroq bo'lishi kerak.
   2. Keyin chap bolalar zanjiri bo'ylab o'ng bolaning chap bolasiga (agar mavjud bo'lsa), keyin chap bolaning chap bolasiga va hokazolarga o'tamiz.
   3. Shunga ko'ra, ushbu yo'lda oxirgi chap bola asl tugunning vorisi bo'ladi.

   Keling, ushbu kichik algoritmni biroz umumlashtiramiz: manba tugunining o'ng bolasining pastki daraxtida barcha tugunlar o'chirilayotganidan kattaroqdir, buni binar qidiruv daraxtining asosiy qoidalaridan tushunish mumkin. Ushbu kichik daraxtda biz eng kichik qiymatni qidiramiz.

   Boshqacha qilib aytganda, biz asl tugundan kattaroq tugunlar to'plamidagi eng kichik tugunni qidiramiz. Kattaroqlari orasida bu eng kichik tugun eng munosib voris bo'ladi.

   3-qiymatli tugunni olib tashlaganingizdan so'ng daraxt qanday ko'rinishga ega bo'ladi:

   ↓

Endi amaliyotdan nazariyaga o'tish vaqti keldi. Keling, ushbu ma'lumotlar strukturasini Java-da qanday qilib xaritalash mumkinligini ko'rib chiqaylik. Yagona tugun 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 +
               '}';
   }
}

Hech narsa juda murakkab emas: har bir element o'zining chap va o'ng bolasiga havolaga ega. Va endi, ehtimol, eng muhim sinf bu daraxt 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);// подводим черту
   }
}

Shunga qaramay, juda murakkab narsa yo'q. Yuqorida tavsiflangan ikkilik qidiruv daraxti operatsiyalari, shuningdek, konsolda daraxtni ko'rsatish usuli mavjud. Xo'sh, endi daraxtning harakatini ko'rib chiqaylik:

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

Ikkilik qidiruv daraxtida qidirish/qo'shish/o'chirish operatsiyalari O(log(N)) vaqt murakkabligiga ega . Lekin bu eng yaxshi stsenariy. Umuman olganda, operatsiyalarning vaqt murakkabligi O(log(N)) dan O(N) gacha . Bu daraxtning degeneratsiya darajasiga bog'liq.

Buzilgan daraxt nima?

Bu eng chap tugun (eng kichik raqam) yoki eng katta tugun (eng katta) pozitsiyasiga qo'shilganda elementlar tushgan daraxt. Bu, masalan, butun chap daraxt har bir darajada bo'sh bo'lsa, faqat o'ng daraxtlar mavjud bo'lsa, ro'yxatda (o'ngga o'tishda) daraxt nasli bo'lsa sodir bo'lishi mumkin. Ha, shunday qilib degeneratsiyalangan daraxt samarali tarzda yakka bog'langan ro'yxatga aylanadi, unda har bir element faqat keyingisi haqida biladi. Bunday holda, ushbu tuzilmadagi barcha operatsiyalar O (N) ning vaqt murakkabligiga yaqinlashadi .

Qanday holatda daraxt degeneratsiyaga aylanishi mumkin?

Masalan, tartiblangan elementlar ro'yxatini qo'shsangiz. Agar ro'yxat o'sish tartibida tartiblangan bo'lsa, unda ildiz birinchi bo'lib, mos ravishda eng kichik bo'ladi. Undan keyingisi to'g'ri bolaning o'rnini egallaydi. Va keyin kelgan ikkinchisidan kattaroq bo'ladi va uning o'ng vorisi o'rnini egallaydi va hokazo ... Agar ro'yxat kamayish tartibida bo'lsa, unda xuddi shu narsa sodir bo'ladi, lekin eng chap elementlar bilan. Bunga yo'l qo'ymaslik uchun, bir qator elementlarni olganingizdan so'ng, ularni oddiygina aralashtirishingiz mumkin. Keyin saralash yo'qoladi va raqamlar daraxt bo'ylab ko'proq yoki kamroq teng ravishda tarqaladi. Bugun hammasi shu, e'tiboringiz uchun rahmat!