{"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\/lv\/blog\/administrirovanie\/binary-tree-ili-kak-prigotovit-binarnoe-derevo-poiska","title":{"rendered":"Binary Tree jeb k\u0101 pagatavot bin\u0101ro me\u017eu mekl\u0113\u0161anai","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Priek\u0161v\u0101rds<\/h2>\n

\n\u0160is raksts ir velt\u012bts bin\u0101rajiem me\u017eiem mekl\u0113\u0161anai. Nesen veicu rakstu par datu saspie\u0161anu, izmantojot Huffma\u0146a metodi.<\/a><\/noindex> Tur es \u012bpa\u0161i nepiev\u0113r\u0161u uzman\u012bbu bin\u0101rajiem me\u017eiem, jo mekl\u0113\u0161anas, ievieto\u0161anas un dz\u0113\u0161anas metodes nebija aktu\u0101las. Tagad esmu nol\u0113mis uzrakst\u012bt rakstu tie\u0161i par kokiem. S\u0101ksim. <\/p>\n

Koks \u2014 datu strukt\u016bra, kas sast\u0101v no mezgliem, kas savienoti ar mal\u0101m. Var teikt, ka koks ir graf\u0113tiskas strukt\u016bras \u012bpa\u0161s gad\u012bjums. L\u016bk, koka piem\u0113rs: <\/p>\n

\"Binary
\n
\nTas nav bin\u0101rais me\u017es! Visi zem katras sada\u013cas!
\n<\/a><\/noindex><\/p>\n

Terminolo\u0123ija<\/h2>\n

<\/p>\n

Sakne<\/h4>\n

\nKoka sakne<\/i> ir augst\u0101kais mezgls. \u0160aj\u0101 piem\u0113r\u0101 tas ir mezgls A. Koks no saknes uz jebkuru citu mezglu var novest tikai pa vienu ce\u013cu! Paties\u012bb\u0101 jebkuru mezglu var uzskat\u012bt par sakni atbilsto\u0161ajam t\u0101 mezglam apak\u0161kokam.<\/p>\n

Vec\u0101ki\/p\u0113cn\u0101c\u0113ji<\/h4>\n

\nVisiem mezgliem, iz\u0146emot sakni, ir tie\u0161i viena mala, kas ved uz citu mezglu. Mezgla, kas atrodas virs pa\u0161reiz\u0113j\u0101, nosaukums ir vec\u0101ks<\/i> \u0161\u012b mezgla. Mezgla, kas atrodas zem pa\u0161reiz\u0113j\u0101 un savienots ar to, nosaukums ir p\u0113cn\u0101c\u0113js<\/i> \u0161\u012b mezgla. Apskat\u012bsim piem\u0113ru. Ja \u0146emam mezglu B, tad t\u0101 vec\u0101ks b\u016bs mezgls A, bet p\u0113cn\u0101c\u0113ji \u2014 mezgli D, E un F.<\/p>\n

Lapa<\/h4>\n

\nMezgla, kuram nav p\u0113cn\u0101c\u0113ju, nosaukums b\u016bs koka lapa. \u0160aj\u0101 piem\u0113r\u0101 lapas b\u016bs mezgli D, E, F, G, I, J, K.<\/p>\n

T\u0101 ir pamatterminolo\u0123ija. Citi j\u0113dzieni tiks apskat\u012bti v\u0113l\u0101k. T\u0101tad, bin\u0101rais koks ir koks, kur\u0101 katram mezglam ir ne vair\u0101k k\u0101 divi p\u0113cn\u0101c\u0113ji. K\u0101 j\u016bs var\u0113j\u0101t uzmin\u0113t, piem\u0113r\u0101 eso\u0161ais koks neb\u016bs bin\u0101rs, jo mezgliem B un H ir vair\u0101k nek\u0101 divi p\u0113cn\u0101c\u0113ji. L\u016bk, bin\u0101r\u0101 koka piem\u0113rs:<\/p>\n

\"Binary
\n
\nKokos var b\u016bt jebk\u0101da inform\u0101cija. Bin\u0101rais me\u017es mekl\u0113\u0161anai ir bin\u0101rais koks, kuram rakstur\u012bgas \u0161\u0101das \u012bpa\u0161\u012bbas:<\/p>\n

    \n
  1. Abi apak\u0161koki \u2014 kreisais un labais \u2014 ir bin\u0101rie me\u017ei mekl\u0113\u0161anai.<\/li>\n
  2. Visiem mezgliem kreisaj\u0101 apak\u0161kok\u0101 noteiktajam mezglam X datu atsl\u0113gu v\u0113rt\u012bbas ir maz\u0101kas nek\u0101 datu atsl\u0113gas v\u0113rt\u012bba pa\u0161am mezglam X.<\/li>\n
  3. Visiem mezgliem labaj\u0101 apak\u0161kok\u0101 noteiktajam mezglam X datu atsl\u0113gu v\u0113rt\u012bbas ir liel\u0101kas vai vien\u0101das ar datu atsl\u0113gas v\u0113rt\u012bbu pa\u0161am mezglam X. <\/li>\n<\/ol>\n

    Atsl\u0113ga<\/i> \u2014 k\u0101da mezgla \u012bpa\u0161\u012bba (piem\u0113ram, skaitlis). Atsl\u0113ga ir nepiecie\u0161ama, lai var\u0113tu atrast koka elementu, kuram atbilst \u0161\u012b atsl\u0113ga. Bin\u0101r\u0101 me\u017ea mekl\u0113\u0161anas piem\u0113rs:<\/p>\n

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

    Koka att\u0113lojums<\/h2>\n

    \nIes\u0101kot ce\u013cu, es snieg\u0161u da\u017eus (iesp\u0113jams, nepiln\u012bgus) koda fragmentus, lai uzlabotu j\u016bsu izpratni. Pilnais kods b\u016bs raksta beig\u0101s. <\/p>\n

    Koks sast\u0101v no mezgliem. Mezgla strukt\u016bra:<\/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\/\/...p\u0101r\u0113j\u0101s mezgla metodes\n}\n<\/code><\/pre>\n
    \nKatram mezglam ir divi p\u0113cn\u0101c\u0113ji (\u013coti iesp\u0113jams, ka \u013caudis leftChild un vai rightChild satur\u0113s v\u0113rt\u012bbu null). J\u016bs, iesp\u0113jams, saprat\u0101t, ka \u0161aj\u0101 gad\u012bjum\u0101 data \u2014 ir dati, kas glab\u0101jas mezgl\u0101; key \u2014 ir mezgla atsl\u0113ga.<\/p>\n
    Mezglu esam apskat\u012bju\u0161i, tagad run\u0101sim par aktu\u0101l\u0101m probl\u0113m\u0101m saist\u012bb\u0101 ar kokiem. \u0160eit un turpm\u0101k ar v\u0101rdu \u201ekoks\u201d es saprat\u012b\u0161u bin\u0101r\u0101 me\u017ea koncepciju. Bin\u0101r\u0101 me\u017ea strukt\u016bra:<\/p>\n
    public class BinaryTree<T> {\n     private Node<T> root;\n\n    \/\/koka metodes\n}\n<\/code><\/pre>\n
    K\u0101 k\u0101das klases lauku m\u0113s izmantosim tikai koka sakni, jo no saknes ar meto\u017eu getLeftChild() un getRightChild() pal\u012bdz\u012bbu var nok\u013c\u016bt pie jebkura koka mezgla.<\/p>\n
    Algoritmi kok\u0101<\/h2>\n
    <\/p>\n
    Mekl\u0113\u0161anai<\/h3>\n
    \nPie\u0146emsim, ka jums ir izveidots koks. K\u0101 atrast elementu ar atsl\u0113gu key? J\u0101virz\u0101s no saknes uz leju pa koku un j\u0101sal\u012bdzina key v\u0113rt\u012bba ar attiec\u012bg\u0101 mezgla atsl\u0113gu: ja key ir maz\u0101ks par attiec\u012bg\u0101 mezgla atsl\u0113gu, j\u0101p\u0101riet uz kreiso p\u0113cn\u0101c\u0113ju, ja liel\u0101ks \u2014 uz labo, ja atsl\u0113gas ir vien\u0101das \u2014 mekl\u0113tais mezgls ir atrasts! Atbilsto\u0161ais kods:<\/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
    \nJa current k\u013c\u016bst vien\u0101ds ar null, tas noz\u012bm\u0113, ka p\u0101rl\u016bko\u0161ana ir sasniegusi koka galu (konceptu\u0101l\u0101 l\u012bmen\u012b j\u016bs atrodaties neeso\u0161\u0101 koka viet\u0101 \u2014 lapu p\u0113cn\u0101c\u0113j\u0101).<\/p>\n
    Apskat\u012bsim mekl\u0113\u0161anas algoritma efektivit\u0101ti sabalans\u0113t\u0101 kok\u0101 (kok\u0101, kur mezgli ir sadal\u012bti apm\u0113ram vienm\u0113r\u012bgi). T\u0101d\u0101 gad\u012bjum\u0101 mekl\u0113\u0161anas efektivit\u0101te b\u016bs O(log(n)), \u0146emot v\u0113r\u0101 logaritmu ar pamatu 2. Skatieties: ja sabalans\u0113t\u0101 kok\u0101 ir n elementi, tas noz\u012bm\u0113, ka b\u016bs log(n) ar pamatu 2 l\u012bme\u0146u koka. Un mekl\u0113\u0161an\u0101, viens cikla solis ir vienas l\u012bme\u0146a nok\u0101pums.<\/p>\n
    Ievieto\u0161ana<\/h3>\n
    \nJa, ja varat saprast mekl\u0113\u0161anas b\u016bt\u012bbu, ievieto\u0161ana nerad\u012bs lielas gr\u016bt\u012bbas. Jums vienk\u0101r\u0161i j\u0101nok\u0101pj l\u012bdz koka lapai (saska\u0146\u0101 ar mekl\u0113\u0161an\u0101 aprakst\u012btajiem nolai\u0161an\u0101s noteikumiem) un j\u0101st\u0101jas t\u0101s p\u0113cn\u0101c\u0113ju viet\u0101 \u2013 kreisaj\u0101 vai labaj\u0101, atkar\u012bb\u0101 no atsl\u0113gas. Realiz\u0101cija:<\/p>\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<\/code><\/pre>\n
    \n\u0160aj\u0101 gad\u012bjum\u0101 ir j\u0101uztur inform\u0101cija ne tikai par pa\u0161reiz\u0113jo mezglu, bet ar\u012b par pa\u0161reiz\u0113j\u0101 mezgla vec\u0101ku. Kad current k\u013c\u016bs par null, main\u012bgaj\u0101 parent b\u016bs nepiecie\u0161am\u0101 lapa. 
    \nIevieto\u0161anas efektivit\u0101te, ac\u012bmredzot, b\u016bs t\u0101da pati k\u0101 mekl\u0113\u0161anai \u2013 O(log(n)).<\/p>\n
    Dz\u0113st<\/h3>\n
    \nDz\u0113\u0161ana ir visgr\u016bt\u0101k\u0101 oper\u0101cija, kas j\u0101veic ar koku. Ir skaidrs, ka vispirms j\u0101atrod elements, kuru m\u0113s gras\u0101mies dz\u0113st. Bet kas p\u0113c tam? Ja vienk\u0101r\u0161i pie\u0161\u0137iram t\u0101 atsauc\u0113 v\u0113rt\u012bbu null, m\u0113s zaud\u0113jam inform\u0101ciju par apak\u0161koku, kura sakne ir \u0161is mezgls. Koku dz\u0113\u0161anas metodes dal\u0101s tr\u012bs gad\u012bjumos.<\/p>\n
    Pirmais gad\u012bjums. Dz\u0113\u0161amais mezgls nav p\u0113cn\u0101c\u0113ju.<\/h4>\n
    \nJa dz\u0113\u0161amais mezgls nav p\u0113cn\u0101c\u0113ju, tas noz\u012bm\u0113, ka tas ir lapa. T\u0101tad, vienk\u0101r\u0161i varam pie\u0161\u0137irt saviem vec\u0101kiem poliem leftChild vai rightChild v\u0113rt\u012bbu null. <\/p>\n
    Otrais gad\u012bjums. Dz\u0113\u0161amais mezgls ir viens p\u0113cn\u0101c\u0113js.<\/h4>\n
    \n\u0160is gad\u012bjums ar\u012b nav \u013coti sare\u017e\u0123\u012bts. Atgriez\u012bsimies pie m\u016bsu piem\u0113ra. Pie\u0146emsim, ka j\u0101dzen dz\u0113\u0161ams elements ar atsl\u0113gu 14. Piekr\u012btiet, ka t\u0101 k\u0101 tas ir labais p\u0113cn\u0101c\u0113js mezglam ar atsl\u0113gu 10, jebkuram t\u0101 p\u0113cn\u0101c\u0113jam (\u0161aj\u0101 gad\u012bjum\u0101 labajam) b\u016bs atsl\u0113ga, kas ir liel\u0101ka par 10, t\u0101p\u0113c to var viegli \"izgriezt\" no koka, un vec\u0101ku tie\u0161i savienot ar dz\u0113st\u0101 mezgla p\u0113cn\u0101c\u0113ju, t.i., mezglu ar atsl\u0113gu 10 savienot ar mezglu 13. L\u012bdz\u012bga situ\u0101cija b\u016btu, ja jums vajadz\u0113tu dz\u0113st mezglu, kas ir sava vec\u0101ka kreisais p\u0113cn\u0101c\u0113js. P\u0101rdom\u0101jiet to pa\u0161i \u2013 prec\u012bza analo\u0123ija. <\/p>\n
    Tre\u0161ais gad\u012bjums. Mezgls ir divi p\u0113cn\u0101c\u0113ji.<\/h4>\n
    \nVisnopietn\u0101kais gad\u012bjums. Apskat\u012bsim uz jauna piem\u0113ra.<\/p>\n
    \"Binary
    \n<\/p>\n
    Mantojuma mekl\u0113\u0161ana<\/h4>\n
    \n Pie\u0146emsim, ka j\u0101izdz\u0113\u0161 mezgls ar atsl\u0113gu 25. Kadu liksim t\u0101 viet\u0101? K\u0101ds no t\u0101 sekot\u0101jiem (p\u0113cn\u0101c\u0113jiem vai t\u0101 p\u0113cn\u0101c\u0113ju p\u0113cn\u0101c\u0113jiem) j\u0101b\u016bt p\u0113ctecim<\/i>(tas, kur\u0161 aiz\u0146ems izdz\u0113st\u0101 mezgla vietu). <\/p>\n
    K\u0101 saprast, kuram j\u0101b\u016bt p\u0113ctecim? Intuit\u012bvi ir skaidrs, ka tas ir mezgls kok\u0101, kura atsl\u0113ga ir n\u0101kam\u0101 liel\u0101k\u0101 p\u0113c izdz\u0113st\u0101 mezgla. Algoritms ir \u0161\u0101ds. J\u0101iet uz t\u0101 lab\u0101 p\u0113cn\u0101c\u0113ja (vienm\u0113r uz lab\u0101, jo jau tika teikts, ka p\u0113cte\u010da atsl\u0113ga ir liel\u0101ka par izdz\u0113st\u0101 mezgla atsl\u0113gu), un p\u0113c tam j\u0101iet pa kreiso p\u0113cn\u0101c\u0113ju \u0137\u0113di \u0161im labajam p\u0113cn\u0101c\u0113jam. Piem\u0113r\u0101 mums j\u0101p\u0101riet uz mezglu ar atsl\u0113gu 35, un tad j\u0101iet uz leju pa kreiso p\u0113cn\u0101c\u0113ju \u0137\u0113di \u2013 \u0161aj\u0101 gad\u012bjum\u0101 \u0161\u012b \u0137\u0113de sast\u0101v tikai no mezgla ar atsl\u0113gu 30. Strikti run\u0101jot, m\u0113s mekl\u0113jam maz\u0101ko mezglu kop\u0101 mezglu, kas ir liel\u0101ki par mekl\u0113to mezglu.<\/p>\n
    \"Binary
    \n
    \nP\u0113cte\u010da mekl\u0113\u0161anas metodes kods:<\/p>\n
        public Node<T> getSuccessor(Node<T> deleteNode) {\n        Node<T> parentSuccessor = deleteNode; \/\/p\u0113cte\u010da vec\u0101ks\n        Node<T> successor = deleteNode; \/\/p\u0113ctecis\n        Node<T> current = successor.getRightChild(); \/\/vienk\u0101r\u0161i \"p\u0101rvietojamais\" mezgls\n        while (current != null) {\n            parentSuccessor = successor;\n            successor = current;\n            current = current.getLeftChild();\n        }\n        \/\/izn\u0101kot no cikla, ieg\u016bstam p\u0113cte\u010da un p\u0113cte\u010da vec\u0101ku\n        if (successor != deleteNode.getRightChild()) { \/\/ja p\u0113ctecis nesakr\u012bt ar izdz\u0113st\u0101 mezgla labaj\u0101 p\u0113cn\u0101c\u0113j\u0101\n            parentSuccessor.setLeftChild(successor.getRightChild()); \/\/tad t\u0101 vec\u0101ks pa\u0146em sev p\u0113cte\u010da p\u0113cn\u0101c\u0113ju, lai to nezaud\u0113tu\n            successor.setRightChild(deleteNode.getRightChild()); \/\/saist\u0101m p\u0113cte\u010da ar izdz\u0113st\u0101 mezgla labajiem p\u0113cn\u0101c\u0113jiem\n        }\n        return successor;\n    }\n<\/code><\/pre>\n
    \nPiln\u012bgais dz\u0113\u0161anas metodes kods:<\/p>\n
    public boolean delete(int deleteKey) {\n        Node current = root;\n        Node parent = current;\n        boolean isLeftChild = false; \/\/ Atkar\u012bb\u0101 no t\u0101, vai dz\u0113\u0161amais mezgls ir kreisais vai labais b\u0113rns, lo\u0123isk\u0101 main\u012bg\u0101 isLeftChild v\u0113rt\u012bba b\u016bs true vai false attiec\u012bgi.\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) { \/\/ pirmais gad\u012bjums\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) { \/\/ otrais gad\u012bjums\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 { \/\/ tre\u0161ais gad\u012bjums\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
    \nSare\u017e\u0123\u012bt\u012bbu var aproksim\u0113t l\u012bdz O(log(n)).<\/p>\n
    Maksim\u0101l\u0101s\/minim\u0101l\u0101s v\u0113rt\u012bbas mekl\u0113\u0161ana kok\u0101<\/h3>\n
    \nAc\u012bmredzami, k\u0101 atrast minim\u0101lo\/maksim\u0101lo v\u0113rt\u012bbu kok\u0101 \u2014 ir j\u0101dodas sec\u012bgi pa kreisajiem\/labajiem koka elementiem attiec\u012bgi; kad sasniegsiet lapu, t\u0101 b\u016bs minim\u0101l\u0101\/maksim\u0101l\u0101 v\u0113rt\u012bba.<\/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
    \nSare\u017e\u0123\u012bt\u012bba \u2014 O(log(n))<\/p>\n
    Simetriska p\u0101rvieto\u0161an\u0101s<\/h3>\n
    \nP\u0101rvieto\u0161an\u0101s \u2014 katra koka mezgla apmekl\u0113\u0161ana ar m\u0113r\u0137i veikt k\u0101du darb\u012bbu ar to.<\/p>\n
    Rekur\u012bv\u0101s simetrisk\u0101s p\u0101rvieto\u0161an\u0101s algoritms:<\/p>\n
      \n
    1. Veikt darb\u012bbu ar kreiso b\u0113rnu<\/li>\n
    2. Veikt darb\u012bbu ar sevi<\/li>\n
    3. Veikt darb\u012bbu ar labo b\u0113rnu<\/li>\n<\/ol>\n
      \nKods:<\/p>\n
          public void inOrder(Node current) {\n        if (current != null) {\n            inOrder(current.getLeftChild());\n            System.out.println(current.getData() + \" \");\/\/\u0160eit var b\u016bt viss, kas vien v\u0113las\n            inOrder(current.getRightChild());\n        }\n    }\n<\/code><\/pre>\n
      <\/p>\n
      Secin\u0101jums<\/h2>\n
      \nBeidzot! Ja es kaut ko neizskaidroju vai ja ir k\u0101di koment\u0101ri, gaidu tos koment\u0101ros. K\u0101 sol\u012bts, \u0161eit ir pilnais kods.<\/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
      Izsist\u0113\u0161ana l\u012bdz O(n)<\/h3>\n
      \nDaudzi no jums, iesp\u0113jams, ir paman\u012bju\u0161i: ko dar\u012bt, lai koks k\u013c\u016btu nesabalans\u0113ts? Piem\u0113ram, ievietojot kok\u0101 mezglus ar pieaugo\u0161\u0101m atsl\u0113g\u0101m: 1,2,3,4,5,6\u2026 \u0160\u0101d\u0101 gad\u012bjum\u0101 koks nedaudz atg\u0101din\u0101s saist\u012bto sarakstu. Un j\u0101, koks zaud\u0113s savu koka strukt\u016bru, t\u0101p\u0113c ar\u012b datu piek\u013cuves efektivit\u0101ti. Mekl\u0113\u0161anas, ievieto\u0161anas un dz\u0113\u0161anas oper\u0101ciju sare\u017e\u0123\u012bt\u012bba k\u013c\u016bs t\u0101da pati k\u0101 saist\u012btaj\u0101 sarakst\u0101: O(n). Tas ir viens no svar\u012bg\u0101kajiem, manupr\u0101t, bin\u0101ro koku tr\u016bkumiem.<\/p>\n
      Tikai re\u0123istr\u0113tie lietot\u0101ji var piedal\u012bties aptauj\u0101. Pieteikties<\/a><\/noindex>, l\u016bdzu.<\/p>\n
      Es pavisam nesen esmu uz Habr, un v\u0113los uzzin\u0101t, par k\u0101d\u0101m t\u0113m\u0101m j\u016bs v\u0113l\u0113tos redz\u0113t vair\u0101k rakstu?<\/h2>\n
        \n
      • \n
                            Datu strukt\u016bras<\/p>\n<\/li>\n
      • \n
                            Algoritmi (DP, rekursija, datu saspiest\u0161ana utt.)<\/p>\n<\/li>\n
      • \n
                            Datu strukt\u016bru un algoritmu pielietojums re\u0101laj\u0101 dz\u012bv\u0113<\/p>\n<\/li>\n
      • \n
                            Android lietot\u0146u programm\u0113\u0161ana Java valod\u0101<\/p>\n<\/li>\n
      • \n
                            Web lietot\u0146u programm\u0113\u0161ana Java valod\u0101<\/p>\n<\/li>\n<\/ul>\n
            Balsu nodeva 2 lietot\u0101ji. Attur\u0113j\u0101s 1 lietot\u0101js.
        \n
        Avots: 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 jeb k\u0101 pagatavot bin\u0101ro mekl\u0113\u0161anas koku | ProHoster","description":"Priek\u0161v\u0101rds \u0160is raksts ir velt\u012bts bin\u0101rajiem mekl\u0113\u0161anas kokiem.","canonical_url":"https:\/\/prohoster.info\/lv\/blog\/administrirovanie\/binary-tree-ili-kak-prigotovit-binarnoe-derevo-poiska","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"lv_LV","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\/lv\/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\/lv\/wp-json\/wp\/v2\/posts\/30530","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/lv\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/lv\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/lv\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/lv\/wp-json\/wp\/v2\/comments?post=30530"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/lv\/wp-json\/wp\/v2\/posts\/30530\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/lv\/wp-json\/wp\/v2\/media\/22528"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/lv\/wp-json\/wp\/v2\/media?parent=30530"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/lv\/wp-json\/wp\/v2\/categories?post=30530"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/lv\/wp-json\/wp\/v2\/tags?post=30530"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}