ProHoster > Blog > Pangangasiwa > Binary Tree o kung paano maghanda ng binary search tree

Binary Tree o kung paano maghanda ng binary search tree

Foreplay

Ang artikulong ito ay tungkol sa binary search tree. Nagsulat ako kamakailan ng isang artikulo tungkol sa compression ng data sa pamamagitan ng Huffman method. Doon ay hindi ko talaga binigyang pansin ang mga binary tree, dahil ang mga paraan ng paghahanap, pagpasok, pagtanggal ay hindi nauugnay. Ngayon ay nagpasya akong magsulat ng isang artikulo tungkol sa mga puno. Siguro magsisimula na tayo.

Ang puno ay isang istraktura ng data na binubuo ng mga node na konektado sa pamamagitan ng mga gilid. Masasabi nating ang puno ay isang espesyal na kaso ng isang graph. Narito ang isang halimbawa ng puno:

Binary Tree o kung paano maghanda ng binary search tree

Ito ay hindi isang binary search tree! Lahat ay nasa ilalim ng hiwa!

terminolohiya

Root

ugat ng puno ay ang pinakamataas na node. Sa halimbawa, ito ay node A. Sa puno, isang landas lamang ang maaaring humantong mula sa ugat patungo sa anumang iba pang node! Sa katunayan, anumang node ay maaaring ituring na ugat ng subtree na tumutugma sa node na ito.

Mga magulang/anak

Ang lahat ng mga node maliban sa ugat ay may eksaktong isang gilid na humahantong sa isa pang node. Ang node sa itaas ng kasalukuyang node ay tinatawag magulang node na ito. Ang isang node na matatagpuan sa ibaba ng kasalukuyang isa at konektado dito ay tinatawag inapo node na ito. Kumuha tayo ng isang halimbawa. Kunin ang node B, kung gayon ang magulang nito ay magiging node A, at ang mga anak nito ay magiging mga node D, E, at F.

Dahon

Ang isang node na walang mga anak ay tinatawag na dahon ng puno. Sa halimbawa, ang mga node D, E, F, G, I, J, K ay magiging mga dahon.

Ito ang pangunahing terminolohiya. Ang iba pang mga konsepto ay tatalakayin sa ibang pagkakataon. Kaya, ang isang binary tree ay isang puno kung saan ang bawat node ay magkakaroon ng hindi hihigit sa dalawang anak. Tulad ng iyong nahulaan, ang puno mula sa halimbawa ay hindi magiging binary, dahil ang mga node B at H ay may higit sa dalawang anak. Narito ang isang halimbawa ng isang binary tree:

Binary Tree o kung paano maghanda ng binary search tree

Ang mga node ng puno ay maaaring maglaman ng anumang impormasyon. Ang binary search tree ay isang binary tree na may mga sumusunod na katangian:

  1. Parehong kaliwa at kanang subtree ay binary search tree.
  2. Ang lahat ng mga node ng kaliwang subtree ng isang arbitrary na node X ay may mga data key values ​​na mas mababa kaysa sa data key value ng node X mismo.
  3. Ang lahat ng mga node ng kanang subtree ng isang arbitrary na node X ay may mga halaga ng data key na mas malaki kaysa sa o katumbas ng halaga ng data key ng node X mismo.

Key - ilang katangian ng node (halimbawa, isang numero). Kailangan ang susi upang mahanap ang elemento ng puno kung saan tumutugma ang susi na ito. Halimbawa ng binary search tree:

Binary Tree o kung paano maghanda ng binary search tree

view ng puno

Habang nagpapatuloy ako, isasama ko ang ilang (marahil hindi kumpleto) mga piraso ng code upang mapabuti ang iyong pang-unawa. Ang buong code ay nasa dulo ng artikulo.

Ang puno ay binubuo ng mga node. Istraktura ng node:

public class Node<T> {
    private T data;
    private int key;
    private Node<T> leftChild;
    private Node<T> rightChild;

    public Node(T data, int key) {
        this.data = data;
        this.key = key;
    }
    public Node<T> getLeftChild() {
        return leftChild;
    }

    public Node<T> getRightChild() {
        return rightChild;
    }
//...ΠΎΡΡ‚Π°Π»ΡŒΠ½Ρ‹Π΅ ΠΌΠ΅Ρ‚ΠΎΠ΄Ρ‹ ΡƒΠ·Π»Π°
}

Ang bawat node ay may dalawang anak (posible na ang leftChild at/o rightChild na mga bata ay magiging null). Marahil ay naunawaan mo na sa kasong ito ang data ng numero ay ang data na nakaimbak sa node; susi - node key.

Nalaman namin ang buhol, ngayon ay pag-usapan natin ang mga problema sa pagpindot tungkol sa mga puno. Pagkatapos nito, ang salitang "puno" ay mangangahulugan ng konsepto ng isang binary search tree. Binary tree structure:

public class BinaryTree<T> {
     private Node<T> root;

    //ΠΌΠ΅Ρ‚ΠΎΠ΄Ρ‹ Π΄Π΅Ρ€Π΅Π²Π°
}

Bilang isang field ng klase, kailangan lang natin ang ugat ng puno, dahil mula sa ugat, gamit ang getLeftChild() at getRightChild() na mga pamamaraan, maaari kang makarating sa anumang node ng puno.

Mga Algorithm ng Puno

paghahanap

Sabihin nating mayroon kang built tree. Paano makahanap ng elemento na may key key? Kailangan mong sunud-sunod na lumipat mula sa ugat pababa sa puno at ihambing ang halaga ng susi sa susi ng susunod na node: kung ang susi ay mas mababa sa susi ng susunod na node, pagkatapos ay pumunta sa kaliwang inapo ng node, kung higit pa - sa kanan, kung ang mga susi ay pantay - ang nais na node ay matatagpuan! Kaugnay na code:

public Node<T> find(int key) {
    Node<T> current = root;
    while (current.getKey() != key) {
        if (key < current.getKey())
            current = current.getLeftChild();
        else
            current = current.getRightChild();
        if (current == null)
            return null;
    }
    return current;
}

Kung ang kasalukuyang ay nagiging null, pagkatapos ay ang pag-ulit ay umabot sa dulo ng puno (sa isang konseptwal na antas, ikaw ay nasa isang hindi umiiral na lugar sa puno - isang anak ng isang dahon).

Isaalang-alang ang kahusayan ng algorithm ng paghahanap sa isang balanseng puno (isang puno kung saan ang mga node ay ipinamamahagi nang higit pa o hindi gaanong pantay-pantay). Pagkatapos ang kahusayan sa paghahanap ay magiging O(log(n)), at ang base 2 logarithm. Tingnan: kung mayroong n elemento sa isang balanseng puno, nangangahulugan ito na magkakaroon ng log(n) base 2 na antas ng puno. At sa paghahanap, para sa isang hakbang ng ikot, bumaba ka ng isang antas.

magpasok

Kung naunawaan mo ang kakanyahan ng paghahanap, hindi magiging mahirap para sa iyo na maunawaan ang pagpasok. Kailangan mo lamang bumaba sa dahon ng puno (ayon sa mga patakaran ng pagbaba na inilarawan sa paghahanap) at maging inapo nito - kaliwa o kanan, depende sa susi. Pagpapatupad:

   public void insert(T insertData, int key) {
        Node<T> current = root;
        Node<T> parent;
        Node<T> newNode = new Node<>(insertData, key);
        if (root == null)
            root = newNode;
        else {
            while (true) {
                parent = current;
                if (key < current.getKey()) {
                    current = current.getLeftChild();
                    if (current == null) {
                         parent.setLeftChild(newNode);
                         return;
                    }
                }
                else {
                    current = current.getRightChild();
                    if (current == null) {
                        parent.setRightChild(newNode);
                        return;
                    }
                }
            }
        }
    }

Sa kasong ito, bilang karagdagan sa kasalukuyang node, kinakailangan na mag-imbak ng impormasyon tungkol sa magulang ng kasalukuyang node. Kapag naging null ang kasalukuyang, maglalaman ang parent variable ng sheet na kailangan namin.
Ang kahusayan sa pagpapasok ay malinaw na kapareho ng sa paghahanap - O(log(n)).

Pag-aalis

Ang pagtanggal ay ang pinaka-kumplikadong operasyon na kailangang gawin sa isang puno. Malinaw na kailangan munang hanapin ang elementong aalisin natin. Pero ano? Kung itatakda lang natin ang reference nito sa null, mawawalan tayo ng impormasyon tungkol sa subtree na ang ugat ay ang node na ito. Ang mga paraan ng pagtanggal ng puno ay nahahati sa tatlong kaso.

Unang kaso. Ang node na aalisin ay walang mga anak.

Kung ang node na tatanggalin ay walang mga anak, nangangahulugan ito na ito ay isang dahon. Samakatuwid, maaari mo lamang itakda ang leftChild o rightChild na mga field ng magulang nito sa null.

Pangalawang kaso. Ang node na aalisin ay may isang anak

Ang kasong ito ay hindi rin napakahirap. Bumalik tayo sa ating halimbawa. Ipagpalagay na kailangan nating tanggalin ang isang elemento na may key 14. Sumang-ayon na dahil ito ang tamang anak ng isang node na may key 10, kung gayon ang alinman sa mga inapo nito (sa kasong ito, ang tama) ay magkakaroon ng key na mas malaki sa 10, kaya ikaw madaling "puputol" ito mula sa puno, at direktang ikonekta ang magulang sa anak ng node na tinatanggal, i.e. ikonekta ang node na may key 10 sa node 13. Magiging katulad ang sitwasyon kung kailangan nating tanggalin ang isang node na kaliwang anak ng magulang nito. Isipin ito para sa iyong sarili - isang eksaktong pagkakatulad.

Pangatlong kaso. Si Node ay may dalawang anak

Ang pinakamahirap na kaso. Tingnan natin ang isang bagong halimbawa.

Binary Tree o kung paano maghanda ng binary search tree

Maghanap ng kahalili

Sabihin nating kailangan nating tanggalin ang node na may susi 25. Sino ang ilalagay natin sa lugar nito? Ang isa sa kanyang mga tagasunod (kaapu-apuhan o inapo ng mga inapo) ay dapat maging kahalili(ang papalit sa tinanggal na node).

Paano mo malalaman kung sino ang dapat na maging kahalili? Sa madaling salita, ito ang node sa puno na ang susi ay ang susunod na pinakamalaki mula sa node na inaalis. Ang algorithm ay ang mga sumusunod. Kailangan mong pumunta sa kanang anak nito (laging sa kanan, dahil sinabi na ang susi ng kahalili ay mas malaki kaysa sa susi ng node na tinatanggal), at pagkatapos ay dumaan sa kadena ng kaliwang mga anak ng kanang ito bata. Sa halimbawa, dapat tayong pumunta sa node na may susi 35, at pagkatapos ay bumaba sa kadena ng mga kaliwang anak nito sa dahon - sa kasong ito, ang kadena na ito ay binubuo lamang ng node na may susi 30. Sa mahigpit na pagsasalita, hinahanap natin ang ang pinakamaliit na node sa hanay ng mga node na mas malaki kaysa sa nais na node.

Binary Tree o kung paano maghanda ng binary search tree

Code ng paraan ng paghahanap ng kahalili:

    public Node<T> getSuccessor(Node<T> deleteNode) {
        Node<T> parentSuccessor = deleteNode;//Ρ€ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒ ΠΏΡ€Π΅Π΅ΠΌΠ½ΠΈΠΊΠ°
        Node<T> successor = deleteNode;//ΠΏΡ€Π΅Π΅ΠΌΠ½ΠΈΠΊ
        Node<T> current = successor.getRightChild();//просто "ΠΏΡ€ΠΎΠ±Π΅Π³Π°ΡŽΡ‰ΠΈΠΉ" ΡƒΠ·Π΅Π»
        while (current != null) {
            parentSuccessor = successor;
            successor = current;
            current = current.getLeftChild();
        }
        //Π½Π° Π²Ρ‹Ρ…ΠΎΠ΄Π΅ ΠΈΠ· Ρ†ΠΈΠΊΠ»Π° ΠΈΠΌΠ΅Π΅ΠΌ ΠΏΡ€Π΅Π΅ΠΌΠ½ΠΈΠΊΠ° ΠΈ родитСля ΠΏΡ€Π΅Π΅ΠΌΠ½ΠΈΠΊΠ°
        if (successor != deleteNode.getRightChild()) {//Ссли ΠΏΡ€Π΅Π΅ΠΌΠ½ΠΈΠΊ Π½Π΅ совпадаСт с ΠΏΡ€Π°Π²Ρ‹ΠΌ ΠΏΠΎΡ‚ΠΎΠΌΠΊΠΎΠΌ удаляСмого ΡƒΠ·Π»Π°
            parentSuccessor.setLeftChild(successor.getRightChild());//Ρ‚ΠΎ Π΅Π³ΠΎ Ρ€ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒ Π·Π°Π±ΠΈΡ€Π°Π΅Ρ‚ сСбС ΠΏΠΎΡ‚ΠΎΠΌΠΊΠ° ΠΏΡ€Π΅Π΅ΠΌΠ½ΠΈΠΊΠ°, Ρ‡Ρ‚ΠΎΠ±Ρ‹ Π½Π΅ ΠΏΠΎΡ‚Π΅Ρ€ΡΡ‚ΡŒ Π΅Π³ΠΎ
            successor.setRightChild(deleteNode.getRightChild());//связываСм ΠΏΡ€Π΅Π΅ΠΌΠ½ΠΈΠΊΠ° с ΠΏΡ€Π°Π²Ρ‹ΠΌ ΠΏΠΎΡ‚ΠΎΠΌΠΊΠΎΠΌ удаляСмого ΡƒΠ·Π»Π°
        }
        return successor;
    }

Ang kumpletong code ng paraan ng pagtanggal:

public boolean delete(int deleteKey) {
        Node<T> current = root;
        Node<T> parent = current;
        boolean isLeftChild = false;//Π’ зависимости ΠΎΡ‚ Ρ‚ΠΎΠ³ΠΎ, являСтся Π»ΠΈ  удаляСмый ΡƒΠ·Π΅Π» Π»Π΅Π²Ρ‹ΠΌ ΠΈΠ»ΠΈ ΠΏΡ€Π°Π²Ρ‹ΠΌ ΠΏΠΎΡ‚ΠΎΠΌΠΊΠΎΠΌ своСго родитСля, булСвская пСрСмСнная isLeftChild Π±ΡƒΠ΄Π΅Ρ‚ ΠΏΡ€ΠΈΠ½ΠΈΠΌΠ°Ρ‚ΡŒ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ true ΠΈΠ»ΠΈ false соотвСтствСнно.
        while (current.getKey() != deleteKey) {
            parent = current;
            if (deleteKey < current.getKey()) {
                current = current.getLeftChild();
                isLeftChild = true;
            } else {
                isLeftChild = false;
                current = current.getRightChild();
            }
            if (current == null)
                return false;
        }

        if (current.getLeftChild() == null && current.getRightChild() == null) {//ΠΏΠ΅Ρ€Π²Ρ‹ΠΉ случай
            if (current == root)
                current = null;
            else if (isLeftChild)
                parent.setLeftChild(null);
            else
                parent.setRightChild(null);
        }
        else if (current.getRightChild() == null) {//Π²Ρ‚ΠΎΡ€ΠΎΠΉ случай
            if (current == root)
                root = current.getLeftChild();
            else if (isLeftChild)
                parent.setLeftChild(current.getLeftChild());
            else
                current.setRightChild(current.getLeftChild());
        } else if (current.getLeftChild() == null) {
            if (current == root)
                root = current.getRightChild();
            else if (isLeftChild)
                parent.setLeftChild(current.getRightChild());
            else
                parent.setRightChild(current.getRightChild());
        } 
        else {//Ρ‚Ρ€Π΅Ρ‚ΠΈΠΉ случай
            Node<T> successor = getSuccessor(current);
            if (current == root)
                root = successor;
            else if (isLeftChild)
                parent.setLeftChild(successor);
            else
                parent.setRightChild(successor);
        }
        return true;
    }

Ang pagiging kumplikado ay maaaring tinantya sa O(log(n)).

Paghahanap ng maximum/minimum sa isang puno

Malinaw, kung paano hanapin ang minimum / maximum na halaga sa puno - kailangan mong sunud-sunod na dumaan sa kadena ng kaliwa / kanang elemento ng puno, ayon sa pagkakabanggit; kapag nakarating ka sa dahon, ito ang magiging minimum/maximum na elemento.

    public Node<T> getMinimum(Node<T> startPoint) {
        Node<T> current = startPoint;
        Node<T> parent = current;
        while (current != null) {
            parent = current;
            current = current.getLeftChild();
        }
        return parent;
    }

    public Node<T> getMaximum(Node<T> startPoint) {
        Node<T> current = startPoint;
        Node<T> parent = current;
        while (current != null) {
            parent = current;
            current = current.getRightChild();
        }
        return parent;
    }

Pagiging kumplikado - O(log(n))

Symmetric Bypass

Ang Traversal ay isang pagbisita sa bawat node ng puno upang magawa ang isang bagay dito.

Recursive symmetric traversal algorithm:

  1. Gumawa ng aksyon sa kaliwang bata
  2. Gumawa ng isang aksyon sa iyong sarili
  3. Gumawa ng aksyon sa tamang bata

Code:

    public void inOrder(Node<T> current) {
        if (current != null) {
            inOrder(current.getLeftChild());
            System.out.println(current.getData() + " ");//Π—Π΄Π΅ΡΡŒ ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ всС, Ρ‡Ρ‚ΠΎ ΡƒΠ³ΠΎΠ΄Π½ΠΎ
            inOrder(current.getRightChild());
        }
    }

Konklusyon

Sa wakas! Kung wala akong ipinaliwanag o may anumang komento, naghihintay ako sa mga komento. Gaya ng ipinangako, narito ang kumpletong code.

Node.java:

public class Node<T> {
    private T data;
    private int key;
    private Node<T> leftChild;
    private Node<T> rightChild;

    public Node(T data, int key) {
        this.data = data;
        this.key = key;
    }

    public void setLeftChild(Node<T> newNode) {
        leftChild = newNode;
    }

    public void setRightChild(Node<T> newNode) {
        rightChild = newNode;
    }

    public Node<T> getLeftChild() {
        return leftChild;
    }

    public Node<T> getRightChild() {
        return rightChild;
    }

    public T getData() {
        return data;
    }

    public int getKey() {
        return key;
    }
}

BinaryTree.java:

public class BinaryTree<T> {
    private Node<T> root;

    public Node<T> find(int key) {
        Node<T> current = root;
        while (current.getKey() != key) {
            if (key < current.getKey())
                current = current.getLeftChild();
            else
                current = current.getRightChild();
            if (current == null)
                return null;
        }
        return current;
    }

    public void insert(T insertData, int key) {
        Node<T> current = root;
        Node<T> parent;
        Node<T> newNode = new Node<>(insertData, key);
        if (root == null)
            root = newNode;
        else {
            while (true) {
                parent = current;
                if (key < current.getKey()) {
                    current = current.getLeftChild();
                    if (current == null) {
                         parent.setLeftChild(newNode);
                         return;
                    }
                }
                else {
                    current = current.getRightChild();
                    if (current == null) {
                        parent.setRightChild(newNode);
                        return;
                    }
                }
            }
        }
    }

    public Node<T> getMinimum(Node<T> startPoint) {
        Node<T> current = startPoint;
        Node<T> parent = current;
        while (current != null) {
            parent = current;
            current = current.getLeftChild();
        }
        return parent;
    }

    public Node<T> getMaximum(Node<T> startPoint) {
        Node<T> current = startPoint;
        Node<T> parent = current;
        while (current != null) {
            parent = current;
            current = current.getRightChild();
        }
        return parent;
    }

    public Node<T> getSuccessor(Node<T> deleteNode) {
        Node<T> parentSuccessor = deleteNode;
        Node<T> successor = deleteNode;
        Node<T> current = successor.getRightChild();
        while (current != null) {
            parentSuccessor = successor;
            successor = current;
            current = current.getLeftChild();
        }

        if (successor != deleteNode.getRightChild()) {
            parentSuccessor.setLeftChild(successor.getRightChild());
            successor.setRightChild(deleteNode.getRightChild());
        }
        return successor;
    }

    public boolean delete(int deleteKey) {
        Node<T> current = root;
        Node<T> parent = current;
        boolean isLeftChild = false;
        while (current.getKey() != deleteKey) {
            parent = current;
            if (deleteKey < current.getKey()) {
                current = current.getLeftChild();
                isLeftChild = true;
            } else {
                isLeftChild = false;
                current = current.getRightChild();
            }
            if (current == null)
                return false;
        }

        if (current.getLeftChild() == null && current.getRightChild() == null) {
            if (current == root)
                current = null;
            else if (isLeftChild)
                parent.setLeftChild(null);
            else
                parent.setRightChild(null);
        }
        else if (current.getRightChild() == null) {
            if (current == root)
                root = current.getLeftChild();
            else if (isLeftChild)
                parent.setLeftChild(current.getLeftChild());
            else
                current.setRightChild(current.getLeftChild());
        } else if (current.getLeftChild() == null) {
            if (current == root)
                root = current.getRightChild();
            else if (isLeftChild)
                parent.setLeftChild(current.getRightChild());
            else
                parent.setRightChild(current.getRightChild());
        } 
        else {
            Node<T> successor = getSuccessor(current);
            if (current == root)
                root = successor;
            else if (isLeftChild)
                parent.setLeftChild(successor);
            else
                parent.setRightChild(successor);
        }
        return true;
    }

    public void inOrder(Node<T> current) {
        if (current != null) {
            inOrder(current.getLeftChild());
            System.out.println(current.getData() + " ");
            inOrder(current.getRightChild());
        }
    }
}

PS

Pagkabulok sa O(n)

Maaaring napansin ng marami sa inyo: paano kung gagawin mong hindi balanse ang puno? Halimbawa, ilagay ang mga node na may pagtaas ng mga susi sa isang puno: 1,2,3,4,5,6... Pagkatapos ang puno ay magiging kamukha ng isang naka-link na listahan. At oo, mawawalan ng istraktura ng puno ang puno, at samakatuwid ang kahusayan ng pag-access ng data. Ang pagiging kumplikado ng mga operasyon sa paghahanap, pagpasok, at pagtanggal ay magiging kapareho ng sa isang naka-link na listahan: O(n). Ito ay isa sa pinakamahalaga, sa palagay ko, ang mga disadvantages ng mga binary tree.

Ang mga rehistradong user lamang ang maaaring lumahok sa survey. Mag-sign in, pakiusap

Medyo matagal na akong wala sa HabrΓ©, at gusto kong malaman kung anong mga artikulo sa anong mga paksa ang gusto mong makita pa?

  • Mga Istraktura ng Data

  • Algorithm (DP, recursion, data compression, atbp.)

  • Application ng mga istruktura ng data at algorithm sa totoong buhay

  • Pagprograma ng mga android application sa Java

  • Java Web Application Programming

2 mga gumagamit ang bumoto. 1 user ang umiwas.

Pinagmulan: www.habr.com

Magdagdag ng komento