ProHoster > Blog > Administrasyon an > Binè Tree oswa ki jan yo prepare yon pye bwa rechèch binè

Binè Tree oswa ki jan yo prepare yon pye bwa rechèch binè

Prelid

Atik sa a se sou pye bwa rechèch binè. Mwen fèk ekri yon atik sou konpresyon done pa metòd Huffman. Gen mwen pa t 'reyèlman peye atansyon sou pye bwa binè, paske metòd yo nan rechèch, mete, efase pa t' enpòtan. Koulye a, mwen deside ekri yon atik sou pye bwa. Petèt nou pral kòmanse.

Yon pye bwa se yon estrikti done ki fòme ak nœuds ki konekte pa bor. Nou ka di ke yon pye bwa se yon ka espesyal nan yon graf. Men yon egzanp pye bwa:

Binè Tree oswa ki jan yo prepare yon pye bwa rechèch binè

Sa a se pa yon pye bwa rechèch binè! Tout se anba koupe a!

Tèminoloji

Rasin

Rasin pye bwa se ne ki pi wo a. Nan egzanp lan, sa a se ne A. Nan pye bwa a, se sèlman yon chemen ki ka mennen soti nan rasin nan nenpòt lòt ne! An reyalite, nenpòt ne ka konsidere kòm rasin nan subtree ki koresponn ak ne sa a.

Paran/desandans

Tout nœuds eksepte rasin lan gen egzakteman yon kwen ki mennen ale nan yon lòt ne. Yo rele ne ki anlè a kounye a paran ne sa a. Yo rele yon ne ki sitiye anba a aktyèl la epi ki konekte ak li desandan ne sa a. Ann pran yon egzanp. Pran ne B, Lè sa a, paran li yo pral ne A, ak pitit li yo pral ne D, E, ak F.

Fèy

Yon ne ki pa gen timoun yo rele yon fèy nan pye bwa a. Nan egzanp lan, nœuds D, E, F, G, I, J, K pral fèy.

Sa a se tèminoloji debaz la. Lòt konsèp yo pral diskite pita. Se konsa, yon pye bwa binè se yon pye bwa kote chak ne pa pral gen plis pase de timoun. Kòm ou devine, pye bwa ki soti nan egzanp lan pa pral binè, paske nœuds B ak H gen plis pase de timoun. Men yon egzanp yon pye bwa binè:

Binè Tree oswa ki jan yo prepare yon pye bwa rechèch binè

Nœuds pyebwa yo ka genyen nenpòt enfòmasyon. Yon pye bwa rechèch binè se yon pye bwa binè ki gen pwopriyete sa yo:

  1. Tou de bò gòch ak dwa se pye bwa rechèch binè.
  2. Tout nœuds nan subtree gòch nan yon ne abitrè X gen valè kle done mwens pase valè kle done nan ne X tèt li.
  3. Tout nœuds nan subtree dwat nan yon ne abitrè X gen valè kle done ki pi gran pase oswa egal a valè kle done a nan ne X tèt li.

Kle - kèk karakteristik nan ne (pa egzanp, yon nimewo). Kle a nesesè pou kapab jwenn eleman nan pye bwa a ki kle sa a koresponn. Egzanp pye bwa rechèch binè:

Binè Tree oswa ki jan yo prepare yon pye bwa rechèch binè

gade pye bwa

Pandan m ap kontinye, mwen pral mete kèk (petèt enkonplè) moso nan kòd yo nan lòd yo amelyore konpreyansyon ou. Kòd konplè a pral nan fen atik la.

Pye bwa a konpoze de nœuds. Estrikti ne:

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;
    }
//...остальные методы узла
}

Chak ne gen de pitit (li se byen posib ke timoun yo leftChild ak/oswa rightChild timoun yo pral nil). Ou pwobableman konprann ke nan ka sa a done nimewo yo se done yo ki estoke nan ne la; kle - kle ne.

Nou kalkile ne a, kounye a ann pale sou pwoblèm yo peze sou pye bwa yo. Isit la ak anba a, mo "pyebwa" a pral vle di konsèp nan yon pye bwa rechèch binè. Estrikti pye bwa binè:

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

    //методы дерева
}

Kòm yon jaden klas, nou sèlman bezwen rasin nan pye bwa a, paske soti nan rasin lan, lè l sèvi avèk getLeftChild () ak getRightChild () metòd, ou ka jwenn nan nenpòt ne nan pye bwa a.

Algoritm pye bwa

rechèch

Ann di ou gen yon pye bwa bati. Ki jan yo jwenn eleman ak kle kle? Ou bezwen sekans deplase soti nan rasin lan desann pye bwa a epi konpare valè kle a ak kle nan pwochen ne: si kle a mwens pase kle a nan pwochen ne, Lè sa a, ale nan desandan gòch nan ne a, si plis - sou bò dwat la, si kle yo egal - yo jwenn ne a vle! Kòd ki enpòtan:

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;
}

Si aktyèl la vin nil, Lè sa a, iterasyon te rive nan fen pye bwa a (nan yon nivo konseptyèl ekspresyon, ou se nan yon kote ki pa egziste nan pye bwa a - yon timoun nan yon fèy).

Konsidere efikasite algorithm rechèch la sou yon pye bwa balanse (yon pye bwa kote nœuds yo distribye plis oswa mwens respire). Lè sa a, efikasite rechèch la pral O(log(n)), ak logaritm baz 2. Gade: si gen n eleman nan yon pye bwa balanse, Lè sa a, sa vle di ke pral gen log(n) nivo baz 2 nan pye bwa a. Ak nan rechèch la, pou yon etap nan sik la, ou desann yon nivo.

Insert

Si ou te konprann sans nan rechèch la, Lè sa a, li pa pral difisil pou ou konprann ensèsyon an. Ou jis bezwen desann nan fèy pye bwa a (dapre règ desandan ki dekri nan rechèch la) epi vin desandan li yo - gòch oswa dwa, tou depann de kle a. Aplikasyon:

   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;
                    }
                }
            }
        }
    }

Nan ka sa a, anplis ne aktyèl la, li nesesè pou estoke enfòmasyon sou paran ne aktyèl la. Lè aktyèl la vin nul, varyab paran an ap genyen fèy nou bezwen an.
Efikasite ensèsyon an pral evidamman menm jan ak rechèch la - O(log(n)).

Deletion

Efase se operasyon ki pi konplèks ki pral bezwen fè ak yon pye bwa. Li klè ke premye li pral nesesè yo jwenn eleman nan ke nou pral retire. Men, lè sa a? Si nou tou senpleman mete referans li a nil, Lè sa a, nou pral pèdi enfòmasyon sou subtree a ki gen rasin se ne sa a. Metòd pou retire pyebwa yo divize an twa ka.

Premye ka. Ne yo dwe retire pa gen okenn timoun.

Si ne yo dwe efase pa gen okenn timoun, sa vle di ke li se yon fèy. Se poutèt sa, ou ka tou senpleman mete leftChild oswa rightChild jaden paran li a nil.

Dezyèm ka. Ne pou retire a gen yon sèl pitit

Ka sa a tou pa trè difisil. Ann tounen nan egzanp nou an. Sipoze nou bezwen efase yon eleman ki gen kle 14. Dakò ke depi li se pitit dwat nan yon ne ak kle 10, Lè sa a, nenpòt nan pitit pitit li yo (nan ka sa a, youn nan dwa) pral gen yon kle ki pi gran pase 10, kidonk ou ka fasilman "koupe" li nan pye bwa a, epi konekte paran an dirèkteman ak pitit la nan ne ke yo te efase, i.e. konekte ne ak kle 10 a ne 13. Sitiyasyon an ta sanble si nou ta dwe efase yon ne ki se pitit gòch paran li. Reflechi sou li pou tèt ou - yon analoji egzak.

Twazyèm ka. Node gen de pitit

Ka ki pi difisil. Ann pran yon gade nan yon nouvo egzanp.

Binè Tree oswa ki jan yo prepare yon pye bwa rechèch binè

Chèche yon siksesè

Ann di nou bezwen efase ne ak kle a 25. Ki moun pou nou mete nan plas li? Youn nan disip li yo (desandan oswa desandan desandan) dwe vin siksesè(moun ki pral pran plas la nan ne la retire).

Ki jan ou fè konnen ki moun ki ta dwe siksesè a? Entwisyon, sa a se ne nan pye bwa a ki gen kle se pwochen pi gwo nan ne ke yo te retire. Algorithm la se jan sa a. Ou bezwen ale nan pitit dwat li (toujou nan youn nan dwa, paske li te deja di ke kle siksesè a pi gran pase kle a nan ne ke yo te efase), ak Lè sa a, ale nan chèn nan timoun gòch nan dwa sa a. pitit. Nan egzanp lan, nou dwe ale nan ne la ak kle 35, ak Lè sa a, desann chèn nan pitit gòch li yo nan fèy la - nan ka sa a, chèn sa a konsiste sèlman nan ne la ak kle 30. Fè egzateman pale, nou ap chèche pou ne ki pi piti a nan seri nœuds ki pi gran pase ne ki vle a.

Binè Tree oswa ki jan yo prepare yon pye bwa rechèch binè

Kòd metòd rechèch siksesè:

    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;
    }

Kòd konplè metòd efase a:

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;
    }

Konpleksite a ka apwoksimatif nan O(log(n)).

Jwenn maksimòm/minimòm nan yon pye bwa

Li evidan, ki jan yo jwenn valè minimòm / maksimòm nan pye bwa a - ou bezwen sekans ale nan chèn nan eleman gòch / dwa nan pye bwa a, respektivman; lè ou rive nan fèy la, li pral eleman nan minimòm / maksimòm.

    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;
    }

Konpleksite - O(log(n))

Bypass simetrik

Traversal se yon vizit nan chak ne nan pye bwa a yo nan lòd yo fè yon bagay ak li.

Rekursif simetrik algorithm travèse:

  1. Fè yon aksyon sou pitit gòch la
  2. Fè yon aksyon ak tèt ou
  3. Fè yon aksyon sou timoun nan dwa

Kòd:

    public void inOrder(Node<T> current) {
        if (current != null) {
            inOrder(current.getLeftChild());
            System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
            inOrder(current.getRightChild());
        }
    }

Konklizyon

Finalman! Si mwen pa t eksplike yon bagay oswa mwen pa gen okenn kòmantè, Lè sa a, mwen ap tann nan kòmantè yo. Kòm te pwomèt la, isit la se kòd la konplè.

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

Dejenerasyon nan O(n)

Anpil nan nou ka remake: e si ou fè pye bwa a vin dezekilib? Pou egzanp, mete nœuds nan pye bwa a ak kle ogmante: 1,2,3,4,5,6 ... Lè sa a, pye bwa a pral yon ti jan okoumansman de yon lis lye. Ak repons lan se wi, pye bwa a pral pèdi estrikti pyebwa li yo, e pakonsekan efikasite nan aksè done. Konpleksite nan rechèch, ensèsyon, ak sipresyon operasyon yo pral vin menm jan ak sa yo ki nan yon lis lye: O(n). Sa a se youn nan pi enpòtan, nan opinyon mwen, dezavantaj nan pye bwa binè.

Se sèlman itilizatè ki anrejistre ki ka patisipe nan sondaj la. Enskri, tanpri.

Mwen pa sou Habré depi byen lontan, e mwen ta renmen konnen ki atik sou ki sijè ou ta renmen wè plis?

  • Estrikti done yo

  • Algoritm (DP, recursion, konpresyon done, elatriye)

  • Aplikasyon nan estrikti done ak algoritm nan lavi reyèl

  • Pwogramasyon aplikasyon android nan Java

  • Programmation Java aplikasyon Web

2 itilizatè yo te vote. 1 itilizatè te absteni.

Sous: www.habr.com

Add nouvo kòmantè