ProHoster > Π‘Π»ΠΎΠ³ > Pagdumala > Binary Tree o kung unsaon pag-andam ang usa ka binary search tree

Binary Tree o kung unsaon pag-andam ang usa ka binary search tree

Alang sa dula

Kini nga artikulo mahitungod sa binary search tree. Bag-o lang ako nagsulat og usa ka artikulo bahin sa data compression pinaagi sa Huffman nga pamaagi. Didto wala gyud ko magtagad sa binary nga mga kahoy, tungod kay ang mga pamaagi sa pagpangita, pagsal-ot, pagtangtang wala’y kalabotan. Karon nakahukom ko sa pagsulat ug artikulo bahin sa mga kahoy. Tingali magsugod kita.

Ang kahoy usa ka istruktura sa datos nga gilangkuban sa mga node nga konektado sa mga sulud. Mahimo natong isulti nga ang usa ka kahoy usa ka espesyal nga kaso sa usa ka graph. Ania ang usa ka pananglitan nga kahoy:

Binary Tree o kung unsaon pag-andam ang usa ka binary search tree

Dili kini usa ka binary nga punoan sa pagpangita! Ang tanan ubos sa pagputol!

Terminolohiya

Gamut

gamut sa kahoy mao ang pinakataas nga node. Sa pananglitan, kini mao ang node A. Sa kahoy, usa ra ka agianan ang mahimong modala gikan sa gamut ngadto sa bisan unsang lain nga node! Sa tinuud, ang bisan unsang node mahimong isipon nga gamut sa subtree nga katumbas niini nga node.

Mga ginikanan/anak

Ang tanan nga mga node gawas sa gamut adunay eksakto nga usa ka ngilit padulong sa lain nga node. Ang node sa ibabaw sa kasamtangan nga node gitawag ginikanan kini nga node. Ang usa ka node nga nahimutang ubos sa kasamtangan ug konektado niini gitawag kaliwat kini nga node. Atong tagdon ang usa ka pananglitan. Kuhaa ang node B, unya ang ginikanan niini mahimong node A, ug ang mga anak niini mahimong mga node D, E, ug F.

Sheet

Ang node nga walay mga anak gitawag nga dahon sa kahoy. Sa pananglitan, ang mga node D, E, F, G, I, J, K mahimong mga dahon.

Kini ang sukaranan nga terminolohiya. Ang ubang mga konsepto hisgotan sa ulahi. Busa, ang binary tree usa ka kahoy diin ang matag node adunay dili molapas sa duha ka mga anak. Sama sa imong natag-an, ang kahoy gikan sa pananglitan dili binary, tungod kay ang mga node B ug H adunay labaw sa duha ka mga anak. Ania ang usa ka pananglitan sa usa ka binary tree:

Binary Tree o kung unsaon pag-andam ang usa ka binary search tree

Ang mga buko sa kahoy mahimong adunay bisan unsang kasayuran. Ang binary search tree usa ka binary tree nga adunay mosunod nga mga kabtangan:

  1. Ang wala ug tuo nga mga subtree kay binary nga search tree.
  2. Ang tanan nga mga node sa wala nga subtree sa usa ka arbitraryong node X adunay data key values ​​nga mas ubos kaysa data key value sa node X mismo.
  3. Ang tanan nga mga node sa tuo nga subtree sa usa ka arbitraryong node X adunay mga yawe sa datos nga mga kantidad nga labaw pa sa o katumbas sa kantidad sa yawe sa datos sa node X mismo.

Key - pipila ka kinaiya sa node (pananglitan, usa ka numero). Ang yawe gikinahanglan aron makit-an ang elemento sa kahoy diin kini nga yawe katumbas. Pananglitan sa binary search tree:

Binary Tree o kung unsaon pag-andam ang usa ka binary search tree

pagtan-aw sa kahoy

Sa akong pagpadayon, akong iapil ang pipila (tingali dili kompleto) nga mga piraso sa code aron mapauswag ang imong pagsabut. Ang bug-os nga code anaa sa katapusan sa artikulo.

Ang kahoy gilangkoban sa mga node. Istruktura sa 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 matag node adunay duha ka mga anak (posible nga ang leftChild ug/o rightChild nga mga bata mahimong null). Tingali nakasabut ka nga sa kini nga kaso ang datos sa numero mao ang datos nga gitipigan sa node; yawe - yawe sa node.

Atong nahibal-an ang higot, karon atong hisgutan ang mga dinalian nga mga problema bahin sa mga kahoy. Human niini, ang pulong nga "kahoy" magpasabot sa konsepto sa usa ka binary search tree. Binary nga kahoy nga istruktura:

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

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

Isip usa ka field sa klase, gikinahanglan lang nato ang gamut sa kahoy, tungod kay gikan sa gamut, gamit ang getLeftChild() ug getRightChild() nga mga pamaagi, makaadto ka sa bisan unsang node sa kahoy.

Mga Algorithm sa Kahoy

Поиск

Ingnon ta nga ikaw adunay gitukod nga kahoy. Giunsa pagpangita ang elemento nga adunay yawe nga yawe? Kinahanglan nimo nga sunud-sunod nga mobalhin gikan sa gamut paubos sa kahoy ug itandi ang kantidad sa yawe sa yawe sa sunod nga node: kung ang yawe mas gamay kaysa sa yawe sa sunod nga node, dayon adto sa wala nga kaliwat sa node, kung daghan pa - sa tuo, kung ang mga yawe managsama - ang gitinguha nga node makit-an! May kalabotan nga 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 kasamtangan mahimong null, nan ang pag-uli nakaabot sa katapusan sa kahoy (sa usa ka konsepto nga lebel, ikaw anaa sa usa ka wala'y dapit sa kahoy - usa ka bata sa usa ka dahon).

Hunahunaa ang kaepektibo sa algorithm sa pagpangita sa usa ka balanse nga kahoy (usa ka kahoy diin ang mga node giapod-apod nga labi o dili kaayo parehas). Unya ang search efficiency mao ang O(log(n)), ug ang base 2 logarithm. Tan-awa: kung adunay n elemento sa usa ka balanse nga kahoy, nan kini nagpasabot nga adunay log(n) base 2 nga lebel sa kahoy. Ug sa pagpangita, alang sa usa ka lakang sa siklo, mopaubos ka sa usa ka lebel.

sal-ot

Kung nasabtan nimo ang esensya sa pagpangita, nan dili ka lisud nga masabtan ang pagsulud. Kinahanglan ka lang nga moadto sa dahon sa kahoy (sumala sa mga lagda sa pagkunsad nga gihulagway sa pagpangita) ug mahimong kaliwat niini - wala o tuo, depende sa yawe. Pagpatuman:

   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 kini nga kaso, dugang sa kasamtangan nga node, gikinahanglan ang pagtipig sa impormasyon mahitungod sa ginikanan sa kasamtangan nga node. Kung ang kasamtangan mahimong null, ang parent variable maglangkob sa sheet nga atong gikinahanglan.
Ang kaepektibo sa pagsal-ot klaro nga parehas sa pagpangita - O(log(n)).

Pagtangtang

Ang pagtangtang mao ang labing komplikado nga operasyon nga kinahanglan buhaton sa usa ka kahoy. Klaro nga kinahanglan una nga pangitaon ang elemento nga atong tangtangon. Apan unsa man? Kung ibutang lang nato ang reperensiya niini sa null, nan mawad-an kita og impormasyon mahitungod sa subtree nga ang gamut niini nga node. Ang mga pamaagi sa pagtangtang sa kahoy gibahin sa tulo ka mga kaso.

Unang kaso. Ang node nga kuhaon walay mga anak.

Kung ang buko nga tangtangon walay mga anak, kini nagpasabot nga kini usa ka dahon. Busa, mahimo nimong itakda ang leftChild o rightChild nga mga field sa ginikanan niini nga null.

Ikaduha nga kaso. Ang node nga kuhaon adunay usa ka anak

Kini nga kaso dili usab lisud kaayo. Balikan nato ang atong ehemplo. Ibutang ta nga kinahanglan natong tangtangon ang usa ka elemento nga adunay yawe 14. Mouyon nga tungod kay kini ang husto nga bata sa node nga adunay yawe 10, nan bisan kinsa sa mga kaliwat niini (sa kini nga kaso, ang husto) adunay usa ka yawe nga labaw sa 10, mao nga ikaw dali nga "maputol" kini gikan sa kahoy, ug ikonektar ang ginikanan direkta sa bata sa node nga gitangtang, i.e. ikonektar ang node sa yawe 10 ngadto sa node 13. Ang sitwasyon mahimong susama kon kinahanglan natong tangtangon ang usa ka node nga wala nga anak sa ginikanan niini. Hunahunaa kini alang sa imong kaugalingon - usa ka eksaktong analohiya.

Ikatulo nga kaso. Si Node adunay duha ka anak

Ang pinakalisud nga kaso. Atong tan-awon ang usa ka bag-ong pananglitan.

Binary Tree o kung unsaon pag-andam ang usa ka binary search tree

Pagpangita usa ka manununod

Ingnon ta nga kinahanglan natong tangtangon ang node nga adunay yawe 25. Kinsa ang atong ibutang sa dapit niini? Usa sa iyang mga sumusunod (kaliwat o kaliwat sa mga kaliwat) kinahanglang mahimong manununod(ang usa nga mopuli sa gikuha nga node).

Giunsa nimo pagkahibalo kung kinsa ang kinahanglan nga mopuli? Sa intuitively, kini ang node sa kahoy kansang yawe mao ang sunod nga pinakadako gikan sa node nga gikuha. Ang algorithm mao ang mosunod. Kinahanglan ka nga moadto sa tuo nga bata niini (kanunay sa tuo, tungod kay giingon na nga ang yawe sa manununod mas dako kaysa sa yawe sa node nga gitangtang), ug dayon moagi sa kadena sa wala nga mga anak niini nga tuo. bata. Sa pananglitan, kinahanglan nga moadto kita sa node nga adunay yawe 35, ug dayon ipaubos ang kadena sa wala nga mga bata sa dahon - sa kini nga kaso, kini nga kadena naglangkob lamang sa node nga adunay yawe 30. Sa estrikto nga pagsulti, gipangita namon ang ang pinakagamay nga node sa set sa mga node nga mas dako pa sa gusto nga node.

Binary Tree o kung unsaon pag-andam ang usa ka binary search tree

Kodigo sa pamaagi sa pagpangita sa nagsunod:

    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 kompleto nga code sa pamaagi sa pagtangtang:

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 pagkakomplikado mahimong mabanabana sa O(log(n)).

Pagpangita sa maximum/minimum sa usa ka kahoy

Dayag nga, kung giunsa pagpangita ang minimum / maximum nga kantidad sa kahoy - kinahanglan nimo nga sunud-sunod nga moagi sa kadena sa wala / tuo nga mga elemento sa kahoy, sa tinuud; pag-abot nimo sa dahon, kini ang minimum/maximum nga 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;
    }

Pagkakomplikado - O(log(n))

Symmetric Bypass

Ang traversal usa ka pagbisita sa matag node sa kahoy aron mahimo ang usa ka butang niini.

Recursive symmetric traversal algorithm:

  1. Paghimo og aksyon sa wala nga bata
  2. Paghimo og aksyon sa imong kaugalingon
  3. Paghimo og aksyon sa husto nga bata

Code:

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

konklusyon

Sa kataposan! Kung wala ako nagpatin-aw sa usa ka butang o adunay bisan unsang mga komento, nan naghulat ako sa mga komento. Ingon sa gisaad, ania ang kompleto nga 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

Pag-us-os ngadto sa O(n)

Daghan kaninyo ang tingali nakamatikod: unsa kaha kon himoon ninyo nga dili balanse ang kahoy? Pananglitan, ibutang ang mga node sa kahoy nga adunay nagkadaghang mga yawe: 1,2,3,4,5,6... Unya ang kahoy medyo makapahinumdom sa usa ka nasumpay nga listahan. Ug oo, ang kahoy mawad-an sa iyang istruktura sa kahoy, ug busa ang kahusayan sa pag-access sa datos. Ang pagkakomplikado sa mga operasyon sa pagpangita, pagsal-ot, ug pagtangtang mahimong pareho sa usa ka gisumpay nga listahan: O(n). Kini mao ang usa sa labing importante, sa akong opinyon, disadvantages sa binary nga mga kahoy.

Ang mga rehistradong tiggamit lamang ang makaapil sa survey. Sign in, walay sapayan.

Dugay na kong wala sa HabrΓ©, ug gusto nakong mahibal-an kung unsang mga artikulo sa unsang mga hilisgutan ang gusto nimo nga makita pa?

  • Mga Istruktura sa Data

  • Algorithm (DP, recursion, data compression, ug uban pa)

  • Ang paggamit sa mga istruktura sa datos ug mga algorithm sa tinuud nga kinabuhi

  • Pagprograma sa mga aplikasyon sa android sa Java

  • Java Web Application Programming

2 user ang nagboto. 1 user ang ni- abstain.

Tinubdan: www.habr.com

Idugang sa usa ka comment