{"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\/sv\/blog\/administrirovanie\/binary-tree-ili-kak-prigotovit-binarnoe-derevo-poiska","title":{"rendered":"Bin\u00e4rt Tr\u00e4d eller hur man skapar ett bin\u00e4rt s\u00f6ktr\u00e4d","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Inledningen<\/h2>\n

\nDen h\u00e4r artikeln handlar om bin\u00e4ra s\u00f6ktr\u00e4d. Nyligen skrev jag en artikel om data komprimering med Huffman-metoden.<\/a><\/noindex> D\u00e4r lade jag inte mycket vikt vid bin\u00e4ra tr\u00e4d, eftersom metoder f\u00f6r s\u00f6kning, ins\u00e4ttning och borttagning inte var aktuella. Nu har jag best\u00e4mt mig f\u00f6r att skriva en artikel just om tr\u00e4d. L\u00e5t oss b\u00f6rja. <\/p>\n

Ett tr\u00e4d \u00e4r en datstruktur som best\u00e5r av noder kopplade med kanter. Man kan s\u00e4ga att ett tr\u00e4d \u00e4r ett specialfall av en graf. H\u00e4r \u00e4r ett exempel p\u00e5 ett tr\u00e4d: <\/p>\n

\"Bin\u00e4rt
\n
\nDetta \u00e4r inte ett bin\u00e4rt s\u00f6ktr\u00e4d! Allt under kat!
\n<\/a><\/noindex><\/p>\n

Terminologi<\/h2>\n

<\/p>\n

Rot<\/h4>\n

\nRoten av ett tr\u00e4d<\/i> \u00e4r dess \u00f6versta nod. I exemplet \u00e4r detta nod A. I tr\u00e4det finns det endast en v\u00e4g fr\u00e5n roten till vilken annan nod som helst! I sj\u00e4lva verket kan varje nod ses som roten av det undertr\u00e4d som motsvarar denna nod.<\/p>\n

F\u00f6r\u00e4ldrar\/avkommor<\/h4>\n

\nAlla noder, f\u00f6rutom roten, har exakt en kant som leder upp\u00e5t till en annan nod. Noden som ligger \u00f6ver den aktuella noden kallas f\u00f6r\u00e4lder<\/i> till denna nod. Noden som ligger under den aktuella noden och \u00e4r kopplad till den kallas avkomma<\/i> till denna nod. L\u00e5t oss ta ett exempel. Vi tar nod B, d\u00e5 blir dess f\u00f6r\u00e4lder nod A, och dess avkommor blir noderna D, E och F.<\/p>\n

Blad<\/h4>\n

\nEn nod som inte har n\u00e5gra avkommor kallas ett blad av tr\u00e4det. I exemplet \u00e4r noderna D, E, F, G, I, J, K blad.<\/p>\n

Detta \u00e4r den grundl\u00e4ggande terminologin. Andra begrepp kommer att diskuteras senare. S\u00e5, ett bin\u00e4rt tr\u00e4d \u00e4r ett tr\u00e4d d\u00e4r varje nod har h\u00f6gst tv\u00e5 avkommor. Som ni gissat kommer tr\u00e4det i exemplet inte att vara bin\u00e4rt, eftersom noderna B och H har mer \u00e4n tv\u00e5 avkommor. H\u00e4r \u00e4r ett exempel p\u00e5 ett bin\u00e4rt tr\u00e4d:<\/p>\n

\"Bin\u00e4rt
\n
\nI noderna av tr\u00e4det kan vilken information som helst finnas. Ett bin\u00e4rt s\u00f6ktr\u00e4d \u00e4r ett bin\u00e4rt tr\u00e4d som k\u00e4nnetecknas av f\u00f6ljande egenskaper:<\/p>\n

    \n
  1. B\u00e5da undertr\u00e4den \u2013 v\u00e4nster och h\u00f6ger \u2013 \u00e4r bin\u00e4ra s\u00f6ktr\u00e4d.<\/li>\n
  2. I alla noder i det v\u00e4nstra undertr\u00e4det till en godtycklig nod X \u00e4r datanycklarna mindre \u00e4n v\u00e4rdet p\u00e5 datanyckeln hos nod X.<\/li>\n
  3. I alla noder i det h\u00f6gra undertr\u00e4det till en godtycklig nod X \u00e4r datanycklarna st\u00f6rre eller lika med v\u00e4rdet p\u00e5 datanyckeln hos nod X. <\/li>\n<\/ol>\n

    Nyckeln<\/i> \u2013 en egenskap hos noden (till exempel ett nummer). Nyckeln beh\u00f6vs f\u00f6r att man ska kunna hitta elementet i tr\u00e4det som motsvarar denna nyckel. Exempel p\u00e5 ett bin\u00e4rt s\u00f6ktr\u00e4d:<\/p>\n

    \"Bin\u00e4rt
    \n<\/p>\n

    Tr\u00e4dets representation<\/h2>\n

    \nAllteftersom vi g\u00e5r fram\u00e5t kommer jag att ge vissa (kanske ofullst\u00e4ndiga) kodstycken f\u00f6r att f\u00f6rb\u00e4ttra din f\u00f6rst\u00e5else. Den fullst\u00e4ndiga koden kommer att finnas i slutet av artikeln. <\/p>\n

    Tr\u00e4det best\u00e5r av noder. Struktur f\u00f6r en 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\/\/...\u00f6vriga metoder f\u00f6r noden\n}\n<\/code><\/pre>\n
    \nVarje nod har tv\u00e5 barn (det \u00e4r m\u00f6jligt att barnen leftChild och\/eller rightChild kommer att ha v\u00e4rdet null). Du har nog f\u00f6rst\u00e5tt att i detta fall \u00e4r data \u2014 de uppgifter som lagras i noden; key \u2014 nodens nyckel.<\/p>\n
    Nu har vi g\u00e5tt igenom noder, s\u00e5 l\u00e5t oss prata om aktuella problem relaterade till tr\u00e4d. H\u00e4r och fram\u00e5t kommer jag att anv\u00e4nda termen \"tr\u00e4d\" f\u00f6r att referera till konceptet av ett bin\u00e4rt s\u00f6ktr\u00e4d. Strukturen f\u00f6r ett bin\u00e4rt tr\u00e4d:<\/p>\n
    public class BinaryTree<T> {\n     private Node<T> root;\n\n    \/\/metoder f\u00f6r tr\u00e4det\n}\n<\/code><\/pre>\n
    Som klassf\u00e4lt beh\u00f6ver vi endast roten av tr\u00e4det, eftersom vi fr\u00e5n roten med metoderna getLeftChild() och getRightChild() kan n\u00e5 vilken nod som helst i tr\u00e4det.<\/p>\n
    Algoritmer i tr\u00e4det<\/h2>\n
    <\/p>\n
    S\u00f6kandet<\/h3>\n
    \nAnta att du har ett byggt tr\u00e4d. Hur hittar man elementet med nyckeln key? Du m\u00e5ste systematiskt r\u00f6ra dig ned\u00e5t fr\u00e5n roten genom tr\u00e4det och j\u00e4mf\u00f6ra v\u00e4rdet av key med nyckeln av aktuell nod: om key \u00e4r mindre \u00e4n nyckeln f\u00f6r den aktuella noden, g\u00e5 till v\u00e4nstra barnet av noden, om st\u00f6rre \u2014 till h\u00f6gra, om nycklarna \u00e4r lika \u2014 den s\u00f6kta noden \u00e4r funnen! Den relevanta koden:<\/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
    \nOm current blir lika med null, betyder det att s\u00f6kningen har n\u00e5tt slutet av tr\u00e4det (p\u00e5 konceptuell niv\u00e5 befinner du dig p\u00e5 en icke-existerande plats i tr\u00e4det \u2014 barnet av ett blad).<\/p>\n
    L\u00e5t oss granska effektiviteten av s\u00f6kalgoritmen p\u00e5 ett balanserat tr\u00e4d (ett tr\u00e4d d\u00e4r noderna \u00e4r distribuera mer eller mindre j\u00e4mnt). Vidare kommer effektiviteten i s\u00f6kningen att vara O(log(n)), d\u00e4r logaritmen \u00e4r bas 2. Se: om det finns n element i det balanserade tr\u00e4det, inneb\u00e4r det att det kommer att finnas log(n) niv\u00e5er i tr\u00e4det. Och i s\u00f6kningen, i ett steg av cykeln, g\u00e5r du ner en niv\u00e5.<\/p>\n
    Infoga<\/h3>\n
    \nOm du har f\u00f6rst\u00e5tt k\u00e4rnan i s\u00f6kningen, kommer det inte att vara sv\u00e5rt f\u00f6r dig att f\u00f6rst\u00e5 ins\u00e4ttningen. Du beh\u00f6ver bara g\u00e5 ner till bladet av tr\u00e4det (enligt nedstigningsreglerna som beskrivs i s\u00f6kningen) och bli dess avkomma \u2014 v\u00e4nster eller h\u00f6ger, beroende p\u00e5 nyckeln. Implementering:<\/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
    \nI det h\u00e4r fallet beh\u00f6ver vi f\u00f6rutom den aktuella noden lagra information om f\u00f6r\u00e4ldern till den aktuella noden. N\u00e4r current blir null kommer variabeln parent att inneh\u00e5lla det blad vi beh\u00f6ver. 
    \nEffektiviteten f\u00f6r ins\u00e4ttning kommer uppenbarligen att vara densamma som f\u00f6r s\u00f6kningen \u2014 O(log(n)).<\/p>\n
    Ta bort<\/h3>\n
    \nBorttagning \u00e4r den mest komplicerade operationen som m\u00e5ste utf\u00f6ras med tr\u00e4det. Det \u00e4r uppenbart att vi f\u00f6rst m\u00e5ste hitta det element som vi planerar att ta bort. Men vad h\u00e4nder sedan? Om vi bara tilldelar dess referens v\u00e4rdet null, kommer vi att f\u00f6rlora information om deltr\u00e4det vars rot \u00e4r denna nod. Borttagningstekniker delas in i tre fall.<\/p>\n
    F\u00f6rsta fallet. Den borttagna noden har inga avkommor<\/h4>\n
    \nOm den borttagna noden inte har n\u00e5gra avkommor betyder det att den \u00e4r ett blad. D\u00e4rf\u00f6r kan vi helt enkelt tilldela leftChild eller rightChild i dess f\u00f6r\u00e4lder v\u00e4rdet null. <\/p>\n
    Andra fallet. Den borttagna noden har en avkomma<\/h4>\n
    \nDetta fall \u00e4r inte heller s\u00e4rskilt sv\u00e5rt. L\u00e5t oss \u00e5terv\u00e4nda till v\u00e5rt exempel. Anta att vi m\u00e5ste ta bort elementet med nyckeln 14. H\u00e5ll med om att eftersom den \u00e4r en h\u00f6ger avkomma till noden med nyckeln 10, kommer vilken avkomma som helst (i det h\u00e4r fallet h\u00f6ger) att ha en nyckel som \u00e4r st\u00f6rre \u00e4n 10, s\u00e5 vi kan enkelt \u201dklippa ut\u201d den fr\u00e5n tr\u00e4det och direkt f\u00f6rknippa f\u00f6r\u00e4ldern med avkomman till den borttagna noden, dvs. noden med nyckeln 10 kopplas till noden 13. En liknande situation skulle vara om vi beh\u00f6vde ta bort en nod som \u00e4r en v\u00e4nster avkomma till sin f\u00f6r\u00e4lder. T\u00e4nk p\u00e5 detta sj\u00e4lv \u2014 exakt analogi. <\/p>\n
    Tredje fallet. Noden har tv\u00e5 avkommor<\/h4>\n
    \nDet mest komplicerade fallet. Vi analyserar det med ett nytt exempel.<\/p>\n
    \"Bin\u00e4rt
    \n<\/p>\n
    S\u00f6kning av eftertr\u00e4dare<\/h4>\n
    \n Anta att vi beh\u00f6ver ta bort noden med nyckeln 25. Vem s\u00e4tter vi i dess st\u00e4lle? N\u00e5gon av dess efterf\u00f6ljare (avkommor eller avkommor till avkommor) m\u00e5ste bli eftertr\u00e4dare<\/i>(den som ska ta platsen f\u00f6r den borttagna noden). <\/p>\n
    Hur f\u00f6rst\u00e5r vi vem som ska bli eftertr\u00e4dare? Det \u00e4r intuitivt klart att det \u00e4r noden i tr\u00e4det vars nyckel \u00e4r den n\u00e4sta st\u00f6rsta efter den borttagna noden. Algoritmen inneb\u00e4r f\u00f6ljande. Vi m\u00e5ste g\u00e5 till dess h\u00f6gra avkomma (alltid till h\u00f6ger, eftersom det redan har sagts att nyckeln f\u00f6r eftertr\u00e4daren \u00e4r st\u00f6rre \u00e4n nyckeln f\u00f6r den borttagna noden), och sedan g\u00e5 ner genom kedjan av v\u00e4nstra avkommor till denna h\u00f6gra avkomma. I exemplet m\u00e5ste vi g\u00e5 till noden med nyckeln 35 och sedan g\u00e5 ner till bladet genom kedjan av dess v\u00e4nstra avkommor - i detta fall best\u00e5r denna kedja endast av noden med nyckel 30. Strikt talat letar vi efter den minsta noden i upps\u00e4ttningen av noder som \u00e4r st\u00f6rre \u00e4n den s\u00f6kta noden.<\/p>\n
    \"Bin\u00e4rt
    \n
    \nKod f\u00f6r metoden f\u00f6r att hitta eftertr\u00e4daren:<\/p>\n
        public Node<T> getSuccessor(Node<T> deleteNode) {\n        Node<T> parentSuccessor = deleteNode; \/\/ f\u00f6r\u00e4lder till eftertr\u00e4daren\n        Node<T> successor = deleteNode; \/\/ eftertr\u00e4dare\n        Node<T> current = successor.getRightChild(); \/\/ bara en \"genomg\u00e5ende\" nod\n        while (current != null) {\n            parentSuccessor = successor;\n            successor = current;\n            current = current.getLeftChild();\n        }\n        \/\/ vid utg\u00e5ngen av loopen har vi eftertr\u00e4daren och f\u00f6r\u00e4ldern till eftertr\u00e4daren\n        if (successor != deleteNode.getRightChild()) { \/\/ om eftertr\u00e4daren inte \u00e4r densamma som den h\u00f6gra avkomman till den borttagna noden\n            parentSuccessor.setLeftChild(successor.getRightChild()); \/\/ tar f\u00f6r\u00e4ldern \u00f6ver eftertr\u00e4darens avkomma f\u00f6r att inte f\u00f6rlora den\n            successor.setRightChild(deleteNode.getRightChild()); \/\/ kopplar eftertr\u00e4daren till den borttagna nodens h\u00f6gra avkomma\n        }\n        return successor;\n    }\n<\/code><\/pre>\n
    \nDen fullst\u00e4ndiga koden f\u00f6r metoden delete:<\/p>\n
    public boolean delete(int deleteKey) {\n        Node current = root;\n        Node parent = current;\n        boolean isLeftChild = false; \/\/ Beroende p\u00e5 om den borttagna noden \u00e4r ett v\u00e4nster- eller h\u00f6gra barn till sin f\u00f6r\u00e4lder, kommer den booleska variabeln isLeftChild att ta v\u00e4rdet true eller 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) { \/\/ f\u00f6rsta fallet\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) { \/\/ andra fallet\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 { \/\/ tredje fallet\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
    \nTidskomplexiteten kan approximativt anges till O(log(n)).<\/p>\n
    S\u00f6kning av maximum\/minimum i tr\u00e4det<\/h3>\n
    \nDet \u00e4r uppenbart hur man hittar det minimi\/maksimala v\u00e4rdet i tr\u00e4det \u2014 man m\u00e5ste sekventiellt g\u00e5 l\u00e4ngs kedjan av v\u00e4nster\/h\u00f6ger element i tr\u00e4det; n\u00e4r man n\u00e5r ett blad, \u00e4r det minimala\/maximala elementet.<\/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
    \nTidskomplexiteten \u00e4r O(log(n))<\/p>\n
    Symmetrisk genomg\u00e5ng<\/h3>\n
    \nGenomg\u00e5ng \u2014 att bes\u00f6ka varje nod i tr\u00e4det f\u00f6r att utf\u00f6ra en \u00e5tg\u00e4rd med den.<\/p>\n
    Algoritm f\u00f6r rekursiv symmetrisk genomg\u00e5ng:<\/p>\n
      \n
    1. Utf\u00f6r \u00e5tg\u00e4rd med v\u00e4nster barn<\/li>\n
    2. Utf\u00f6r \u00e5tg\u00e4rd med sig sj\u00e4lv<\/li>\n
    3. Utf\u00f6r \u00e5tg\u00e4rd med h\u00f6gra barn<\/li>\n<\/ol>\n
      \nKod:<\/p>\n
          public void inOrder(Node current) {\n        if (current != null) {\n            inOrder(current.getLeftChild());\n            System.out.println(current.getData() + \" \");\/\/ H\u00e4r kan det vara vad som helst\n            inOrder(current.getRightChild());\n        }\n    }\n<\/code><\/pre>\n
      <\/p>\n
      Slutsats<\/h2>\n
      \n\u00c4ntligen! Om jag har f\u00f6rklarat n\u00e5got f\u00f6r lite eller om det finns n\u00e5gra kommentarer, ser jag fram emot dem i kommentarerna. Som utlovat, h\u00e4r \u00e4r hela koden.<\/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
      F\u00f6rfalla till O(n)<\/h3>\n
      \nM\u00e5nga av er kanske har m\u00e4rkt: vad h\u00e4nder om vi g\u00f6r s\u00e5 att tr\u00e4det blir obalanserat? Till exempel genom att l\u00e4gga in noder med \u00f6kande nycklar: 1,2,3,4,5,6\u2026 D\u00e5 kommer tr\u00e4det att p\u00e5minna om en l\u00e4nkad lista. Och ja, tr\u00e4det kommer att f\u00f6rlora sin tr\u00e4struktur, vilket i sin tur p\u00e5verkar effektiviteten vid datatillg\u00e5ng. Tidskomplexiteten f\u00f6r operationer som s\u00f6kning, ins\u00e4ttning och borttagning kommer att bli som f\u00f6r en l\u00e4nkad lista: O(n). Det h\u00e4r \u00e4r en av de viktigaste, enligt min \u00e5sikt, nackdelarna med bin\u00e4ra tr\u00e4d.<\/p>\n
      Endast registrerade anv\u00e4ndare kan delta i omr\u00f6stningen. Logga in<\/a><\/noindex>, tack.<\/p>\n
      Jag \u00e4r inte s\u00e5 l\u00e4nge p\u00e5 Habr\u00e9, och jag skulle vilja veta vilka \u00e4mnen ni skulle vilja se fler artiklar om?<\/h2>\n
        \n
      • \n
                            Datastrukturer<\/p>\n<\/li>\n
      • \n
                            Algoritmer (DP, rekursion, datakompression osv.)<\/p>\n<\/li>\n
      • \n
                            Till\u00e4mpning av datastrukturer och algoritmer i verkliga livet<\/p>\n<\/li>\n
      • \n
                            Programmering av android-appar i Java<\/p>\n<\/li>\n
      • \n
                            Programmering av web-appar i Java<\/p>\n<\/li>\n<\/ul>\n
            2 anv\u00e4ndare r\u00f6stade. 1 anv\u00e4ndare avstod.
        \n
        K\u00e4lla: 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 eller hur man skapar ett bin\u00e4rt s\u00f6ktr\u00e4d | ProHoster","description":"Inledning Denna artikel handlar om bin\u00e4ra s\u00f6ktr\u00e4d.","canonical_url":"https:\/\/prohoster.info\/sv\/blog\/administrirovanie\/binary-tree-ili-kak-prigotovit-binarnoe-derevo-poiska","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"sv_SE","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\/sv\/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\/sv\/wp-json\/wp\/v2\/posts\/30530","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/sv\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/sv\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/sv\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/sv\/wp-json\/wp\/v2\/comments?post=30530"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/sv\/wp-json\/wp\/v2\/posts\/30530\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/sv\/wp-json\/wp\/v2\/media\/22528"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/sv\/wp-json\/wp\/v2\/media?parent=30530"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/sv\/wp-json\/wp\/v2\/categories?post=30530"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/sv\/wp-json\/wp\/v2\/tags?post=30530"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}