{"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\/pl\/blog\/administrirovanie\/binary-tree-ili-kak-prigotovit-binarnoe-derevo-poiska","title":{"rendered":"Binary Tree, czyli jak przygotowa\u0107 drzewo binarne wyszukiwania","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Wst\u0119p<\/h2>\n

\nTen artyku\u0142 po\u015bwi\u0119cony jest binarnym drzewom wyszukiwania. Niedawno pisa\u0142em artyku\u0142 na temat kompresji danych metod\u0105 Huffmana.<\/a><\/noindex> Tam nie zwraca\u0142em du\u017co uwagi na drzewa binarne, poniewa\u017c metody wyszukiwania, wstawiania i usuwania nie by\u0142y istotne. Teraz postanowi\u0142em napisa\u0107 artyku\u0142 dok\u0142adnie o drzewach. Zacznijmy. <\/p>\n

Drzewo to struktura danych sk\u0142adaj\u0105ca si\u0119 z w\u0119z\u0142\u00f3w po\u0142\u0105czonych kraw\u0119dziami. Mo\u017cna powiedzie\u0107, \u017ce drzewo jest szczeg\u00f3lnym przypadkiem grafu. Oto przyk\u0142ad drzewa: <\/p>\n

\"Binary
\n
\nTo nie jest binarne drzewo wyszukiwania! Wszystko poni\u017cej!
\n<\/a><\/noindex><\/p>\n

Terminologia<\/h2>\n

<\/p>\n

Korze\u0144<\/h4>\n

\nKorze\u0144 drzewa<\/i> to najwy\u017cszy jego w\u0119ze\u0142. W naszym przyk\u0142adzie jest to w\u0119ze\u0142 A. W drzewie od korzenia do dowolnego innego w\u0119z\u0142a mo\u017ce prowadzi\u0107 tylko jedna \u015bcie\u017cka! W rzeczywisto\u015bci ka\u017cdy w\u0119ze\u0142 mo\u017cna rozwa\u017ca\u0107 jako korze\u0144 odpowiadaj\u0105cego mu poddrzewa.<\/p>\n

Rodzice \/ potomkowie<\/h4>\n

\nWszystkie w\u0119z\u0142y, poza korzeniem, maj\u0105 dok\u0142adnie jedn\u0105 kraw\u0119d\u017a prowadz\u0105c\u0105 w g\u00f3r\u0119 do innego w\u0119z\u0142a. W\u0119ze\u0142 znajduj\u0105cy si\u0119 wy\u017cej od aktualnego nazywa si\u0119 rodzicem<\/i> tego w\u0119z\u0142a. W\u0119ze\u0142 znajduj\u0105cy si\u0119 ni\u017cej i po\u0142\u0105czony z nim nazywa si\u0119 potomkiem<\/i> tego w\u0119z\u0142a. Sp\u00f3jrzmy na przyk\u0142ad. We\u017amy w\u0119ze\u0142 B, wtedy jego rodzicem b\u0119dzie w\u0119ze\u0142 A, a potomkami w\u0119z\u0142y D, E i F.<\/p>\n

Kartka<\/h4>\n

\nW\u0119ze\u0142, kt\u00f3ry nie ma potomk\u00f3w, nazywa si\u0119 li\u015bciem drzewa. W naszym przyk\u0142adzie li\u015b\u0107mi b\u0119d\u0105 w\u0119z\u0142y D, E, F, G, I, J, K.<\/p>\n

To podstawowa terminologia. Inne poj\u0119cia b\u0119d\u0105 omawiane dalej. Tak wi\u0119c, drzewo binarne to drzewo, w kt\u00f3rym ka\u017cdy w\u0119ze\u0142 ma nie wi\u0119cej ni\u017c dw\u00f3ch potomk\u00f3w. Jak si\u0119 domy\u015blili\u015bcie, drzewo z przyk\u0142adu nie jest binarne, poniewa\u017c w\u0119z\u0142y B i H maj\u0105 wi\u0119cej ni\u017c dw\u00f3ch potomk\u00f3w. Oto przyk\u0142ad binarnego drzewa:<\/p>\n

\"Binary
\n
\nW w\u0119z\u0142ach drzewa mo\u017ce znajdowa\u0107 si\u0119 dowolna informacja. Binarne drzewo wyszukiwania to binarne drzewo, kt\u00f3re charakteryzuje si\u0119 nast\u0119puj\u0105cymi w\u0142a\u015bciwo\u015bciami:<\/p>\n

    \n
  1. Oba poddrzewa \u2014 lewe i prawe \u2014 s\u0105 binarnymi drzewami wyszukiwania.<\/li>\n
  2. Wszystkie w\u0119z\u0142y lewego poddrzewa dowolnego w\u0119z\u0142a X maj\u0105 warto\u015bci kluczy danych mniejsze ni\u017c warto\u015b\u0107 klucza danych samego w\u0119z\u0142a X.<\/li>\n
  3. Wszystkie w\u0119z\u0142y prawego poddrzewa dowolnego w\u0119z\u0142a X maj\u0105 warto\u015bci kluczy danych wi\u0119ksze lub r\u00f3wne warto\u015bci klucza danych tego w\u0119z\u0142a X. <\/li>\n<\/ol>\n

    Klucz<\/i> to jaka\u015b cecha w\u0119z\u0142a (np. liczba). Klucz jest potrzebny, aby mo\u017cna by\u0142o znale\u017a\u0107 element drzewa, do kt\u00f3rego przypisany jest ten klucz. Oto przyk\u0142ad binarnego drzewa wyszukiwania:<\/p>\n

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

    Reprezentacja drzewa<\/h2>\n

    \nW miar\u0119 post\u0119pu b\u0119d\u0119 przedstawia\u0107 niekt\u00f3re (by\u0107 mo\u017ce niekompletne) fragmenty kodu, aby poprawi\u0107 twoje zrozumienie. Pe\u0142ny kod b\u0119dzie na ko\u0144cu artyku\u0142u. <\/p>\n

    Drzewo sk\u0142ada si\u0119 z w\u0119z\u0142\u00f3w. Struktura w\u0119z\u0142a:<\/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\/\/...pozosta\u0142e metody w\u0119z\u0142a\n}\n<\/code><\/pre>\n
    \nKa\u017cdy w\u0119ze\u0142 ma dw\u00f3ch potomk\u00f3w (prawdopodobnie potomkowie leftChild i\/lub rightChild b\u0119d\u0105 zawiera\u0107 warto\u015b\u0107 null). Mo\u017cna zauwa\u017cy\u0107, \u017ce w tym przypadku liczba data \u2013 to dane przechowywane w w\u0119\u017ale; key \u2013 to klucz w\u0119z\u0142a.<\/p>\n
    Z w\u0119z\u0142em ju\u017c si\u0119 zapoznali\u015bmy, teraz porozmawiajmy o bie\u017c\u0105cych problemach zwi\u0105zanych z drzewami. Tutaj i dalej przez s\u0142owo \u201edrzewo\u201d rozumiem poj\u0119cie binarnego drzewa wyszukiwania. Struktura binarnego drzewa:<\/p>\n
    public class BinaryTree<T> {\n     private Node<T> root;\n\n    \/\/metody drzewa\n}\n<\/code><\/pre>\n
    Jako pole klasy potrzebujemy tylko korzenia drzewa, poniewa\u017c z korzenia za pomoc\u0105 metod getLeftChild() i getRightChild() mo\u017cna dotrze\u0107 do dowolnego w\u0119z\u0142a drzewa.<\/p>\n
    Algorytmy w drzewie<\/h2>\n
    <\/p>\n
    Wyszukiwanie<\/h3>\n
    \nZa\u0142\u00f3\u017cmy, \u017ce masz zbudowane drzewo. Jak znale\u017a\u0107 element z kluczem key? Nale\u017cy kolejno porusza\u0107 si\u0119 od korzenia w d\u00f3\u0142 po drzewie i por\u00f3wnywa\u0107 warto\u015b\u0107 key z kluczem kolejnego w\u0119z\u0142a: je\u015bli key jest mniejszy ni\u017c klucz kolejnego w\u0119z\u0142a, to przeszukaj lewego potomka w\u0119z\u0142a, je\u015bli wi\u0119kszy \u2013 prawego, a je\u015bli klucze s\u0105 r\u00f3wne \u2013 poszukiwany w\u0119ze\u0142 zosta\u0142 znaleziony! Odpowiedni kod:<\/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
    \nJe\u015bli current staje si\u0119 r\u00f3wny null, to oznacza, \u017ce przeszukiwanie osi\u0105gn\u0119\u0142o koniec drzewa (na poziomie koncepcyjnym znajdujesz si\u0119 w nieistniej\u0105cym miejscu drzewa \u2013 potomku li\u015bcia).<\/p>\n
    Rozwa\u017cmy efektywno\u015b\u0107 algorytmu wyszukiwania w zbalansowanym drzewie (drzewie, w kt\u00f3rym w\u0119z\u0142y s\u0105 roz\u0142o\u017cone w miar\u0119 r\u00f3wnomiernie). W takim razie efektywno\u015b\u0107 wyszukiwania b\u0119dzie O(log(n)), przy czym logarytm o podstawie 2. Zobacz: je\u015bli w zbalansowanym drzewie jest n element\u00f3w, to oznacza, \u017ce b\u0119dzie log(n) o podstawie 2 poziom\u00f3w drzewa. A w wyszukiwaniu, w jednym kroku p\u0119tli, schodzisz na jeden poziom.<\/p>\n
    Wstawka<\/h3>\n
    \nJe\u015bli zrozumia\u0142e\u015b istot\u0119 wyszukiwania, to zrozumienie wstawki nie sprawi ci trudno\u015bci. Wystarczy po prostu zej\u015b\u0107 do li\u015bcia drzewa (zgodnie z zasadami schodzenia, opisanymi w wyszukiwaniu) i sta\u0107 si\u0119 jego potomkiem \u2014 lewym lub prawym, w zale\u017cno\u015bci od klucza. Implementacja:<\/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
    \nW tej sytuacji nale\u017cy, opr\u00f3cz bie\u017c\u0105cego w\u0119z\u0142a, przechowywa\u0107 informacje o rodzicu bie\u017c\u0105cego w\u0119z\u0142a. Kiedy current stanie si\u0119 r\u00f3wny null, w zmiennej parent b\u0119dzie le\u017ca\u0142 potrzebny nam li\u015b\u0107. 
    \nEfektywno\u015b\u0107 wstawki oczywi\u015bcie b\u0119dzie taka sama jak dla wyszukiwania \u2014 O(log(n)).<\/p>\n
    Usuni\u0119cie<\/h3>\n
    \nUsuni\u0119cie jest najtrudniejsz\u0105 operacj\u0105, jak\u0105 trzeba b\u0119dzie przeprowadzi\u0107 z drzewem. Oczywiste jest, \u017ce najpierw musimy znale\u017a\u0107 element, kt\u00f3ry planujemy usun\u0105\u0107. Ale co potem? Je\u015bli po prostu przypiszemy jego referencji warto\u015b\u0107 null, stracimy informacje o poddrzewie, kt\u00f3rego korzeniem jest ten w\u0119ze\u0142. Metody usuwania drzewa dziel\u0105 si\u0119 na trzy przypadki.<\/p>\n
    Pierwszy przypadek. Usuwany w\u0119ze\u0142 nie ma potomk\u00f3w.<\/h4>\n
    \nJe\u015bli usuwany w\u0119ze\u0142 nie ma potomk\u00f3w, to oznacza, \u017ce jest li\u015bciem. W zwi\u0105zku z tym mo\u017cna po prostu przypisa\u0107 warto\u015b\u0107 null polom leftChild lub rightChild jego rodzica. <\/p>\n
    Drugi przypadek. Usuwany w\u0119ze\u0142 ma jednego potomka.<\/h4>\n
    \nTen przypadek r\u00f3wnie\u017c nie jest zbyt trudny. Wr\u00f3\u0107my do naszego przyk\u0142adu. Za\u0142\u00f3\u017cmy, \u017ce musimy usun\u0105\u0107 element z kluczem 14. Zg\u00f3d\u017a si\u0119, \u017ce poniewa\u017c jest on prawym potomkiem w\u0119z\u0142a z kluczem 10, ka\u017cdy jego potomek (w tym przypadku prawy) b\u0119dzie mia\u0142 klucz wi\u0119kszy od 10, wi\u0119c mo\u017cna go \u0142atwo \u201ewyci\u0105\u0107\u201d z drzewa, a rodzica bezpo\u015brednio po\u0142\u0105czy\u0107 z potomkiem usuwanego w\u0119z\u0142a, tzn. w\u0119ze\u0142 z kluczem 10 po\u0142\u0105czy\u0107 z w\u0119z\u0142em 13. Podobna sytuacja mia\u0142aby miejsce, gdyby trzeba by\u0142o usun\u0105\u0107 w\u0119ze\u0142, kt\u00f3ry jest lewym potomkiem swojego rodzica. Pomy\u015bl o tym sam. <\/p>\n
    Trzeci przypadek. W\u0119ze\u0142 ma dw\u00f3ch potomk\u00f3w.<\/h4>\n
    \nNajtrudniejszy przypadek. Rozwa\u017cmy na nowym przyk\u0142adzie.<\/p>\n
    \"Binary
    \n<\/p>\n
    Wyszukiwanie nast\u0119pcy.<\/h4>\n
    \n Za\u0142\u00f3\u017cmy, \u017ce trzeba usun\u0105\u0107 w\u0119ze\u0142 o kluczu 25. Kogo ustawimy na jego miejsce? Kto\u015b z jego potomk\u00f3w (dziedzic\u00f3w lub potomk\u00f3w potomk\u00f3w) powinien zosta\u0107 nast\u0119pc\u0105<\/i>(tym, kto zajmie miejsce usuwanego w\u0119z\u0142a). <\/p>\n
    Jak zrozumie\u0107, kto powinien zosta\u0107 nast\u0119pc\u0105? Intuicyjnie wiadomo, \u017ce jest to w\u0119ze\u0142 w drzewie, kt\u00f3rego klucz jest najwi\u0119kszy spo\u015br\u00f3d kluczy mniejszych od usuwanego w\u0119z\u0142a. Algorytm polega na tym, aby przej\u015b\u0107 do jego prawego potomka (zawsze do prawego, poniewa\u017c ju\u017c wspomniano, \u017ce klucz nast\u0119pcy jest wi\u0119kszy od klucza usuwanego w\u0119z\u0142a), a nast\u0119pnie prze\u015bledzi\u0107 \u0142a\u0144cuch lewych potomk\u00f3w tego prawego potomka. W przyk\u0142adzie musimy przej\u015b\u0107 do w\u0119z\u0142a o kluczu 35, a nast\u0119pnie przej\u015b\u0107 w d\u00f3\u0142 do li\u015bcia wzd\u0142u\u017c \u0142a\u0144cucha jego lewych potomk\u00f3w \u2014 w tym przypadku \u0142a\u0144cuch ten sk\u0142ada si\u0119 tylko z w\u0119z\u0142a o kluczu 30. \u015acis\u0142e m\u00f3wi\u0105c, szukamy najmniejszego w\u0119z\u0142a w zbiorze w\u0119z\u0142\u00f3w wi\u0119kszych ni\u017c szukany w\u0119ze\u0142.<\/p>\n
    \"Binary
    \n
    \nKod metody wyszukiwania nast\u0119pcy:<\/p>\n
        public Node<T> getSuccessor(Node<T> deleteNode) {\n        Node<T> parentSuccessor = deleteNode; \/\/ rodzic nast\u0119pcy\n        Node<T> successor = deleteNode; \/\/ nast\u0119pca\n        Node<T> current = successor.getRightChild(); \/\/ po prostu \"przebiegaj\u0105cy\" w\u0119ze\u0142\n        while (current != null) {\n            parentSuccessor = successor;\n            successor = current;\n            current = current.getLeftChild();\n        }\n        \/\/ na wyj\u015bciu z p\u0119tli mamy nast\u0119pcy i rodzica nast\u0119pcy\n        if (successor != deleteNode.getRightChild()) { \/\/ je\u015bli nast\u0119pca nie zgadza si\u0119 z prawym potomkiem usuwanego w\u0119z\u0142a\n            parentSuccessor.setLeftChild(successor.getRightChild()); \/\/ to jego rodzic zabiera sobie potomka nast\u0119pcy, aby go nie straci\u0107\n            successor.setRightChild(deleteNode.getRightChild()); \/\/ \u0142\u0105czymy nast\u0119pcy z prawym potomkiem usuwanego w\u0119z\u0142a\n        }\n        return successor;\n    }\n<\/code><\/pre>\n
    \nPe\u0142ny kod metody delete:<\/p>\n
    public boolean delete(int deleteKey) {\n        Node current = root;\n        Node parent = current;\n        boolean isLeftChild = false; \/\/ W zale\u017cno\u015bci od tego, czy usuwany w\u0119ze\u0142 jest lewym, czy prawym dzieckiem swojego rodzica, zmienna boolean isLeftChild przyjmie warto\u015b\u0107 true lub false odpowiednio.\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) { \/\/ pierwszy przypadek\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) { \/\/ drugi przypadek\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 { \/\/ trzeci przypadek\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
    \nZ\u0142o\u017cono\u015b\u0107 mo\u017cna przybli\u017cy\u0107 do O(log(n)).<\/p>\n
    Szukaj maksimum\/minimum w drzewie<\/h3>\n
    \nOczywi\u015bcie, aby znale\u017a\u0107 minimaln\u0105\/maksymaln\u0105 warto\u015b\u0107 w drzewie, nale\u017cy kolejno przechodzi\u0107 po \u0142a\u0144cuchu lewych\/prawych element\u00f3w drzewa; kiedy dotrzesz do li\u015bcia, b\u0119dzie on minimalnym\/maksymalnym elementem.<\/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
    \nZ\u0142o\u017cono\u015b\u0107 \u2014 O(log(n))<\/p>\n
    Symetryczne przej\u015bcie<\/h3>\n
    \nPrzej\u015bcie \u2014 odwiedzanie ka\u017cdego w\u0119z\u0142a drzewa w celu wykonania jakiej\u015b akcji.<\/p>\n
    Algorytm rekurencyjnego symetrycznego przej\u015bcia:<\/p>\n
      \n
    1. Zr\u00f3b akcj\u0119 z lewym dzieckiem<\/li>\n
    2. Zr\u00f3b akcj\u0119 ze sob\u0105<\/li>\n
    3. Zr\u00f3b akcj\u0119 z prawym dzieckiem<\/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() + \" \"); \/\/Tutaj mo\u017ce by\u0107 wszystko, co chcesz\n            inOrder(current.getRightChild());\n        }\n    }\n<\/code><\/pre>\n
      <\/p>\n
      Podsumowanie<\/h2>\n
      \nW ko\u0144cu! Je\u015bli co\u015b niedok\u0142adnie wyja\u015bni\u0142em lub masz jakiekolwiek uwagi, czekam na komentarze. Jak obieca\u0142em, podaj\u0119 pe\u0142ny kod.<\/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
      Degeneracja do O(n)<\/h3>\n
      \nWielu z was mog\u0142o zauwa\u017cy\u0107: a co, je\u015bli zrobimy drzewo niezr\u00f3wnowa\u017conym? Na przyk\u0142ad, umieszczaj\u0105c w drzewie w\u0119z\u0142y z rosn\u0105cymi kluczami: 1,2,3,4,5,6\u2026 Wtedy drzewo b\u0119dzie przypomina\u0107 list\u0119 po\u0142\u0105czon\u0105. I tak, drzewo straci swoj\u0105 struktur\u0119 drzewiast\u0105, a co za tym idzie, efektywno\u015b\u0107 dost\u0119pu do danych. Z\u0142o\u017cono\u015b\u0107 operacji wyszukiwania, wstawiania, usuwania stanie si\u0119 taka jak w listach po\u0142\u0105czonych: O(n). W tym objawia si\u0119 jedno z najwa\u017cniejszych, moim zdaniem, niedoci\u0105gni\u0119\u0107 drzew binarnych.<\/p>\n
      Tylko zarejestrowani u\u017cytkownicy mog\u0105 bra\u0107 udzia\u0142 w ankiecie. Zaloguj si\u0119<\/a><\/noindex>, prosz\u0119.<\/p>\n
      Niedawno znalaz\u0142em si\u0119 na Hubie i chcia\u0142bym wiedzie\u0107, o jakich tematach chcieliby\u015bcie widzie\u0107 wi\u0119cej artyku\u0142\u00f3w?<\/h2>\n
        \n
      • \n
                            Struktury danych<\/p>\n<\/li>\n
      • \n
                            Algorytmy (DP, rekurencja, kompresja danych itd.)<\/p>\n<\/li>\n
      • \n
                            Zastosowanie struktur danych i algorytm\u00f3w w realnym \u017cyciu<\/p>\n<\/li>\n
      • \n
                            Programowanie aplikacji android w Javie<\/p>\n<\/li>\n
      • \n
                            Programowanie aplikacji webowych w Javie<\/p>\n<\/li>\n<\/ul>\n
            Zag\u0142osowa\u0142o 2 u\u017cytkownik\u00f3w. Wstrzyma\u0142 si\u0119 1 u\u017cytkownik.
        \n
        \u0179r\u00f3d\u0142o: 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\udd47Binary Tree czyli jak przygotowa\u0107 binarne drzewo wyszukiwania | ProHoster","description":"Preludium Ten artyku\u0142 po\u015bwi\u0119cony jest binarnym drzewom wyszukiwania.","canonical_url":"https:\/\/prohoster.info\/pl\/blog\/administrirovanie\/binary-tree-ili-kak-prigotovit-binarnoe-derevo-poiska","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"pl_PL","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\/pl\/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\/pl\/wp-json\/wp\/v2\/posts\/30530","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/comments?post=30530"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/posts\/30530\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/media\/22528"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/media?parent=30530"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/categories?post=30530"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/tags?post=30530"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}