{"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\/cs\/blog\/administrirovanie\/binary-tree-ili-kak-prigotovit-binarnoe-derevo-poiska","title":{"rendered":"Bin\u00e1rn\u00ed strom nebo jak vytvo\u0159it bin\u00e1rn\u00ed vyhled\u00e1vac\u00ed strom","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Prelude<\/h2>\n

\nTento \u010dl\u00e1nek se zab\u00fdv\u00e1 bin\u00e1rn\u00edmi vyhled\u00e1vac\u00edmi stromy. Ned\u00e1vno jsem psal \u010dl\u00e1nek o kompresi dat pomoc\u00ed Huffmanovy metody.<\/a><\/noindex> Tam jsem se p\u0159\u00edli\u0161 nezam\u011b\u0159oval na bin\u00e1rn\u00ed stromy, proto\u017ee metody vyhled\u00e1v\u00e1n\u00ed, vkl\u00e1d\u00e1n\u00ed a maz\u00e1n\u00ed nebyly relevantn\u00ed. Nyn\u00ed jsem se rozhodl napsat \u010dl\u00e1nek pr\u00e1v\u011b o stromech. Mysl\u00edm, \u017ee za\u010dneme. <\/p>\n

Strom je datov\u00e1 struktura slo\u017een\u00e1 z uzl\u016f spojen\u00fdch hranami. M\u016f\u017eeme \u0159\u00edci, \u017ee strom je zvl\u00e1\u0161tn\u00edm p\u0159\u00edpadem grafu. Zde je p\u0159\u00edklad stromu: <\/p>\n

\"Bin\u00e1rn\u00ed
\n
\nTo nen\u00ed bin\u00e1rn\u00ed vyhled\u00e1vac\u00ed strom! V\u0161echno n\u00ed\u017ee!
\n<\/a><\/noindex><\/p>\n

Terminologie<\/h2>\n

<\/p>\n

Ko\u0159en<\/h4>\n

\nKo\u0159en stromu<\/i> je nejvy\u0161\u0161\u00ed uzel. V p\u0159\u00edkladu to je uzel A. Ze stromu m\u016f\u017ee k jak\u00e9mukoli jin\u00e9mu uzlu v\u00e9st pouze jedna cesta! Ve skute\u010dnosti m\u016f\u017ee b\u00fdt jak\u00fdkoli uzel pova\u017eov\u00e1n za ko\u0159en odpov\u00eddaj\u00edc\u00edho podstromu.<\/p>\n

Rodi\u010de\/potomci<\/h4>\n

\nV\u0161echny uzly krom\u011b ko\u0159enov\u00e9ho maj\u00ed p\u0159esn\u011b jednu hranu vedouc\u00ed nahoru k jin\u00e9mu uzlu. Uzel um\u00edst\u011bn\u00fd nad aktu\u00e1ln\u00edm se naz\u00fdv\u00e1 rodi\u010dem<\/i> tohoto uzlu. Uzel um\u00edst\u011bn\u00fd pod aktu\u00e1ln\u00edm uzlem a spojen\u00fd s n\u00edm se naz\u00fdv\u00e1 potomkem<\/i> tohoto uzlu. Poj\u010fme tomu d\u00e1t p\u0159\u00edklad. Vezm\u011bme uzel B, jeho rodi\u010dem bude uzel A a potomky budou uzly D, E a F.<\/p>\n

List<\/h4>\n

\nUzel, kter\u00fd nem\u00e1 \u017e\u00e1dn\u00e9 potomky, se naz\u00fdv\u00e1 list stromu. V p\u0159\u00edkladu budou listy uzly D, E, F, G, I, J, K.<\/p>\n

To je z\u00e1kladn\u00ed terminologie. Dal\u0161\u00ed pojmy budou rozebr\u00e1ny d\u00e1le. Tak\u017ee bin\u00e1rn\u00ed strom je strom, ve kter\u00e9m m\u00e1 ka\u017ed\u00fd uzel maxim\u00e1ln\u011b dva potomky. Jak jste asi uhodli, strom z p\u0159\u00edkladu nebude bin\u00e1rn\u00ed, proto\u017ee uzly B a H maj\u00ed v\u00edce ne\u017e dva potomky. Zde je p\u0159\u00edklad bin\u00e1rn\u00edho stromu:<\/p>\n

\"Bin\u00e1rn\u00ed
\n
\nUzlech stromu m\u016f\u017ee b\u00fdt jak\u00e1koli informace. Bin\u00e1rn\u00ed vyhled\u00e1vac\u00ed strom je bin\u00e1rn\u00ed strom, kter\u00fd m\u00e1 n\u00e1sleduj\u00edc\u00ed vlastnosti:<\/p>\n

    \n
  1. Ob\u011b podstromy \u2013 lev\u00fd a prav\u00fd \u2013 jsou bin\u00e1rn\u00edmi vyhled\u00e1vac\u00edmi stromy.<\/li>\n
  2. U v\u0161ech uzl\u016f lev\u00e9ho podstromu libovoln\u00e9ho uzlu X jsou hodnoty kl\u00ed\u010d\u016f dat men\u0161\u00ed ne\u017e hodnota kl\u00ed\u010de dat samotn\u00e9ho uzlu X.<\/li>\n
  3. U v\u0161ech uzl\u016f prav\u00e9ho podstromu libovoln\u00e9ho uzlu X jsou hodnoty kl\u00ed\u010d\u016f dat v\u011bt\u0161\u00ed nebo rovny hodnot\u011b kl\u00ed\u010de dat samotn\u00e9ho uzlu X. <\/li>\n<\/ol>\n

    Kl\u00ed\u010d<\/i> \u2013 jak\u00e1koli charakteristika uzlu (nap\u0159\u00edklad \u010d\u00edslo). Kl\u00ed\u010d je pot\u0159ebn\u00fd, aby bylo mo\u017en\u00e9 naj\u00edt prvek stromu, kter\u00fd odpov\u00edd\u00e1 tomuto kl\u00ed\u010di. P\u0159\u00edklad bin\u00e1rn\u00edho vyhled\u00e1vac\u00edho stromu:<\/p>\n

    \"Bin\u00e1rn\u00ed
    \n<\/p>\n

    Zobrazen\u00ed stromu<\/h2>\n

    \nB\u011bhem postupu budu uv\u00e1d\u011bt n\u011bkter\u00e9 (mo\u017en\u00e1 ne\u00fapln\u00e9) \u00faryvky k\u00f3du, abych zlep\u0161il va\u0161e porozum\u011bn\u00ed. Kompletn\u00ed k\u00f3d bude na konci \u010dl\u00e1nku. <\/p>\n

    Strom se skl\u00e1d\u00e1 z uzl\u016f. Struktura uzlu:<\/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\/\/...dal\u0161\u00ed metody uzlu\n}\n<\/code><\/pre>\n
    \nKa\u017ed\u00fd uzel m\u00e1 dva potomky (pravd\u011bpodobn\u011b, potomci leftChild a\/nebo rightChild mohou m\u00edt hodnotu null). Asi jste pochopili, \u017ee v tomto p\u0159\u00edpad\u011b data \u2014 data ulo\u017een\u00e1 v uzlu; key \u2014 kl\u00ed\u010d uzlu.<\/p>\n
    S uzlem jsme se sezn\u00e1mili, te\u010f si promluvme o aktu\u00e1ln\u00edch probl\u00e9mech strom\u016f. Zde a d\u00e1le pod pojmem \"strom\" budu m\u00edt na mysli koncept bin\u00e1rn\u00edho vyhled\u00e1vac\u00edho stromu. Struktura bin\u00e1rn\u00edho stromu:<\/p>\n
    public class BinaryTree<T> {\n     private Node<T> root;\n\n    \/\/metody stromu\n}\n<\/code><\/pre>\n
    Jako pole t\u0159\u00eddy pot\u0159ebujeme pouze ko\u0159en stromu, proto\u017ee od ko\u0159ene pomoc\u00ed metod getLeftChild() a getRightChild() se m\u016f\u017eeme dostat k libovoln\u00e9mu uzlu stromu.<\/p>\n
    Algoritmy ve strom\u011b<\/h2>\n
    <\/p>\n
    Hled\u00e1n\u00ed<\/h3>\n
    \nP\u0159edstavte si, \u017ee m\u00e1te postaven\u00fd strom. Jak nal\u00e9zt prvek s kl\u00ed\u010dem key? Je t\u0159eba postupn\u011b j\u00edt od ko\u0159ene dol\u016f po strom\u011b a porovn\u00e1vat hodnotu key s kl\u00ed\u010dem aktu\u00e1ln\u00edho uzlu: pokud je key men\u0161\u00ed ne\u017e kl\u00ed\u010d aktu\u00e1ln\u00edho uzlu, p\u0159ejd\u011bte na lev\u00e9ho potomka uzlu, pokud v\u011bt\u0161\u00ed \u2014 na prav\u00e9ho, pokud jsou kl\u00ed\u010de stejn\u00e9 \u2014 hledan\u00fd uzel byl nalezen! Odpov\u00eddaj\u00edc\u00ed 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
    \nPokud current se stane rovno null, znamen\u00e1 to, \u017ee prohled\u00e1v\u00e1n\u00ed dos\u00e1hlo konce stromu (na konceptu\u00e1ln\u00ed \u00farovni se nach\u00e1z\u00edte na neexistuj\u00edc\u00edm m\u00edst\u011b stromu \u2014 potomku listu).<\/p>\n
    Zva\u017eme \u00fa\u010dinnost algoritmu hled\u00e1n\u00ed na vyv\u00e1\u017een\u00e9m stromu (stromu, ve kter\u00e9m jsou uzly rozlo\u017eeny v\u00edce \u010di m\u00e9n\u011b rovnom\u011brn\u011b). V tomto p\u0159\u00edpad\u011b bude \u00fa\u010dinnost hled\u00e1n\u00ed O(log(n)), p\u0159i\u010dem\u017e logaritmus je se z\u00e1kladem 2. Pod\u00edvejte se: pokud je v vyv\u00e1\u017een\u00e9m strom\u011b n prvk\u016f, znamen\u00e1 to, \u017ee bude log(n) se z\u00e1kladem 2 \u00farovn\u00ed stromu. A p\u0159i hled\u00e1n\u00ed, b\u011bhem jednoho kroku cyklu, sestupujete o jednu \u00farove\u0148.<\/p>\n
    Vlo\u017een\u00ed<\/h3>\n
    \nPokud jste pochopili podstatu hled\u00e1n\u00ed, nebude pro v\u00e1s obt\u00ed\u017en\u00e9 pochopit vlo\u017een\u00ed. Sta\u010d\u00ed jen sestoupit na \u00farove\u0148 stromu (podle pravidel uveden\u00fdch v hled\u00e1n\u00ed) a st\u00e1t se jeho potomkem \u2014 lev\u00fdm nebo prav\u00fdm, v z\u00e1vislosti na kl\u00ed\u010di. Implementace:<\/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 p\u0159\u00edpad\u011b je nutn\u00e9 krom\u011b aktu\u00e1ln\u00edho uzlu uchov\u00e1vat tak\u00e9 informace o jeho rodi\u010di. Kdy\u017e current bude rovno null, v prom\u011bnn\u00e9 parent bude pot\u0159ebn\u00fd list. 
    \nEfektivita vkl\u00e1d\u00e1n\u00ed bude zjevn\u011b stejn\u00e1 jako p\u0159i hled\u00e1n\u00ed \u2014 O(log(n)).<\/p>\n
    Odstranit<\/h3>\n
    \nOdstran\u011bn\u00ed je nejt\u011b\u017e\u0161\u00ed operace, kterou je pot\u0159eba prov\u00e9st se stromem. Je jasn\u00e9, \u017ee nejprve bude nutn\u00e9 naj\u00edt prvek, kter\u00fd se chyst\u00e1me odstranit. Ale co potom? Pokud pouze p\u0159i\u0159ad\u00edme jeho odkazu hodnotu null, ztrat\u00edme informace o podstromu, jeho\u017e ko\u0159enem je tento uzel. Metody odstran\u011bn\u00ed stromu d\u011bl\u00edme na t\u0159i p\u0159\u00edpady.<\/p>\n
    Prvn\u00ed p\u0159\u00edpad. Odstra\u0148ovan\u00fd uzel nem\u00e1 potomky.<\/h4>\n
    \nPokud odstra\u0148ovan\u00fd uzel nem\u00e1 potomky, znamen\u00e1 to, \u017ee je listem. Proto m\u016f\u017eeme jednodu\u0161e p\u0159i\u0159adit pol\u00edm leftChild nebo rightChild jeho rodi\u010de hodnotu null. <\/p>\n
    Druh\u00fd p\u0159\u00edpad. Odstra\u0148ovan\u00fd uzel m\u00e1 jednoho potomka.<\/h4>\n
    \nTento p\u0159\u00edpad tak\u00e9 nen\u00ed p\u0159\u00edli\u0161 slo\u017eit\u00fd. Vra\u0165me se k na\u0161emu p\u0159\u00edkladu. P\u0159edpokl\u00e1dejme, \u017ee mus\u00edme odstranit prvek s kl\u00ed\u010dem 14. Souhlas\u00edte, \u017ee proto\u017ee je \u2014 prav\u00fdm potomkem uzlu s kl\u00ed\u010dem 10, jak\u00fdkoli jeho potomek (v tomto p\u0159\u00edpad\u011b prav\u00fd) bude m\u00edt kl\u00ed\u010d v\u011bt\u0161\u00ed ne\u017e 10, tak\u017ee ho lze snadno 'vy\u0159\u00edznout' ze stromu, a rodi\u010de propojit p\u0159\u00edmo s potomkem odstra\u0148ovan\u00e9ho uzlu, tj. uzel s kl\u00ed\u010dem 10 propojit s uzlem 13. Podobn\u00e1 situace by nastala, kdybychom museli odstranit uzel, kter\u00fd je lev\u00fdm potomkem sv\u00e9ho rodi\u010de. Zamyslete se nad t\u00edm sami \u2014 p\u0159esn\u00e1 analogie. <\/p>\n
    T\u0159et\u00ed p\u0159\u00edpad. Uzel m\u00e1 dva potomky.<\/h4>\n
    \nNejkomplexn\u011bj\u0161\u00ed p\u0159\u00edpad. Rozebere na nov\u00e9m p\u0159\u00edkladu.<\/p>\n
    \"Bin\u00e1rn\u00ed
    \n<\/p>\n
    Hled\u00e1n\u00ed n\u00e1stupce.<\/h4>\n
    \n P\u0159edstavme si, \u017ee je pot\u0159eba odstranit uzel s kl\u00ed\u010dem 25. Kdo ho nahrad\u00ed? N\u011bkdo z jeho n\u00e1sledovn\u00edk\u016f (potomk\u016f nebo potomk\u016f potomk\u016f) by m\u011bl b\u00fdt n\u00e1stupcem<\/i>(ten, kdo obsad\u00ed m\u00edsto odstran\u011bn\u00e9ho uzlu). <\/p>\n
    Jak pochopit, kdo by m\u011bl b\u00fdt n\u00e1stupcem? Intuitivn\u011b je jasn\u00e9, \u017ee jde o uzel v strom\u011b, jeho\u017e kl\u00ed\u010d je nejv\u011bt\u0161\u00ed, ale st\u00e1le men\u0161\u00ed ne\u017e kl\u00ed\u010d odstraniteln\u00fdch uzl\u016f. Algoritmus spo\u010d\u00edv\u00e1 v n\u00e1sleduj\u00edc\u00edm. Mus\u00edme p\u0159ej\u00edt k jeho prav\u00e9mu potomkovi (v\u017edy k prav\u00e9mu, proto\u017ee, jak ji\u017e bylo zm\u00edn\u011bno, kl\u00ed\u010d n\u00e1stupce je v\u011bt\u0161\u00ed ne\u017e kl\u00ed\u010d odstra\u0148ovan\u00e9ho uzlu) a pot\u00e9 proj\u00edt \u0159et\u011bzec lev\u00fdch potomk\u016f tohoto prav\u00e9ho potomka. V p\u0159\u00edkladu p\u0159ejdeme k uzlu s kl\u00ed\u010dem 35 a pot\u00e9 se proch\u00e1z\u00edme dol\u016f po \u0159et\u011bzci jeho lev\u00fdch potomk\u016f \u2013 v tomto p\u0159\u00edpad\u011b se tento \u0159et\u011bzec skl\u00e1d\u00e1 pouze z uzlu s kl\u00ed\u010dem 30. P\u0159\u00edsn\u011b vzato, hled\u00e1me nejmen\u0161\u00ed uzel v sad\u011b uzl\u016f, kter\u00e9 jsou v\u011bt\u0161\u00ed ne\u017e hledan\u00fd uzel.<\/p>\n
    \"Bin\u00e1rn\u00ed
    \n
    \nK\u00f3d metody pro hled\u00e1n\u00ed n\u00e1stupce:<\/p>\n
        public Node getSuccessor(Node deleteNode) {\n        Node parentSuccessor = deleteNode; \/\/ rodi\u010d n\u00e1stupce\n        Node successor = deleteNode; \/\/ n\u00e1stupce\n        Node current = successor.getRightChild(); \/\/ prost\u011b \"proch\u00e1zej\u00edc\u00ed\" uzel\n        while (current != null) {\n            parentSuccessor = successor;\n            successor = current;\n            current = current.getLeftChild();\n        }\n        \/\/ p\u0159i v\u00fdstupu z cyklu m\u00e1me n\u00e1stupce a rodi\u010de n\u00e1stupce\n        if (successor != deleteNode.getRightChild()) { \/\/ pokud n\u00e1stupce nesouhlas\u00ed s prav\u00fdm potomkem odstran\u011bn\u00e9ho uzlu\n            parentSuccessor.setLeftChild(successor.getRightChild()); \/\/ pak si jeho rodi\u010d vezme potomka n\u00e1stupce, aby ho neztratil\n            successor.setRightChild(deleteNode.getRightChild()); \/\/ propojujeme n\u00e1stupce s prav\u00fdm potomkem odstran\u011bn\u00e9ho uzlu\n        }\n        return successor;\n    }\n<\/code><\/pre>\n
    \nCel\u00fd k\u00f3d metody delete:<\/p>\n
    public boolean delete(int deleteKey) {\n        Node current = root;\n        Node parent = current;\n        boolean isLeftChild = false;  \/\/ V z\u00e1vislosti na tom, zda je odstra\u0148ovan\u00fd uzel lev\u00fdm nebo prav\u00fdm potomkem sv\u00e9ho rodi\u010de, bude boolean prom\u011bnn\u00e1 isLeftChild nab\u00fdvat hodnoty true nebo 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) {  \/\/ prvn\u00ed p\u0159\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 p\u0159\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 {  \/\/ t\u0159et\u00ed p\u0159\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
    \nSlo\u017eitost m\u016f\u017ee b\u00fdt aproximov\u00e1na k O(log(n)).<\/p>\n
    Hled\u00e1n\u00ed maxima\/minima v stromu<\/h3>\n
    \nJe z\u0159ejm\u00e9, jak naj\u00edt minim\u00e1ln\u00ed\/maxim\u00e1ln\u00ed hodnotu ve stromu \u2014 je t\u0159eba se postupn\u011b p\u0159esouvat po \u0159et\u011bzci lev\u00fdch\/pr\u00e1vn\u00edch prvk\u016f stromu; kdy\u017e se dostanete k listu, ten bude minim\u00e1ln\u00edm\/maxim\u00e1ln\u00edm prvkem.<\/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
    \nSlo\u017eitost \u2014 O(log(n))<\/p>\n
    Symetrick\u00fd pr\u016fchod<\/h3>\n
    \nPr\u016fchod \u2014 n\u00e1v\u0161t\u011bva ka\u017ed\u00e9ho uzlu stromu s c\u00edlem prov\u00e9st s n\u00edm n\u011bjakou akci.<\/p>\n
    Algoritmus rekurzivn\u00edho symetrick\u00e9ho pr\u016fchodu:<\/p>\n
      \n
    1. Prove\u010fte akci s lev\u00fdm potomkem<\/li>\n
    2. Prove\u010fte akci se sebou<\/li>\n
    3. Prove\u010fte akci s prav\u00fdm potomkem<\/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() + \" \"); \/\/ Zde m\u016f\u017ee b\u00fdt cokoliv\n            inOrder(current.getRightChild());\n        }\n    }\n<\/code><\/pre>\n
      <\/p>\n
      Z\u00e1v\u011br<\/h2>\n
      \nKone\u010dn\u011b! Pokud jsem n\u011bco nedo\u0159ekl nebo m\u00e1te n\u011bjak\u00e9 p\u0159ipom\u00ednky, budu \u010dekat na koment\u00e1\u0159e. Jak jsem sl\u00edbil, uv\u00e1d\u00edm cel\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
      Degenerace do O(n)<\/h3>\n
      \nMnoz\u00ed z v\u00e1s si mo\u017en\u00e1 v\u0161imli: co kdy\u017e ud\u011bl\u00e1me, aby se strom stal nevyv\u00e1\u017een\u00fdm? Nap\u0159\u00edklad, pokud do stromu vlo\u017e\u00edme uzly s rostouc\u00edmi kl\u00ed\u010di: 1,2,3,4,5,6\u2026 To by byl strom s n\u011b\u010d\u00edm p\u0159ipom\u00ednaj\u00edc\u00ed spojov\u00fd seznam. A ano, strom ztrat\u00ed svou stromovou strukturu, a tedy i efektivitu p\u0159\u00edstupu k dat\u016fm. Slo\u017eitost operac\u00ed vyhled\u00e1v\u00e1n\u00ed, vkl\u00e1d\u00e1n\u00ed, odstra\u0148ov\u00e1n\u00ed se stanou podobn\u00fdmi jako u spojov\u00e9ho seznamu: O(n). A to je jeden z nejd\u016fle\u017eit\u011bj\u0161\u00edch nedostatk\u016f bin\u00e1rn\u00edch strom\u016f, podle m\u00e9ho n\u00e1zoru.<\/p>\n
      Pouze registrovan\u00ed u\u017eivatel\u00e9 se mohou \u00fa\u010dastnit ankety. P\u0159ihlaste se<\/a><\/noindex>, pros\u00edm.<\/p>\n
      Ned\u00e1vno jsem na Habru a cht\u011bl bych v\u011bd\u011bt, o jak\u00fdch t\u00e9matech byste cht\u011bli vid\u011bt v\u00edce \u010dl\u00e1nk\u016f?<\/h2>\n
        \n
      • \n
                            Datov\u00e9 struktury<\/p>\n<\/li>\n
      • \n
                            Algoritmy (DP, rekurze, komprese dat atd.)<\/p>\n<\/li>\n
      • \n
                            Aplikace datov\u00fdch struktur a algoritm\u016f v re\u00e1ln\u00e9m \u017eivot\u011b<\/p>\n<\/li>\n
      • \n
                            Programov\u00e1n\u00ed android aplikac\u00ed v Jav\u011b<\/p>\n<\/li>\n
      • \n
                            Programov\u00e1n\u00ed webov\u00fdch aplikac\u00ed v Jav\u011b<\/p>\n<\/li>\n<\/ul>\n
            Hlasovalo 2 u\u017eivatel\u016f. Zdr\u017eel se 1 u\u017eivatel.
        \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 neboli jak p\u0159ipravit bin\u00e1rn\u00ed strom hled\u00e1n\u00ed | ProHoster","description":"P\u0159edmluva Tento \u010dl\u00e1nek je v\u011bnov\u00e1n bin\u00e1rn\u00edm strom\u016fm hled\u00e1n\u00ed.","canonical_url":"https:\/\/prohoster.info\/cs\/blog\/administrirovanie\/binary-tree-ili-kak-prigotovit-binarnoe-derevo-poiska","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"cs_CZ","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\/cs\/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\/cs\/wp-json\/wp\/v2\/posts\/30530","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/comments?post=30530"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/posts\/30530\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/media\/22528"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/media?parent=30530"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/categories?post=30530"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/tags?post=30530"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}