{"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\/ro\/blog\/administrirovanie\/binary-tree-ili-kak-prigotovit-binarnoe-derevo-poiska","title":{"rendered":"Binary Tree sau cum s\u0103 prepari un arbore binary de c\u0103utare","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Preludiu<\/h2>\n

\nAcest articol este dedicat arborilor binari de c\u0103utare. Recent am scris un articol despre compresia datelor prin metoda Huffman.<\/a><\/noindex> Acolo nu am acordat prea mult\u0103 aten\u021bie arborilor binari, deoarece metodele de c\u0103utare, inserare \u0219i \u0219tergere nu erau relevante. Acum am decis s\u0103 scriu un articol tocmai despre arbori. Probabil c\u0103 s\u0103 \u00eencepem. <\/p>\n

Un arbore este o structur\u0103 de date format\u0103 din noduri conectate prin muchii. Se poate spune c\u0103 un arbore este un caz particular de graf. Iat\u0103 un exemplu de arbore: <\/p>\n

\"Binary
\n
\nAcesta nu este un arbore binar de c\u0103utare! Totul este sub cat!
\n<\/a><\/noindex><\/p>\n

Terminologie<\/h2>\n

<\/p>\n

R\u0103d\u0103cin\u0103<\/h4>\n

\nR\u0103d\u0103cina arborului<\/i> este cel mai de sus nod. \u00cen exemplu, acesta este nodul A. \u00cen arbore, de la r\u0103d\u0103cin\u0103 la orice alt nod poate duce doar un singur drum! De fapt, orice nod poate fi considerat ca r\u0103d\u0103cina subarborelui corespunz\u0103tor acestui nod.<\/p>\n

P\u0103rin\u021bi \/ descenden\u021bi<\/h4>\n

\nToate nodurile, cu excep\u021bia r\u0103d\u0103cinii, au exact o muchie care duce \u00een sus c\u0103tre un alt nod. Nodul situat deasupra nodului curent se nume\u0219te p\u0103rinte<\/i> al acestui nod. Nodul situat sub nodul curent, care este conectat cu acesta, se nume\u0219te descendent<\/i> al acestui nod. S\u0103 lu\u0103m un exemplu. S\u0103 lu\u0103m nodul B, astfel \u00eenc\u00e2t p\u0103rintele s\u0103u va fi nodul A, iar descenden\u021bii s\u0103i vor fi nodurile D, E \u0219i F.<\/p>\n

Foaie<\/h4>\n

\nUn nod care nu are descenden\u021bi se va numi frunz\u0103 a arborului. \u00cen exemplu, frunzele vor fi nodurile D, E, F, G, I, J, K.<\/p>\n

Aceasta este terminologia de baz\u0103. Alte concepte vor fi discutate mai departe. A\u0219adar, un arbore binar este un arbore \u00een care fiecare nod va avea cel mult doi descenden\u021bi. A\u0219a cum a\u021bi ghicit, arborele din exemplu nu va fi binar, deoarece nodurile B \u0219i H au mai mult de doi descenden\u021bi. Iat\u0103 un exemplu de arbore binar:<\/p>\n

\"Binary
\n
\n\u00cen nodurile arborului poate fi orice informa\u021bie. Arborele binar de c\u0103utare este un arbore binar, pentru care caracteristicile urm\u0103toare sunt caracteristice:<\/p>\n

    \n
  1. Ambele subarbori - st\u00e2ng \u0219i drept - sunt arbori binari de c\u0103utare.<\/li>\n
  2. La toate nodurile subarborelui st\u00e2ng al oric\u0103rui nod X, valorile cheilor de date sunt mai mici dec\u00e2t valoarea cheii de date a nodului X.<\/li>\n
  3. La toate nodurile subarborelui drept al oric\u0103rui nod X, valorile cheilor de date sunt mai mari sau egale cu valoarea cheii de date a nodului X. <\/li>\n<\/ol>\n

    Cheia<\/i> \u2014 orice caracteristic\u0103 a nodului (de exemplu, un num\u0103r). Cheia este necesar\u0103 pentru a putea g\u0103si elementul arborelui c\u0103ruia \u00eei corespunde aceast\u0103 cheie. Exemplu de arbore binar de c\u0103utare:<\/p>\n

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

    Reprezentarea arborului<\/h2>\n

    \nPe m\u0103sur\u0103 ce avans\u0103m, voi prezenta c\u00e2teva (posibil incomplete) fragmente de cod pentru a \u00eembun\u0103t\u0103\u021bi \u00een\u021belegerea dvs. Codul complet va fi la finalul articolului. <\/p>\n

    Arborele este alc\u0103tuit din noduri. Structura unui nod:<\/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\/\/...alte metode ale nodului\n}\n<\/code><\/pre>\n
    \nFiecare nod are doi fii (este posibil ca fiii leftChild \u0219i\/sau rightChild s\u0103 con\u021bin\u0103 valoarea null). Probabil a\u021bi \u00een\u021beles c\u0103 \u00een acest caz num\u0103rul data reprezint\u0103 datele stocate \u00een nod; key este cheia nodului.<\/p>\n
    Am rezolvat nodul, acum s\u0103 discut\u0103m despre problemele actuale ale arborilor. Aici \u0219i mai departe, prin \"arbore\" voi \u00een\u021belege conceptul de arbore binar de c\u0103utare. Structura unui arbore binar:<\/p>\n
    public class BinaryTree<T> {\n     private Node<T> root;\n\n    \/\/metodele arborelui\n}\n<\/code><\/pre>\n
    Ca \u0219i c\u00e2mp al clasei, ne va trebui doar r\u0103d\u0103cina arborelui, deoarece de la r\u0103d\u0103cin\u0103, folosind metodele getLeftChild() \u0219i getRightChild(), se poate ajunge la orice nod din arbore.<\/p>\n
    Algoritmi \u00een arbore<\/h2>\n
    <\/p>\n
    C\u0103utarea<\/h3>\n
    \nS\u0103 presupunem c\u0103 ave\u021bi un arbore construit. Cum g\u0103si\u021bi un element cu cheia key? Trebuie s\u0103 v\u0103 deplasa\u021bi pe r\u00e2nd de la r\u0103d\u0103cin\u0103 \u00een josul arborelui \u0219i s\u0103 compara\u021bi valoarea key cu cheia nodului curent: dac\u0103 key este mai mic dec\u00e2t cheia nodului curent, trece\u021bi la fiul st\u00e2ng al nodului; dac\u0103 este mai mare - la fiul drept; dac\u0103 cheile sunt egale - nodul c\u0103utat a fost g\u0103sit! Codul corespunz\u0103tor:<\/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
    \nDac\u0103 current devine egal cu null, \u00eenseamn\u0103 c\u0103 c\u0103utarea a atins finalul arborelui (la nivel conceptual, v\u0103 afla\u021bi \u00eentr-un loc inexistent al arborelui - un fiu al unei frunze).<\/p>\n
    S\u0103 examin\u0103m eficien\u021ba algoritmului de c\u0103utare pe un arbore echilibrat (un arbore \u00een care nodurile sunt distribuite mai mult sau mai pu\u021bin uniform). Atunci eficien\u021ba c\u0103ut\u0103rii va fi O(log(n)), cu logaritm la baza 2. Observa\u021bi: dac\u0103 \u00een arborele echilibrat sunt n elemente, \u00eenseamn\u0103 c\u0103 vor fi log(n) la baza 2 niveluri ale arborelui. Iar \u00een timpul c\u0103ut\u0103rii, cu un pas al buclei, cobor\u00e2\u021bi un nivel.<\/p>\n
    Inserare<\/h3>\n
    \nDac\u0103 a\u021bi \u00een\u021beles esen\u021ba c\u0103ut\u0103rii, atunci nu va fi greu s\u0103 \u00een\u021belege\u021bi inser\u021bia. Trebuie s\u0103 cobor\u00e2\u021bi p\u00e2n\u0103 la frunza arborelui (conform regulilor de cobor\u00e2re descrise \u00een c\u0103utare) \u0219i s\u0103 deveni\u021bi descendentul s\u0103u \u2014 st\u00e2ng, sau drept, \u00een func\u021bie de cheie. Implementare:<\/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\u00cen acest caz, trebuie s\u0103 p\u0103str\u0103m informa\u021bia despre p\u0103rintele nodului curent, pe l\u00e2ng\u0103 nodul curent. C\u00e2nd current devine egal cu null, variabila parent va con\u021bine frunza de care avem nevoie. 
    \nEficien\u021ba inser\u021biei va fi, evident, aceea\u0219i ca \u0219i la c\u0103utare \u2014 O(log(n)).<\/p>\n
    \u0218tergere<\/h3>\n
    \n\u0218tergerea este cea mai complex\u0103 opera\u021bie care trebuie efectuat\u0103 cu arborele. Este clar c\u0103 mai \u00eent\u00e2i trebuie s\u0103 g\u0103sim elementul pe care dorim s\u0103-l \u0219tergem. Dar ce urmeaz\u0103? Dac\u0103 pur \u0219i simplu atribuim valoarea null leg\u0103turii sale, vom pierde informa\u021bia despre subarborele av\u00e2nd acest nod ca r\u0103d\u0103cin\u0103. Metodele de \u0219tergere a arborilor se \u00eempart \u00een trei cazuri.<\/p>\n
    Primul caz. Nodul \u0219ters nu are descenden\u021bi.<\/h4>\n
    \nDac\u0103 nodul \u0219ters nu are descenden\u021bi, atunci \u00eenseamn\u0103 c\u0103 este o frunz\u0103. Prin urmare, putem pur \u0219i simplu s\u0103 atribuim valorile null c\u00e2mpurilor leftChild sau rightChild ale p\u0103rintelui s\u0103u. <\/p>\n
    Al doilea caz. Nodul \u0219ters are un descendent.<\/h4>\n
    \nAcest caz nu este foarte complicat. S\u0103 ne \u00eentoarcem la exemplul nostru. S\u0103 presupunem c\u0103 dorim s\u0103 \u0219tergem elementul cu cheia 14. S\u0103 admit\u0103m c\u0103, fiind un descendent drept al nodului cu cheia 10, orice descendent al s\u0103u (\u00een acest caz, dreptul) va avea o cheie mai mare de 10, a\u0219a c\u0103 putem s\u0103-l \u201et\u0103iem\u201d cu u\u0219urin\u021b\u0103 din arbore, iar p\u0103rintele s\u0103u va fi conectat direct la descendentul nodului \u0219ters, adic\u0103 nodul cu cheia 10 va fi conectat la nodul 13. O situa\u021bie similar\u0103 ar fi dac\u0103 dorim s\u0103 \u0219tergem un nod care este descendent st\u00e2ng al p\u0103rintelui s\u0103u. G\u00e2ndi\u021bi-v\u0103 la asta zilnic \u2014 o analogie exact\u0103. <\/p>\n
    Al treilea caz. Nodul are doi descenden\u021bi.<\/h4>\n
    \nCazul cel mai complex. S\u0103-l analiz\u0103m pe un exemplu nou.<\/p>\n
    \"Binary
    \n<\/p>\n
    C\u0103utarea succesorului.<\/h4>\n
    \n S\u0103 presupunem c\u0103 trebuie s\u0103 elimin\u0103m un nod cu cheia 25. Pe cine vom pune \u00een locul s\u0103u? Cineva dintre urma\u0219ii s\u0103i (descenden\u021bi sau descenden\u021bi ai descenden\u021bilor) ar trebui s\u0103 devin\u0103 succesorul<\/i>(cel care va ocupa locul nodului eliminat). <\/p>\n
    Cum putem \u00een\u021belege cine ar trebui s\u0103 devin\u0103 succesor? Este evident c\u0103 acesta este un nod din arbore, ale c\u0103rui cheie este urm\u0103toarea ca m\u0103rime fa\u021b\u0103 de nodul eliminat. Algoritmul este urm\u0103torul. Trebuie s\u0103 ne deplas\u0103m la descendentul s\u0103u din dreapta (\u00eentotdeauna la dreapta, deoarece s-a spus deja c\u0103 cheia succesorului este mai mare dec\u00e2t cheia nodului eliminat) \u0219i apoi s\u0103 parcurgem lan\u021bul descenden\u021bilor din st\u00e2nga acestui descendent din dreapta. \u00cen exemplul nostru, trebuie s\u0103 ne deplas\u0103m la nodul cu cheia 35 \u0219i apoi s\u0103 cobor\u00e2m la frunz\u0103 de-a lungul lan\u021bului descenden\u021bilor s\u0103i din st\u00e2nga \u2014 \u00een acest caz, acest lan\u021b este format doar din nodul cu cheia 30. Strict vorbind, c\u0103ut\u0103m cel mai mic nod din setul nodurilor mai mari dec\u00e2t nodul c\u0103utat.<\/p>\n
    \"Binary
    \n
    \nCodul metodei de c\u0103utare a succesorului:<\/p>\n
        public Node<T> getSuccessor(Node<T> deleteNode) {\n        Node<T> parentSuccessor = deleteNode; \/\/ p\u0103rintele succesorului\n        Node<T> successor = deleteNode; \/\/ succesorul\n        Node<T> current = successor.getRightChild(); \/\/ nodul \u201ede parcurs\u201d\n        while (current != null) {\n            parentSuccessor = successor;\n            successor = current;\n            current = current.getLeftChild();\n        }\n        \/\/ la ie\u0219irea din ciclu avem succesorul \u0219i p\u0103rintele succesorului\n        if (successor != deleteNode.getRightChild()) { \/\/ dac\u0103 succesorul nu este identic cu descendentul din dreapta al nodului eliminat\n            parentSuccessor.setLeftChild(successor.getRightChild()); \/\/ p\u0103rintele s\u0103u \u00ee\u0219i ia descendentul succesorului, pentru a nu-l pierde\n            successor.setRightChild(deleteNode.getRightChild()); \/\/ leg\u0103m succesorul de descendentul din dreapta al nodului eliminat\n        }\n        return successor;\n    }\n<\/code><\/pre>\n
    \nCodul complet al metodei delete:<\/p>\n
    public boolean delete(int deleteKey) {\n        Node current = root;\n        Node parent = current;\n        boolean isLeftChild = false; \/\/ \u00cen func\u021bie de faptul dac\u0103 nodul care trebuie eliminat este copil st\u00e2ng sau drept al p\u0103rintelui s\u0103u, variabila boolean\u0103 isLeftChild va avea valoarea true sau false, respectiv.\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) { \/\/ primul caz\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) { \/\/ al doilea caz\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 { \/\/ al treilea caz\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
    \nComplexitatea poate fi aproximat\u0103 la O(log(n)).<\/p>\n
    C\u0103utarea maximului\/minimului \u00eentr-un arbore<\/h3>\n
    \nEste evident cum s\u0103 g\u0103sim valoarea minim\u0103\/maximum \u00een arbore \u2014 trebuie s\u0103 trecem succesiv prin lan\u021bul de elemente st\u00e2ngi\/drepte al arborelui, respectiv; c\u00e2nd ajunge\u021bi la o frunz\u0103, aceasta va fi elementul minim\/maxim.<\/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
    \nComplexitatea \u2014 O(log(n))<\/p>\n
    Parcurgere simetric\u0103<\/h3>\n
    \nParcurgerea \u2014 vizitarea fiec\u0103rui nod al arborelui cu scopul de a face o ac\u021biune asupra acestuia.<\/p>\n
    Algoritmul de parcurgere simetric\u0103 recursiv\u0103:<\/p>\n
      \n
    1. Face\u021bi o ac\u021biune cu copilul st\u00e2ng<\/li>\n
    2. Face\u021bi o ac\u021biune cu sine \u00eensu\u0219i<\/li>\n
    3. Face\u021bi o ac\u021biune cu copilul drept<\/li>\n<\/ol>\n
      \nCod:<\/p>\n
          public void inOrder(Node current) {\n        if (current != null) {\n            inOrder(current.getLeftChild());\n            System.out.println(current.getData() + \" \");\/\/Aici poate fi orice\n            inOrder(current.getRightChild());\n        }\n    }\n<\/code><\/pre>\n
      <\/p>\n
      Concluzie<\/h2>\n
      \n\u00cen sf\u00e2r\u0219it! Dac\u0103 am omis ceva sau ave\u021bi sugestii, v\u0103 a\u0219tept \u00een comentarii. A\u0219a cum am promis, iat\u0103 codul complet.<\/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
      Degenerare la O(n)<\/h3>\n
      \nMul\u021bi dintre voi a\u021bi observat: dar ce ar fi dac\u0103 am face ca arborele s\u0103 devin\u0103 dezechilibrat? De exemplu, s\u0103 ad\u0103ug\u0103m \u00een arbore noduri cu chei \u00een cre\u0219tere: 1,2,3,4,5,6\u2026 Atunci, arborele va sem\u0103na cu o list\u0103 legat\u0103. \u0218i da, arborele \u00ee\u0219i va pierde structura ramificat\u0103, iar, prin urmare, eficien\u021ba accesului la date. Complexitatea opera\u021biunilor de c\u0103utare, inserare \u0219i \u0219tergere va deveni similar\u0103 cu cea a unei liste legate: O(n). Aici se manifest\u0103, din punctul meu de vedere, unul dintre cele mai importante dezavantaje ale arborilor binari.<\/p>\n
      Numai utilizatorii \u00eenregistra\u021bi pot participa la sondaj. Conecta\u021bi-v\u0103<\/a><\/noindex>, v\u0103 rug\u0103m.<\/p>\n
      Nu sunt aici de foarte mult timp pe Haber \u0219i mi-ar pl\u0103cea s\u0103 \u0219tiu despre ce subiecte a\u021bi dori s\u0103 vede\u021bi mai multe articole?<\/h2>\n
        \n
      • \n
                            Structuri de date<\/p>\n<\/li>\n
      • \n
                            Algoritmi (DP, recursivitate, compresia datelor etc.)<\/p>\n<\/li>\n
      • \n
                            Aplicarea structurilor de date \u0219i algoritmilor \u00een via\u021ba real\u0103<\/p>\n<\/li>\n
      • \n
                            Programarea aplica\u021biilor Android \u00een Java<\/p>\n<\/li>\n
      • \n
                            Programarea aplica\u021biilor web \u00een Java<\/p>\n<\/li>\n<\/ul>\n
            2 utilizatori au votat. 1 utilizator s-a ab\u021binut.
        \n
        Surs\u0103: 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\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\udd47Arbore Binari sau cum s\u0103 prepari un arbore binar de c\u0103utare | ProHoster","description":"Preludiu Aceast\u0103 articol este dedicat arborilor binari de c\u0103utare.","canonical_url":"https:\/\/prohoster.info\/ro\/blog\/administrirovanie\/binary-tree-ili-kak-prigotovit-binarnoe-derevo-poiska","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"ro_RO","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\/ro\/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\/ro\/wp-json\/wp\/v2\/posts\/30530","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/comments?post=30530"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/posts\/30530\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/media\/22528"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/media?parent=30530"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/categories?post=30530"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/tags?post=30530"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}