JavaRush /Blog Jawa /Random-JV /Struktur Data: Wit Binary ing Jawa

tingkat

28 February 2021
43 views
0 comments

Struktur Data: Wit Binary ing Jawa

Hi Hi! Iku angel dadi programmer kuwat tanpa kawruh dhasar. Lan ing kene tegese ora mung kawruh babagan sintaks basa pamrograman asli, nanging uga dhasar lan konsep pemrograman umume. Salah sawijining dhasar kasebut yaiku algoritma lan struktur data. Minangka aturan, sawetara luwih ngerti babagan masalah iki, sawetara kurang, nanging ana sawetara informasi dhasar sing saben wong kudu ngerti. Antarane basis data kanggo struktur data, mesthine worth mangerteni wit telusuran binar. Struktur Data: Wit Biner ing Jawa - 1

Bener, dina iki kita bakal ndeleng struktur kasebut kanthi fitur-fitur kasebut lan ngerteni carane sampeyan bisa ngetrapake wit binar ing Jawa . Pisanan, ayo ngerteni apa wit binar. Wit binar minangka struktur data sing saben simpul (wong tuwa) paling akeh duwe anak loro (waris tengen lan kiwa). Struktur Data: Wit Biner ing Jawa - 2

Ing praktik, rong jinis wit binar sing umum digunakake - wit telusuran biner lan piramida (tumpukan). Dina iki kita bakal ndeleng wit telusuran binar.

Manfaat Wit Binar

Apa kauntungan saka nyimpen data minangka wit telusuran binar? Mbayangno yen kita duwe buku referensi 100-halaman lan kita kudu nemokake kaca tartamtu sing bakal ngemot data sing dibutuhake. Kita uga ngerti saka isi kaca tartamtu sing kita butuhake. Yen kita ngetutake dalan sing biasa, kita kudu ngowahi siji-sijine kaca nganti tekan sing dibutuhake. Tegese, kita bakal mbukak saka 1 nganti 100 kaca nganti kita nemokake dhewe ing panggonan sing bener. Contone, yen kita butuh kaca 77, kita bakal duwe 77 telusuran. Yen kita ngomong babagan kerumitan wektu, mula bakal dadi O(N) . Nanging iki bisa ditindakake kanthi luwih efisien, ta? Ayo nyoba nindakake perkara sing padha, nanging nggunakake telusuran binar :

Kita dibagi direktori dadi rong bagéan, pisanan - saka 1 kanggo 50, kaloro - 51-100. Kita ngerti persis ing bagean kasebut kaca kita: yen kita njupuk kaca 77 maneh, iku ana ing bagean liya saka buku kasebut.
Sabanjure, kita nimbang bagean kapindho lan dibagi dadi loro - saka 51 nganti 75, saka 76 nganti 100. Ing kasus iki, kaca kita bakal maneh ing separo kapindho, ing kisaran 76-100.
Sabanjure, kita dibagi interval iki kanthi 2 lan entuk 76-88 lan 89-100. Kaca kasebut cocog karo celah pisanan, mula kita mbuwang sing kapindho.
Sabanjure yaiku interval: 76-81 lan 82-88, njupuk sing pisanan.
76-78 lan 79-81, njupuk sing pisanan.
76 lan 77-78, njupuk nomer loro.
77 lan 78, njupuk sing pisanan lan entuk kaca kita - 77.

Tinimbang 77 langkah, kita mung butuh 7! Kompleksitas wektu panelusuran iki bakal dadi O(log(N)) .

Aturan kanggo mbangun wit telusuran binar

Wit telusuran binar dibangun miturut aturan tartamtu:

saben simpul duwe paling loro anak;
saben nilai kurang saka nilai simpul dadi anak kiwa utawa anak saka anak kiwa;
saben nilai luwih saka utawa padha karo nilai simpul dadi anak tengen utawa anak saka anak tengen.

Contone, kita duwe seri nomer saka 1 nganti 10. Ayo ndeleng kaya apa wit telusuran biner kanggo seri iki: Struktur Data: Wit Biner ing Jawa - 3

Ayo dipikirake apa kabeh kahanan wit binar wis ditemokake ing kene:

kabeh simpul ora duwe luwih saka rong ahli waris, syarat pisanan ketemu;
Yen kita nimbang, contone, simpul kanthi nilai 7 (utawa liyane), kita bakal weruh yen kabeh nilai unsur ing subtree kiwa bakal kurang, lan ing sisih tengen - luwih. Iki tegese syarat 2 lan 3 wis ditemtokake.

Ayo goleki carane operasi dhasar kedadeyan - selipan, pambusakan, telusuran.

Telusuri unsur

Nalika nggoleki unsur kanthi nilai tartamtu, kita miwiti ing unsur root:

Yen padha karo nilai sing digoleki, unsur oyot yaiku sing digoleki; yen ora, kita mbandhingake nilai oyod lan sing digoleki.
Yen unsur sing kita goleki luwih gedhe, kita pindhah menyang anak tengen, yen ora, kita pindhah menyang anak kiwa.
Yen unsur ora ditemokake, gunakake langkah 1 lan 2, nanging kanggo bocah (tengen utawa kiwa) nganti unsur kasebut ditemokake.

Contone, ing wit telusuran binar sing ditampilake ing ndhuwur, kita pengin nemokake unsur kanthi nilai 5:

kita mbandhingaké karo unsur ROOT, kita waca sing unsur ROOT luwih gedhe, supaya kita pindhah menyang anak kiwa, kang nduweni nilai 3;
kita mbandhingake sing digoleki lan unsur sing duwe nilai 3, kita weruh yen sing digoleki luwih gedhe, mula kita butuh turunan sing tepat saka unsur kasebut, yaiku unsur sing duwe nilai 5;
Kita mbandhingake keturunan iki karo sing kita goleki lan ndeleng manawa nilai kasebut padha - unsur ditemokake.

Nglebokake unsur

Algoritma selipan uga prasaja banget:

Kita mbandhingake sing anyar karo oyod (yen ora ana, unsur anyar yaiku oyod).
Yen unsur anyar:
- kurang, banjur pindhah menyang pewaris kiwa, yen ora ana, unsur anyar njupuk panggonan pewaris kiwa, lan algoritma wis rampung;
- luwih gedhe tinimbang utawa padha karo oyod, banjur pindhah menyang ahli waris sing bener. Lan uga, yen unsur iki ora ana, banjur unsur anyar bakal njupuk Panggonan saka unsur tengen lan algoritma wis rampung.
Kanggo unsur anyar sing dimaksud, sing ana ing sisih tengen utawa kiwa saka langkah sadurunge, baleni langkah 1 lan 2 nganti unsur sing dilebokake.

Minangka conto, kita pengin nglebokake wit sing dianggep ing ndhuwur, unsur kanthi nilai 11:
- kita mbandhingaké karo unsur ROOT 7 lan ndeleng sing unsur ROOT cilik, supaya kita pindhah menyang ahli waris tengen;
- unsur sabanjuré ing wawasan wis Nilai 9, kang kurang saka anyar 11, supaya kita pindhah menyang ahli waris tengen;
- ahli waris tengen wis Nilai 10, kang maneh kurang, supaya kita menyang unsur pisanan, lan wiwit iku ora ana, unsur anyar karo nilai 11 diselehake ing panggonan iki.
↓

Mbusak unsur

Mbok menawa, kabeh operasi karo wit telusuran binar, pambusakan paling angel. Kaping pisanan, ana telusuran kanggo unsur sing bakal dibusak, sawise nemokake tahapan sing bakal ditindakake, sing bisa duwe telung variasi:

Simpul sing arep dibusak yaiku simpul godhong (ora duwe anak).

Mbok sing paling prasaja. Iku kabeh nerangake kasunyatan sing kita mung Cut mati saka wit, tanpa manipulasi rasah. Contone, saka wit kita mbusak simpul kanthi nilai 8:
↓
Node sing dibusak duwe anak siji.

Ing kasus iki, kita mbusak simpul sing dipilih lan sijine turunane ing panggonane (intine, kita mung ngethok simpul sing dipilih saka rantai). Minangka conto, ayo mbusak simpul kanthi nilai 9 saka wit:
↓
Node sing dibusak duwe anak loro.

Sisih paling menarik. Sawise kabeh, yen simpul sing dibusak duwe anak loro bebarengan, sampeyan ora bisa ngganti karo salah siji saka bocah kasebut (utamane yen bocah duwe anak dhewe).

Tuladha: Ing wit ing ndhuwur, simpul endi sing kudu dadi anak kiwa simpul 3?

Yen sampeyan mikir sethithik, dadi jelas yen iki kudu dadi simpul kanthi nilai 4. Nanging apa yen wit kasebut ora prasaja? Yen ngemu atusan nilai, bakal dadi gampang kanggo nemtokake sapa sing bakal dadi penerus?

Sing jelas ora. Mulane, kita butuh algoritma panelusuran panrima cilik dhewe:
1. Pisanan kita kudu pindhah menyang anak tengen simpul sing dipilih, sing nilai kudu luwih gedhe tinimbang nilai simpul.
2. Banjur kita menyang anak kiwa anak tengen (yen ana), banjur menyang anak kiwa anak kiwa, lan liya-liyane, ngetutake rantai anak kiwa.
3. Patut, anak kiwa pungkasan ing dalan iki bakal dadi penerus simpul asli.
Ayo umumake algoritma cilik iki: ing subtree anak tengen saka simpul sumber, kabeh simpul luwih gedhe tinimbang sing dibusak, sing bisa dimangerteni saka aturan dhasar saka wit telusuran binar. Ing subtree iki kita nggoleki nilai sing paling cilik.

Ing tembung liya, kita nggoleki simpul paling cilik ing sakumpulan simpul sing luwih gedhe tinimbang simpul asli. Simpul paling cilik iki ing antarane sing luwih gedhe bakal dadi penerus sing paling cocok.

Kaya apa wit kasebut sawise ngilangi simpul kanthi nilai 3:
↓

Saiki wektune pindhah saka praktik menyang teori. Ayo dideleng kepiye carane nggawe peta struktur data iki ing basa Jawa. Kelas node tunggal:

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

Ora ana sing rumit banget: saben unsur nduweni pranala menyang anak kiwa lan tengen. Lan saiki, mbok menawa, kelas sing paling penting yaiku kelas wit:

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

Maneh, ora ana sing rumit banget. Operasi wit telusuran binar sing diterangake sadurunge saiki, ditambah karo metode kanggo nampilake wit kasebut ing konsol. Nah, saiki ayo deleng wit ing tumindak:

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

Operasi telusuran / masang / mbusak ing wit telusuran binar duwe kerumitan wektu O(log(N)) . Nanging iki skenario paling apik. Umumé, kerumitan wektu operasi kisaran saka O(log(N)) kanggo O(N) . Iku gumantung ing tingkat degenerasi saka wit.

Apa wit degenerasi?

Iki minangka wit sing unsur-unsur kasebut tiba nalika ditambahake ing posisi simpul paling kiwa (node paling cilik) utawa simpul paling gedhe (paling gedhe). Iki bisa kedadeyan yen, umpamane, kabeh wit kiwa kosong ing saben level, mung ana wit tengen, mula wit kasebut degenerasi dadi dhaptar (arep menyang sisih tengen). Ya, iki carane wit degenerasi kanthi efektif dadi dhaptar sing disambung, sing saben unsur mung ngerti babagan sing ana ing jejere. Ing kasus iki, kabeh operasi ing struktur iki nyedhaki kerumitan wektu O(N) .

Ing kasus apa wit bisa dadi degenerasi?

Contone, yen sampeyan nambahake dhaptar unsur sing diurutake. Yen dhaptar diurutake kanthi urutan munggah, mula oyod bakal dadi sing pertama, sing paling cilik. Sing sabanjure sawise dheweke bakal njupuk posisi bocah sing bener. Lan sing bakal teka bakal luwih gedhe tinimbang sing kapindho lan bakal njupuk posisi penerus sing tengen, lan sateruse ... Yen dhaptar ing urutan mudhun, mula kedadeyan sing padha, nanging kanthi unsur paling kiwa. Kanggo ngindhari iki, sawise nampa sawetara unsur, sampeyan mung bisa nyampur. Banjur ngurutake bakal ilang, lan nomer bakal luwih utawa kurang roto-roto kasebar ing saindhenging wit. Struktur Data: Wit Biner ing Jawa - 13

Semono uga kanggo dina iki, matur nuwun kanggo perhatian sampeyan!

Komentar

TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION