{"id":30530,"date":"2019-10-31T21:36:01","date_gmt":"2019-10-31T18:36:01","guid":{"rendered":"https:\/\/prohoster.info\/blog\/binary-tree-ili-kak-prigotovit-binarnoe-derevo-poiska\/"},"modified":"2019-10-31T21:36:01","modified_gmt":"2019-10-31T18:36:01","slug":"binary-tree-ili-kak-prigotovit-binarnoe-derevo-poiska","status":"publish","type":"post","link":"https:\/\/prohoster.info\/sk\/blog\/administrirovanie\/binary-tree-ili-kak-prigotovit-binarnoe-derevo-poiska","title":{"rendered":"Binary Tree alebo ako pripravi\u0165 bin\u00e1rny vyh\u013ead\u00e1vac\u00ed strom","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Prelude<\/h2>\n

\nTento \u010dl\u00e1nok sa zaober\u00e1 bin\u00e1rnymi stromami vyh\u013ead\u00e1vania. Ned\u00e1vno som robil \u010dl\u00e1nok o kompresii d\u00e1t met\u00f3dou Huffmana.<\/a><\/noindex> Tam som sa ve\u013emi nezameriaval na bin\u00e1rne stromy, preto\u017ee met\u00f3dy vyh\u013ead\u00e1vania, vkladania a odstra\u0148ovania neboli aktu\u00e1lne. Teraz som sa rozhodol nap\u00edsa\u0165 \u010dl\u00e1nok presne o stromoch. Asi za\u010dneme. <\/p>\n

Strom je d\u00e1tov\u00e1 \u0161trukt\u00fara pozost\u00e1vaj\u00faca z uzlov, spojen\u00fdch hranami. M\u00f4\u017eeme poveda\u0165, \u017ee strom je osobitn\u00fd pr\u00edpad grafu. Tu je pr\u00edklad stromu: <\/p>\n

\"Binary
\n
\nToto nie je bin\u00e1rne vyh\u013ead\u00e1vacie strom! V\u0161etko pod kat!
\n<\/a><\/noindex><\/p>\n

Terminol\u00f3gia<\/h2>\n

<\/p>\n

Korene<\/h4>\n

\nKore\u0148 stromu<\/i> je najvy\u0161\u0161\u00ed uzol. V pr\u00edklade je to uzol A. V strome od kore\u0148a k ak\u00e9muko\u013evek in\u00e9mu uzlu m\u00f4\u017ee vies\u0165 len jedna cesta! V skuto\u010dnosti sa ak\u00fdko\u013evek uzol d\u00e1 pova\u017eova\u0165 za kore\u0148 pr\u00edslu\u0161n\u00e9ho podstromu.<\/p>\n

Rodi\u010dia\/potomkovia<\/h4>\n

\nV\u0161etky uzly okrem kore\u0148ov\u00e9ho maj\u00fa presne jednu hranu, ved\u00facu nahor k in\u00e9mu uzlu. Uzol, nach\u00e1dzaj\u00faci sa nad aktu\u00e1lnym, sa naz\u00fdva rodi\u010dom<\/i> tohto uzla. Uzol, nach\u00e1dzaj\u00faci sa pod aktu\u00e1lnym a spojen\u00fd s n\u00edm, sa naz\u00fdva potomkom<\/i> tohto uzla. Pozrime sa na pr\u00edklad. Vezmeme uzol B, jeho rodi\u010dom bude uzol A a potomkami bud\u00fa uzly D, E a F.<\/p>\n

List<\/h4>\n

\nUzol, ktor\u00fd nem\u00e1 potomkov, sa naz\u00fdva listom stromu. V pr\u00edklade s\u00fa listami uzly D, E, F, G, I, J, K.<\/p>\n

Toto je z\u00e1kladn\u00e1 terminol\u00f3gia. \u010eal\u0161ie pojmy bud\u00fa podrobne vysvetlen\u00e9 nesk\u00f4r. Tak\u017ee bin\u00e1rny strom je strom, v ktorom m\u00e1 ka\u017ed\u00fd uzol najviac dvoch potomkov. Ako ste sa asi u\u017e domysleli, strom z pr\u00edkladu nebude bin\u00e1rny, preto\u017ee uzly B a H maj\u00fa viac ako dvoch potomkov. Tu je pr\u00edklad bin\u00e1rneho stromu:<\/p>\n

\"Binary
\n
\nV uzloch stromu m\u00f4\u017ee by\u0165 ak\u00e1ko\u013evek inform\u00e1cia. Bin\u00e1rny vyh\u013ead\u00e1vac\u00ed strom je bin\u00e1rny strom, ktor\u00e9ho charakteristick\u00e9 vlastnosti s\u00fa nasleduj\u00face:<\/p>\n

    \n
  1. Oba podstromy \u2014 \u013eav\u00fd a prav\u00fd \u2014 s\u00fa bin\u00e1rnymi vyh\u013ead\u00e1vac\u00edmi stromami.<\/li>\n
  2. V\u0161etky uzly \u013eav\u00e9ho podstromu ak\u00e9hoko\u013evek uzla X maj\u00fa hodnoty k\u013e\u00fa\u010dov\u00fdch \u00fadajov men\u0161ie ne\u017e hodnota k\u013e\u00fa\u010da samotn\u00e9ho uzla X.<\/li>\n
  3. V\u0161etky uzly prav\u00e9ho podstromu ak\u00e9hoko\u013evek uzla X maj\u00fa hodnoty k\u013e\u00fa\u010dov\u00fdch \u00fadajov v\u00e4\u010d\u0161ie alebo rovn\u00e9 ne\u017e hodnota k\u013e\u00fa\u010da samotn\u00e9ho uzla X. <\/li>\n<\/ol>\n

    Parameter<\/i> nejak\u00e1 charakteristika uzla (napr\u00edklad \u010d\u00edslo). K\u013e\u00fa\u010d je potrebn\u00fd na to, aby bolo mo\u017en\u00e9 n\u00e1js\u0165 prvok stromu, ktor\u00fd zodpoved\u00e1 tomuto k\u013e\u00fa\u010du. Pr\u00edklad bin\u00e1rneho vyh\u013ead\u00e1vacieho stromu:<\/p>\n

    \"Binary
    \n<\/p>\n

    Zobrazenie stromu<\/h2>\n

    \nAko budete pokra\u010dova\u0165, prinesiem niektor\u00e9 (mo\u017eno ne\u00fapln\u00e9) \u00fatr\u017eky k\u00f3du, aby som zlep\u0161il va\u0161e porozumenie. Kompletn\u00fd k\u00f3d bude na konci \u010dl\u00e1nku. <\/p>\n

    Strom sa sklad\u00e1 z uzlov. \u0160trukt\u00fara uzla:<\/p>\n

    public class Node<T> {\n    private T data;\n    private int key;\n    private Node<T> leftChild;\n    private Node<T> rightChild;\n\n    public Node(T data, int key) {\n        this.data = data;\n        this.key = key;\n    }\n    public Node<T> getLeftChild() {\n        return leftChild;\n    }\n\n    public Node<T> getRightChild() {\n        return rightChild;\n    }\n\/\/...ostatn\u00e9 met\u00f3dy uzla\n}\n<\/code><\/pre>\n
    \nKa\u017ed\u00fd uzol m\u00e1 dvoch potomkov (je mo\u017en\u00e9, \u017ee potomkovia leftChild a\/alebo rightChild bud\u00fa ma\u0165 hodnotu null). Ur\u010dite ste pochopili, \u017ee v tomto pr\u00edpade \u010d\u00edslo data \u2014 \u00fadaje ulo\u017een\u00e9 v uzle; key \u2014 k\u013e\u00fa\u010d uzla.<\/p>\n
    S uzlom m\u00e1me jasno, teraz sa porozpr\u00e1vajme o aktu\u00e1lnych probl\u00e9moch stromov. Tu a \u010falej pod pojmom \"strom\" budem rozumie\u0165 pojem bin\u00e1rneho vyh\u013ead\u00e1vacieho stromu. \u0160trukt\u00fara bin\u00e1rneho stromu:<\/p>\n
    public class BinaryTree<T> {\n     private Node<T> root;\n\n    \/\/met\u00f3dy stromu\n}\n<\/code><\/pre>\n
    Ako pole triedy n\u00e1m bude potrebn\u00fd len kore\u0148 stromu, preto\u017ee od kore\u0148a pomocou met\u00f3d getLeftChild() a getRightChild() sa d\u00e1 dosta\u0165 ku ak\u00e9muko\u013evek uzlu stromu.<\/p>\n
    Algoritmy v strome<\/h2>\n
    <\/p>\n
    H\u013eadanie<\/h3>\n
    \nPredpokladajme, \u017ee m\u00e1te postaven\u00fd strom. Ako n\u00e1js\u0165 prvok s k\u013e\u00fa\u010dom key? Je potrebn\u00e9 postupne sa pohybova\u0165 od kore\u0148a smerom dole po strome a porovn\u00e1va\u0165 hodnotu key s k\u013e\u00fa\u010dom aktu\u00e1lneho uzla: ak je key men\u0161\u00ed ako k\u013e\u00fa\u010d aktu\u00e1lneho uzla, prejdite k \u013eav\u00e9mu potomkovi uzla, ak je v\u00e4\u010d\u0161\u00ed \u2014 k prav\u00e9mu, ak s\u00fa k\u013e\u00fa\u010de rovn\u00e9 \u2014 po\u017eadovan\u00fd uzol je n\u00e1jden\u00fd! Prisl\u00fachaj\u00faci k\u00f3d:<\/p>\n
    public Node<T> find(int key) {\n    Node<T> current = root;\n    while (current.getKey() != key) {\n        if (key < current.getKey())\n            current = current.getLeftChild();\n        else\n            current = current.getRightChild();\n        if (current == null)\n            return null;\n    }\n    return current;\n}\n<\/code><\/pre>\n
    \nAk current sa st\u00e1va rovn\u00fd null, znamen\u00e1 to, \u017ee preverenie dosiahlo koniec stromu (na konceptu\u00e1lnej \u00farovni sa nach\u00e1dzate na neexistuj\u00facom mieste stromu \u2014 potomkovi listu).<\/p>\n
    Zv\u00e1\u017eme efektivitu vyh\u013ead\u00e1vacieho algoritmu na vyv\u00e1\u017eenom strome (strome, v ktorom s\u00fa uzly rozlo\u017een\u00e9 viac-menej rovnomerne). Potom efektivita vyh\u013ead\u00e1vania bude O(log(n)), pri\u010dom logaritmus je so z\u00e1kladom 2. Pozrite: ak je v vyv\u00e1\u017eenom strome n prvkov, znamen\u00e1 to, \u017ee bude log(n) so z\u00e1kladom 2 \u00farovn\u00ed stromu. A pri vyh\u013ead\u00e1van\u00ed, za jeden krok cyklu, zostupujete na jednu \u00farove\u0148.<\/p>\n
    Vlo\u017eenie<\/h3>\n
    \nAk ste pochopili podstatu vyh\u013ead\u00e1vania, potom pre v\u00e1s nebude probl\u00e9m pochopi\u0165 vkladanie. Sta\u010d\u00ed len zost\u00fapi\u0165 na list stromu (pod\u013ea pravidiel zostupu pop\u00edsan\u00fdch vo vyh\u013ead\u00e1van\u00ed) a sta\u0165 sa jeho potomkom - \u013eav\u00fdm alebo prav\u00fdm, v z\u00e1vislosti od k\u013e\u00fa\u010da. Realiz\u00e1cia:<\/p>\n
       public void insert(T insertData, int key) {\n        Node current = root;\n        Node parent;\n        Node newNode = new Node(insertData, key);\n        if (root == null)\n            root = newNode;\n        else {\n            while (true) {\n                parent = current;\n                if (key < current.getKey()) {\n                    current = current.getLeftChild();\n                    if (current == null) {\n                         parent.setLeftChild(newNode);\n                         return;\n                    }\n                }\n                else {\n                    current = current.getRightChild();\n                    if (current == null) {\n                        parent.setRightChild(newNode);\n                        return;\n                    }\n                }\n            }\n        }\n    }\n<\/code><\/pre>\n
    \nV tomto pr\u00edpade je potrebn\u00e9 okrem aktu\u00e1lneho uzla uchov\u00e1va\u0165 inform\u00e1cie o rodi\u010dovi aktu\u00e1lneho uzla. Ke\u010f current dosiahne hodnotu null, v premennej parent bude le\u017ea\u0165 potrebn\u00fd list. 
    \n\u00da\u010dinnos\u0165 vkladania bude zjavne rovnak\u00e1 ako pri vyh\u013ead\u00e1van\u00ed \u2014 O(log(n)).<\/p>\n
    Odstr\u00e1nenie<\/h3>\n
    \nVymazanie je najzlo\u017eitej\u0161ia oper\u00e1cia, ktor\u00fa bude potrebn\u00e9 vykona\u0165 so stromom. Je jasn\u00e9, \u017ee najprv bude potrebn\u00e9 n\u00e1js\u0165 prvok, ktor\u00fd chceme odstr\u00e1ni\u0165. Ale \u010do potom? Ak jednoducho pridel\u00edme jeho odkazu hodnotu null, strat\u00edme inform\u00e1cie o podstrome, ktor\u00e9ho kore\u0148om je tento uzol. Met\u00f3dy odstra\u0148ovania stromu rozde\u013eujeme na tri pr\u00edpady.<\/p>\n
    Prv\u00fd pr\u00edpad. Odstra\u0148ovan\u00fd uzol nem\u00e1 potomkov.<\/h4>\n
    \nAk odstra\u0148ovan\u00fd uzol nem\u00e1 potomkov, znamen\u00e1 to, \u017ee je to list. Preto je mo\u017en\u00e9 priradi\u0165 poliam leftChild alebo rightChild jeho rodi\u010da hodnotu null. <\/p>\n
    Druh\u00fd pr\u00edpad. Odstra\u0148ovan\u00fd uzol m\u00e1 jedn\u00e9ho potomka.<\/h4>\n
    \nTento pr\u00edpad nie je tie\u017e ve\u013emi zlo\u017eit\u00fd. Vr\u00e1\u0165me sa k n\u00e1\u0161mu pr\u00edkladu. Predpokladajme, \u017ee treba odstr\u00e1ni\u0165 prvok s k\u013e\u00fa\u010dom 14. S\u00fahlas\u00edte, \u017ee ke\u010f\u017ee je to prav\u00fd potomok uzla s k\u013e\u00fa\u010dom 10, ak\u00fdko\u013evek jeho potomok (v tomto pr\u00edpade prav\u00fd) bude ma\u0165 k\u013e\u00fa\u010d v\u00e4\u010d\u0161\u00ed ako 10, preto ho m\u00f4\u017eeme \u013eahko \u201evyradi\u0165\u201c zo stromu a rodi\u010da pripoji\u0165 priamo k potomkovi odstra\u0148ovan\u00e9ho uzla, t.j. uzol s k\u013e\u00fa\u010dom 10 pripoji\u0165 k uzlu 13. Podobn\u00e1 by bola situ\u00e1cia, keby sme mali odstr\u00e1ni\u0165 uzol, ktor\u00fd je \u013eav\u00fdm potomkom svojho rodi\u010da. Zamyslite sa nad t\u00fdm sami \u2014 presn\u00e1 anal\u00f3gia. <\/p>\n
    Tret\u00ed pr\u00edpad. Uzol m\u00e1 dvoch potomkov.<\/h4>\n
    \nNajzlo\u017eitej\u0161\u00ed pr\u00edpad. Rozoberieme na novom pr\u00edklade.<\/p>\n
    \"Binary
    \n<\/p>\n
    H\u013eadanie n\u00e1stupcu.<\/h4>\n
    \n Povedzme, \u017ee chceme odstr\u00e1ni\u0165 uzol s k\u013e\u00fa\u010dom 25. Kto zaberie jeho miesto? Niekto z jeho n\u00e1sledn\u00edkov (potomkov alebo potomkov potomkov) by sa mal sta\u0165 n\u00e1stupcom<\/i>(t\u00fdm, kto zaujme miesto odstr\u00e1nen\u00e9ho uzla). <\/p>\n
    Ako zisti\u0165, kto by mal by\u0165 n\u00e1stupcom? Intuit\u00edvne je jasn\u00e9, \u017ee ide o uzol v strome, ktor\u00e9ho k\u013e\u00fa\u010d je najbli\u017e\u0161\u00ed vy\u0161\u0161\u00ed k odstr\u00e1nen\u00e9mu uzlu. Algoritmus spo\u010d\u00edva v nasleduj\u00facom. Mus\u00edme prejs\u0165 k jeho prav\u00e9mu potomkovi (v\u017edy k prav\u00e9mu, preto\u017ee u\u017e bolo povedan\u00e9, \u017ee k\u013e\u00fa\u010d n\u00e1stupcu je v\u00e4\u010d\u0161\u00ed ako k\u013e\u00fa\u010d odstr\u00e1nen\u00e9ho uzla) a potom prejs\u0165 re\u0165azcom \u013eav\u00fdch potomkov tohto prav\u00e9ho potomka. V pr\u00edklade mus\u00edme prejs\u0165 k uzlu s k\u013e\u00fa\u010dom 35 a potom postupova\u0165 nadol po re\u0165azci jeho \u013eav\u00fdch potomkov \u2014 v tomto pr\u00edpade sa re\u0165azec sklad\u00e1 len z uzla s k\u013e\u00fa\u010dom 30. Stricto sensu, h\u013ead\u00e1me najmenej uzol v mno\u017eine uzlov, ktor\u00e9 s\u00fa v\u00e4\u010d\u0161ie ako h\u013eadan\u00fd uzol.<\/p>\n
    \"Binary
    \n
    \nK\u00f3d met\u00f3dy vyh\u013ead\u00e1vania n\u00e1stupcu:<\/p>\n
        public Node<T> getSuccessor(Node<T> deleteNode) {\n        Node<T> parentSuccessor = deleteNode; \/\/ rodi\u010d n\u00e1stupcu\n        Node<T> successor = deleteNode; \/\/ n\u00e1stupca\n        Node<T> current = successor.getRightChild(); \/\/ prost\u00fd \"be\u017eiaci\" uzol\n        while (current != null) {\n            parentSuccessor = successor;\n            successor = current;\n            current = current.getLeftChild();\n        }\n        \/\/ na v\u00fdstupe z cyklu m\u00e1me n\u00e1stupcu a rodi\u010da n\u00e1stupcu\n        if (successor != deleteNode.getRightChild()) { \/\/ ak sa n\u00e1stupca nezhoduje s prav\u00fdm potomkom odstra\u0148ovan\u00e9ho uzla\n            parentSuccessor.setLeftChild(successor.getRightChild()); \/\/ potom jeho rodi\u010d vezme potomka n\u00e1stupcu, aby ho nestratil\n            successor.setRightChild(deleteNode.getRightChild()); \/\/ spoj\u00edme n\u00e1stupcu s prav\u00fdm potomkom odstra\u0148ovan\u00e9ho uzla\n        }\n        return successor;\n    }\n<\/code><\/pre>\n
    \n\u00dapln\u00fd k\u00f3d met\u00f3dy delete:<\/p>\n
    public boolean delete(int deleteKey) {\n        Node current = root;\n        Node parent = current;\n        boolean isLeftChild = false; \/\/ V z\u00e1vislosti od toho, \u010di je mazan\u00fd uzol \u013eav\u00fdm alebo prav\u00fdm potomkom svojho rodi\u010da, boolean premenna isLeftChild bude ma\u0165 hodnotu true alebo false.\n        while (current.getKey() != deleteKey) {\n            parent = current;\n            if (deleteKey < current.getKey()) {\n                current = current.getLeftChild();\n                isLeftChild = true;\n            } else {\n                isLeftChild = false;\n                current = current.getRightChild();\n            }\n            if (current == null)\n                return false;\n        }\n\n        if (current.getLeftChild() == null && current.getRightChild() == null) { \/\/ prv\u00fd pr\u00edpad\n            if (current == root)\n                current = null;\n            else if (isLeftChild)\n                parent.setLeftChild(null);\n            else\n                parent.setRightChild(null);\n        }\n        else if (current.getRightChild() == null) { \/\/ druh\u00fd pr\u00edpad\n            if (current == root)\n                root = current.getLeftChild();\n            else if (isLeftChild)\n                parent.setLeftChild(current.getLeftChild());\n            else\n                current.setRightChild(current.getLeftChild());\n        } else if (current.getLeftChild() == null) {\n            if (current == root)\n                root = current.getRightChild();\n            else if (isLeftChild)\n                parent.setLeftChild(current.getRightChild());\n            else\n                parent.setRightChild(current.getRightChild());\n        } \n        else { \/\/ tret\u00ed pr\u00edpad\n            Node successor = getSuccessor(current);\n            if (current == root)\n                root = successor;\n            else if (isLeftChild)\n                parent.setLeftChild(successor);\n            else\n                parent.setRightChild(successor);\n        }\n        return true;\n    }\n<\/code><\/pre>\n
    \nZlo\u017eitost m\u00f4\u017ee by\u0165 aproximovan\u00e1 na O(log(n)).<\/p>\n
    H\u013eadanie maxima\/minima v strome<\/h3>\n
    \nJe zrejm\u00e9, ako n\u00e1js\u0165 minim\u00e1lnu\/maxim\u00e1lnu hodnotu v strome \u2014 treba postupne prech\u00e1dza\u0165 po re\u0165azci \u013eav\u00fdch\/prav\u00fdch prvkov stromu; ke\u010f sa dostanete k listu, ten bude minim\u00e1lnym\/maxim\u00e1lnym prvkom.<\/p>\n
        public Node getMinimum(Node startPoint) {\n        Node current = startPoint;\n        Node parent = current;\n        while (current != null) {\n            parent = current;\n            current = current.getLeftChild();\n        }\n        return parent;\n    }\n\n    public Node getMaximum(Node startPoint) {\n        Node current = startPoint;\n        Node parent = current;\n        while (current != null) {\n            parent = current;\n            current = current.getRightChild();\n        }\n        return parent;\n    }\n<\/code><\/pre>\n
    \nZlo\u017eitost \u2014 O(log(n))<\/p>\n
    Symetrick\u00fd prechod<\/h3>\n
    \nPrechod \u2014 n\u00e1v\u0161teva ka\u017ed\u00e9ho uzla stromu s cie\u013eom vykona\u0165 s n\u00edm nejak\u00fa akciu.<\/p>\n
    Algoritmus rekurz\u00edvneho symetrick\u00e9ho prechodu:<\/p>\n
      \n
    1. Urobi\u0165 akciu s \u013eav\u00fdm potomkom<\/li>\n
    2. Urobi\u0165 akciu so sebou<\/li>\n
    3. Urobi\u0165 akciu s prav\u00fdm potomkom<\/li>\n<\/ol>\n
      \nK\u00f3d:<\/p>\n
          public void inOrder(Node current) {\n        if (current != null) {\n            inOrder(current.getLeftChild());\n            System.out.println(current.getData() + \" \");\/\/Tu m\u00f4\u017ee by\u0165 \u010doko\u013evek\n            inOrder(current.getRightChild());\n        }\n    }\n<\/code><\/pre>\n
      <\/p>\n
      Z\u00e1ver<\/h2>\n
      \nKone\u010dne! Ak som nie\u010do nedostato\u010dne vysvetlil alebo m\u00e1te nejak\u00e9 pripomienky, \u010dak\u00e1m na koment\u00e1roch. Ako som s\u013e\u00fabil, prin\u00e1\u0161am kompletn\u00fd k\u00f3d.<\/p>\n
      Node.java:<\/p>\n
      public class Node {\n    private T data;\n    private int key;\n    private Node leftChild;\n    private Node rightChild;\n\n    public Node(T data, int key) {\n        this.data = data;\n        this.key = key;\n    }\n\n    public void setLeftChild(Node newNode) {\n        leftChild = newNode;\n    }\n\n    public void setRightChild(Node newNode) {\n        rightChild = newNode;\n    }\n\n    public Node getLeftChild() {\n        return leftChild;\n    }\n\n    public Node getRightChild() {\n        return rightChild;\n    }\n\n    public T getData() {\n        return data;\n    }\n\n    public int getKey() {\n        return key;\n    }\n}\n\n<\/code><\/pre>\n
      \nBinaryTree.java:<\/p>\n
      public class BinaryTree<T> {\n    private Node<T> root;\n\n    public Node<T> find(int key) {\n        Node<T> current = root;\n        while (current.getKey() != key) {\n            if (key < current.getKey())\n                current = current.getLeftChild();\n            else\n                current = current.getRightChild();\n            if (current == null)\n                return null;\n        }\n        return current;\n    }\n\n    public void insert(T insertData, int key) {\n        Node<T> current = root;\n        Node<T> parent;\n        Node<T> newNode = new Node<>(insertData, key);\n        if (root == null)\n            root = newNode;\n        else {\n            while (true) {\n                parent = current;\n                if (key < current.getKey()) {\n                    current = current.getLeftChild();\n                    if (current == null) {\n                         parent.setLeftChild(newNode);\n                         return;\n                    }\n                }\n                else {\n                    current = current.getRightChild();\n                    if (current == null) {\n                        parent.setRightChild(newNode);\n                        return;\n                    }\n                }\n            }\n        }\n    }\n\n    public Node<T> getMinimum(Node<T> startPoint) {\n        Node<T> current = startPoint;\n        Node<T> parent = current;\n        while (current != null) {\n            parent = current;\n            current = current.getLeftChild();\n        }\n        return parent;\n    }\n\n    public Node<T> getMaximum(Node<T> startPoint) {\n        Node<T> current = startPoint;\n        Node<T> parent = current;\n        while (current != null) {\n            parent = current;\n            current = current.getRightChild();\n        }\n        return parent;\n    }\n\n    public Node<T> getSuccessor(Node<T> deleteNode) {\n        Node<T> parentSuccessor = deleteNode;\n        Node<T> successor = deleteNode;\n        Node<T> current = successor.getRightChild();\n        while (current != null) {\n            parentSuccessor = successor;\n            successor = current;\n            current = current.getLeftChild();\n        }\n\n        if (successor != deleteNode.getRightChild()) {\n            parentSuccessor.setLeftChild(successor.getRightChild());\n            successor.setRightChild(deleteNode.getRightChild());\n        }\n        return successor;\n    }\n\n    public boolean delete(int deleteKey) {\n        Node<T> current = root;\n        Node<T> parent = current;\n        boolean isLeftChild = false;\n        while (current.getKey() != deleteKey) {\n            parent = current;\n            if (deleteKey < current.getKey()) {\n                current = current.getLeftChild();\n                isLeftChild = true;\n            } else {\n                isLeftChild = false;\n                current = current.getRightChild();\n            }\n            if (current == null)\n                return false;\n        }\n\n        if (current.getLeftChild() == null && current.getRightChild() == null) {\n            if (current == root)\n                current = null;\n            else if (isLeftChild)\n                parent.setLeftChild(null);\n            else\n                parent.setRightChild(null);\n        }\n        else if (current.getRightChild() == null) {\n            if (current == root)\n                root = current.getLeftChild();\n            else if (isLeftChild)\n                parent.setLeftChild(current.getLeftChild());\n            else\n                current.setRightChild(current.getLeftChild());\n        } else if (current.getLeftChild() == null) {\n            if (current == root)\n                root = current.getRightChild();\n            else if (isLeftChild)\n                parent.setLeftChild(current.getRightChild());\n            else\n                parent.setRightChild(current.getRightChild());\n        } \n        else {\n            Node<T> successor = getSuccessor(current);\n            if (current == root)\n                root = successor;\n            else if (isLeftChild)\n                parent.setLeftChild(successor);\n            else\n                parent.setRightChild(successor);\n        }\n        return true;\n    }\n\n    public void inOrder(Node<T> current) {\n        if (current != null) {\n            inOrder(current.getLeftChild());\n            System.out.println(current.getData() + \" \");\n            inOrder(current.getRightChild());\n        }\n    }\n}\n<\/code><\/pre>\n
      P.S.<\/h2>\n
      <\/p>\n
      Zr\u00fatenie na O(n)<\/h3>\n
      \nMnoh\u00ed z v\u00e1s si mohli v\u0161imn\u00fa\u0165: a \u010do ak by sme urobili, aby sa strom stal nevyv\u00e1\u017een\u00fdm? Napr\u00edklad, ak by sme do stromu vkladali uzly s rast\u00facimi k\u013e\u00fa\u010dmi: 1,2,3,4,5,6\u2026 Potom bude strom pripom\u00edna\u0165 prepojen\u00fd zoznam. A \u00e1no, strom strat\u00ed svoju stromov\u00fa \u0161trukt\u00faru, a t\u00fdm aj efekt\u00edvnos\u0165 pr\u00edstupu k \u00fadajom. Zlo\u017eitosti oper\u00e1ci\u00ed vyh\u013ead\u00e1vania, vkladania a odstra\u0148ovania sa stan\u00fa rovnak\u00fdmi, ako pri prepojen\u00fdch zoznamoch: O(n). V tom sa prejavuje jeden z najd\u00f4le\u017eitej\u0161\u00edch nedostatkov bin\u00e1rnych stromov, pod\u013ea m\u00f4jho n\u00e1zoru.<\/p>\n
      Len registrovan\u00ed pou\u017e\u00edvatelia sa m\u00f4\u017eu z\u00fa\u010dastni\u0165 prieskumu. Prihl\u00e1ste sa<\/a><\/noindex>, pros\u00edm.<\/p>\n
      Nie som na habre ve\u013emi dlho a chcel by som vedie\u0165, o ak\u00fdch t\u00e9mach by ste chceli vidie\u0165 viac \u010dl\u00e1nkov?<\/h2>\n
        \n
      • \n
                            D\u00e1tov\u00e9 \u0161trukt\u00fary<\/p>\n<\/li>\n
      • \n
                            Algoritmy (DP, rekurzia, kompresia d\u00e1t at\u010f.)<\/p>\n<\/li>\n
      • \n
                            Pou\u017eitie d\u00e1tov\u00fdch \u0161trukt\u00far a algoritmov v re\u00e1lnom \u017eivote<\/p>\n<\/li>\n
      • \n
                            Programovanie android aplik\u00e1ci\u00ed v Jave<\/p>\n<\/li>\n
      • \n
                            Programovanie webov\u00fdch aplik\u00e1ci\u00ed v Jave<\/p>\n<\/li>\n<\/ul>\n
            Hlasovali 2 u\u017e\u00edvatelia. Zdr\u017eali sa 1 u\u017e\u00edvate\u013e.
        \n
        Zdroj: habr.com<\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"
        \u041f\u0440\u0435\u043b\u044e\u0434\u0438\u044f \u042d\u0442\u0430 \u0441\u0442\u0430\u0442\u044c\u044f \u043f\u043e\u0441\u0432\u044f\u0449\u0435\u043d\u0430 \u0431\u0438\u043d\u0430\u0440\u043d\u044b\u043c \u0434\u0435\u0440\u0435\u0432\u044c\u044f\u043c \u043f\u043e\u0438\u0441\u043a\u0430. \u041d\u0435\u0434\u0430\u0432\u043d\u043e \u0434\u0435\u043b\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u044e \u043f\u0440\u043e \u0441\u0436\u0430\u0442\u0438\u0435 \u0434\u0430\u043d\u043d\u044b\u0445 \u043c\u0435\u0442\u043e\u0434\u043e\u043c \u0425\u0430\u0444\u0444\u043c\u0430\u043d\u0430. \u0422\u0430\u043c \u044f \u043d\u0435 \u043e\u0447\u0435\u043d\u044c \u043e\u0431\u0440\u0430\u0449\u0430\u043b \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435 \u043d\u0430 \u0431\u0438\u043d\u0430\u0440\u043d\u044b\u0435 \u0434\u0435\u0440\u0435\u0432\u044c\u044f, \u0438\u0431\u043e \u043c\u0435\u0442\u043e\u0434\u044b \u043f\u043e\u0438\u0441\u043a\u0430, \u0432\u0441\u0442\u0430\u0432\u043a\u0438, \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u043d\u0435 \u0431\u044b\u043b\u0438 \u0430\u043a\u0442\u0443\u0430\u043b\u044c\u043d\u044b. \u0422\u0435\u043f\u0435\u0440\u044c \u0440\u0435\u0448\u0438\u043b \u043d\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u0441\u0442\u0430\u0442\u044c\u044e \u0438\u043c\u0435\u043d\u043d\u043e \u043f\u0440\u043e \u0434\u0435\u0440\u0435\u0432\u044c\u044f. \u041f\u043e\u0436\u0430\u043b\u0443\u0439, \u043d\u0430\u0447\u043d\u0435\u043c. \u0414\u0435\u0440\u0435\u0432\u043e \u2014 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445, \u0441\u043e\u0441\u0442\u043e\u044f\u0449\u0430\u044f \u0438\u0437 \u0443\u0437\u043b\u043e\u0432, \u0441\u043e\u0435\u0434\u0438\u043d\u0435\u043d\u043d\u044b\u0445 \u0440\u0435\u0431\u0440\u0430\u043c\u0438. \u041c\u043e\u0436\u043d\u043e \u0441\u043a\u0430\u0437\u0430\u0442\u044c, \u0447\u0442\u043e \u0434\u0435\u0440\u0435\u0432\u043e \u2014 […]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":22528,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[688],"tags":[],"class_list":["post-30530","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-administrirovanie"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\n","aioseo_head_json":{"title":"\ud83e\udd47Binary Tree alebo ako pripravi\u0165 bin\u00e1rny strom vyh\u013ead\u00e1vania | ProHoster","description":"Prelude Tento \u010dl\u00e1nok je venovan\u00fd bin\u00e1rnym stromom vyh\u013ead\u00e1vania.","canonical_url":"https:\/\/prohoster.info\/sk\/blog\/administrirovanie\/binary-tree-ili-kak-prigotovit-binarnoe-derevo-poiska","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"sk_SK","og:site_name":"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b","og:type":"article","og:title":"\ud83e\udd47Binary Tree \u0438\u043b\u0438 \u043a\u0430\u043a \u043f\u0440\u0438\u0433\u043e\u0442\u043e\u0432\u0438\u0442\u044c \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u043e\u0438\u0441\u043a\u0430 | ProHoster","og:description":"\u041f\u0440\u0435\u043b\u044e\u0434\u0438\u044f \u042d\u0442\u0430 \u0441\u0442\u0430\u0442\u044c\u044f \u043f\u043e\u0441\u0432\u044f\u0449\u0435\u043d\u0430 \u0431\u0438\u043d\u0430\u0440\u043d\u044b\u043c \u0434\u0435\u0440\u0435\u0432\u044c\u044f\u043c \u043f\u043e\u0438\u0441\u043a\u0430.","og:url":"https:\/\/prohoster.info\/sk\/blog\/administrirovanie\/binary-tree-ili-kak-prigotovit-binarnoe-derevo-poiska","og:image":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:secure_url":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:width":350,"og:image:height":350,"article:published_time":"2019-10-31T18:36:01+00:00","article:modified_time":"2019-10-31T18:36:01+00:00","article:publisher":"https:\/\/www.facebook.com\/prohoster","article:author":"https:\/\/www.facebook.com\/prohoster"},"aioseo_meta_data":{"post_id":"30530","title":null,"description":null,"keywords":null,"keyphrases":null,"primary_term":null,"canonical_url":null,"og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":null,"og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"","isEnabled":true},"graphs":[]},"schema_type":null,"schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":null,"robots_max_videopreview":null,"robots_max_imagepreview":"large","priority":null,"frequency":null,"local_seo":null,"seo_analyzer_scan_date":"2026-01-21 01:39:20","breadcrumb_settings":null,"limit_modified_date":false,"reviewed_by":null,"ai":null,"created":"2021-03-01 03:33:27","updated":"2026-01-21 01:39:20","focus_keyword":null,"additional_keywords":null,"truseo_locale":null},"gt_translate_keys":[{"key":"link","format":"url"}],"_links":{"self":[{"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/posts\/30530","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/comments?post=30530"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/posts\/30530\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/media\/22528"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/media?parent=30530"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/categories?post=30530"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/tags?post=30530"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}