🥇Binary Tsob Ntoo lossis yuav ua li cas npaj tsob ntoo nrhiav binary

Ua Neej Tsaus Ntuj

Kab lus no yog hais txog binary nrhiav ntoo. Tsis ntev los no kuv tau sau ib tsab xov xwm txog Cov ntaub ntawv compression los ntawm Huffman txoj kev. Nyob ntawd kuv tsis tau them sai sai rau binary ntoo, vim hais tias txoj kev tshawb nrhiav, ntxig, tshem tawm tsis cuam tshuam. Tam sim no kuv txiav txim siab sau ib tsab xov xwm txog ntoo. Tej zaum peb yuav pib.

Ib tsob ntoo yog cov ntaub ntawv qauv uas muaj cov nodes txuas nrog cov npoo. Peb tuaj yeem hais tias tsob ntoo yog qhov tshwj xeeb ntawm daim duab. Nov yog ib qho piv txwv ntoo:

Qhov no tsis yog binary nrhiav ntoo! Txhua yam yog nyob rau hauv kev txiav!

Terminology

Hauv paus

Tsob ntoo cag yog lub saum toj kawg nkaus node. Hauv qhov piv txwv, qhov no yog node A. Hauv tsob ntoo, tsuas yog ib txoj hauv kev tuaj yeem coj los ntawm cov hauv paus mus rau lwm qhov node! Qhov tseeb, txhua lub node tuaj yeem suav tias yog lub hauv paus ntawm cov ntoo subtree sib haum rau cov node.

Niam txiv/ xeeb ntxwv

Tag nrho cov nodes tsuas yog lub hauv paus muaj raws nraim ib tug ntug coj mus rau lwm qhov. Cov node saum toj node tam sim no hu ua niam txiv qhov node. Ib lub node nyob hauv qab qhov tam sim no thiab txuas nrog nws hu ua xeeb ntxwv qhov node. Cia peb ua piv txwv. Coj node B, ces nws niam nws txiv yuav node A, thiab nws cov me nyuam yuav nodes D, E, thiab F.

Nplooj

Ib lub pob uas tsis muaj menyuam yog hu ua nplooj ntoo. Hauv qhov piv txwv, nodes D, E, F, G, I, J, K yuav yog nplooj.

Qhov no yog qhov yooj yim terminology. Lwm lub tswv yim yuav tham tom qab. Yog li, ib tsob ntoo binary yog tsob ntoo uas txhua tus ntawm yuav tsis muaj ntau tshaj ob tus menyuam. Raws li koj tau twv, tsob ntoo los ntawm qhov piv txwv yuav tsis yog binary, vim cov nodes B thiab H muaj ntau tshaj ob tug me nyuam. Nov yog ib qho piv txwv ntawm tsob ntoo binary:

Cov kab ntawm tsob ntoo tuaj yeem muaj cov ntaub ntawv. Ib tsob ntoo nrhiav binary yog tsob ntoo binary uas muaj cov khoom nram qab no:

Ob sab laug thiab sab xis subtrees yog binary nrhiav ntoo.
Tag nrho cov nodes ntawm sab laug subtree ntawm ib tug arbitrary node X muaj cov ntaub ntawv tseem ceeb qhov tseem ceeb tsawg tshaj li cov ntaub ntawv tseem ceeb tus nqi ntawm node X nws tus kheej.
Tag nrho cov nodes ntawm txoj cai subtree ntawm ib tug arbitrary node X muaj cov ntaub ntawv tseem ceeb qhov tseem ceeb tshaj los yog sib npaug rau tus nqi ntawm cov ntaub ntawv tseem ceeb ntawm node X nws tus kheej.

Ntsiab - ib co yam ntxwv ntawm node (piv txwv li, tus lej). Tus yuam sij yog xav tau kom thiaj li nrhiav tau lub ntsiab ntawm tsob ntoo uas tus yuam sij no sib raug. Binary nrhiav ntoo piv txwv:

tsob ntoo saib

Raws li kuv mus, kuv yuav suav nrog qee qhov (tej zaum tsis tiav) cov lej txhawm rau txhawm rau txhim kho koj txoj kev nkag siab. Tag nrho cov cai yuav nyob rau ntawm qhov kawg ntawm tsab xov xwm.

Ntoo yog ua los ntawm cov nodes. Node qauv:

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

Txhua lub pob muaj ob tug me nyuam (nws yog ib qho ua tau tias cov me nyuam laug thiab/los yog cov me nyuam txoj cai yuav tsis muaj). Tej zaum koj yuav nkag siab tias qhov no cov ntaub ntawv tus lej yog cov ntaub ntawv khaws cia hauv qhov node; key-node key.

Peb xam tawm lub pob, tam sim no cia peb tham txog cov teeb meem nias txog ntoo. Hauv qab no, lo lus "tsob ntoo" yuav txhais tau tias lub tswvyim ntawm tsob ntoo nrhiav binary. Binary ntoo qauv:

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

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

Raws li cov chav kawm, peb tsuas yog xav tau cov cag ntoo, vim tias los ntawm cov hauv paus, siv getLeftChild() thiab getRightChild() txoj kev, koj tuaj yeem mus rau txhua qhov ntawm tsob ntoo.

Ntoo algorithms

Поиск

Wb hais tias koj muaj ib tsob ntoo ua. Yuav ua li cas nrhiav tau lub ntsiab nrog tus yuam sij tseem ceeb? Koj yuav tsum tau txav mus los ntawm cov hauv paus hauv qab tsob ntoo thiab sib piv tus nqi ntawm qhov tseem ceeb nrog tus yuam sij ntawm lub tom ntej node: yog tias tus yuam sij tsawg dua tus yuam sij ntawm lub tom ntej node, ces mus rau sab laug xeeb leej xeeb ntxwv ntawm node, yog tias ntau dua - mus rau sab xis, yog tias cov yuam sij sib npaug - pom cov node xav tau! Relevant 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;
}

Yog tias tam sim no dhau los ua tsis tiav, tom qab ntawd iteration tau mus txog qhov kawg ntawm tsob ntoo (ntawm lub tswv yim theem, koj nyob hauv qhov chaw tsis muaj nyob hauv tsob ntoo - me nyuam ntawm nplooj).

Xav txog qhov ua tau zoo ntawm kev tshawb nrhiav algorithm ntawm tsob ntoo sib npaug (ib tsob ntoo uas cov nodes faib ntau dua lossis tsawg dua sib npaug). Tom qab ntawd qhov kev tshawb nrhiav kev ua haujlwm yuav yog O(log(n)), thiab lub hauv paus 2 logarithm. Saib: yog tias muaj n cov ntsiab lus hauv cov ntoo sib npaug, qhov no txhais tau tias yuav muaj log(n) hauv paus 2 theem ntawm tsob ntoo. Thiab hauv kev tshawb nrhiav, rau ib kauj ruam ntawm lub voj voog, koj mus rau ib theem.

ntxig

Yog tias koj tau nkag siab qhov tseem ceeb ntawm kev tshawb nrhiav, ces nws yuav tsis yooj yim rau koj kom nkag siab txog qhov ntxig. Koj tsuas yog yuav tsum tau nqes mus rau nplooj ntoo (raws li cov cai ntawm qhovntsej thiaj tsis mob tau piav qhia hauv kev tshawb nrhiav) thiab dhau los ua nws cov xeeb ntxwv - sab laug lossis sab xis, nyob ntawm tus yuam sij. Kev siv:

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

Nyob rau hauv tas li ntawd mus rau lub tam sim no node, nws yog tsim nyog los khaws cov ntaub ntawv hais txog cov niam txiv ntawm lub tam sim no node. Thaum tam sim no dhau los ua null, qhov hloov pauv niam txiv yuav muaj cov ntawv peb xav tau.
Qhov kev ua kom pom tseeb yuav pom tseeb zoo ib yam li qhov kev tshawb nrhiav - O(log(n)).

Rho tawm

Kev tshem tawm yog txoj haujlwm nyuaj tshaj plaws uas yuav tsum tau ua nrog tsob ntoo. Nws yog qhov tseeb tias ua ntej nws yuav tsim nyog los nrhiav lub caij uas peb yuav tshem tawm. Tab sis yog li cas? Yog tias peb tsuas yog teeb tsa nws siv rau null, ces peb yuav poob cov ntaub ntawv hais txog lub subtree uas nws lub hauv paus yog qhov node. Txoj kev tshem tsob ntoo muab faib ua peb kis.

Thawj rooj plaub. Cov node kom tshem tawm tsis muaj menyuam.

Yog cov node yuav deleted tsis muaj me nyuam, nws txhais tau hais tias nws yog nplooj. Yog li ntawd, koj tuaj yeem teeb tsa sab laugChild lossis rightChild teb ntawm nws niam nws txiv rau null.

Qhov thib ob. Cov node yuav raug tshem tawm muaj ib tug me nyuam

Cov ntaub ntawv no kuj tsis nyuaj heev. Cia peb rov qab mus rau peb qhov piv txwv. Piv txwv tias peb yuav tsum rho tawm ib lub ntsiab lus nrog tus yuam sij 14. Pom zoo tias txij li nws yog tus menyuam txoj cai ntawm node nrog tus yuam sij 10, ces ib qho ntawm nws cov xeeb leej xeeb ntxwv (qhov no, qhov yog) yuav muaj tus yuam sij ntau dua 10, yog li koj. tuaj yeem yooj yim "txiav" los ntawm tsob ntoo, thiab txuas tus niam txiv ncaj qha rau tus menyuam ntawm lub pob raug tshem tawm, i.e. txuas lub node nrog tus yuam sij 10 mus rau ntawm 13. Qhov xwm txheej yuav zoo sib xws yog tias peb yuav tsum tshem tawm ib qho ntawm tus menyuam sab laug ntawm nws niam nws txiv. Xav txog nws rau koj tus kheej - ib qho piv txwv tseeb.

Qhov thib peb. Node muaj ob tug me nyuam

Qhov nyuaj tshaj plaws. Cia wb mus saib ib qho piv txwv tshiab.

Nrhiav ib tug successor

Wb hais tias peb yuav tsum tau tshem lub node nrog tus yuam sij 25. Peb yuav muab leej twg nyob rau hauv nws qhov chaw? Ib tug ntawm nws cov thwjtim (cov xeeb leej xeeb ntxwv lossis cov xeeb ntxwv ntawm cov xeeb leej xeeb ntxwv) yuav tsum ua tus ua tiav(tus uas yuav coj qhov chaw ntawm qhov tshem tawm ntawm node).

Ua li cas koj thiaj paub tias leej twg yuav tsum ua tus kav? Intuitively, qhov no yog qhov ntawm tsob ntoo uas nws tus yuam sij yog qhov loj tshaj plaws tom ntej los ntawm cov node raug tshem tawm. Lub algorithm yog raws li nram no. Koj yuav tsum mus rau nws tus me nyuam txoj cai (ib txwm mus rau sab xis, vim nws twb tau hais tias tus yuam sij ntawm tus neeg ua tiav yog ntau dua li tus yuam sij ntawm lub pob raug tshem tawm), thiab tom qab ntawd mus hla cov saw ntawm cov menyuam sab laug ntawm txoj cai no. tus menyuam. Hauv qhov piv txwv, peb yuav tsum mus rau ntawm lub pob nrog tus yuam sij 35, thiab tom qab ntawd mus rau hauv cov saw hlau ntawm nws cov menyuam sab laug mus rau nplooj - qhov no, cov saw no tsuas yog muaj cov node nrog tus yuam sij 30. nruj me ntsis hais lus, peb tab tom nrhiav. qhov tsawg tshaj plaws ntawm cov txheej ntawm cov nodes ntau dua li qhov xav tau node.

Successor search method code:

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

Tag nrho cov cai ntawm txoj kev rho tawm:

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

Qhov nyuaj tuaj yeem kwv yees li O(log(n)).

Nrhiav qhov siab tshaj plaws / tsawg kawg hauv ib tsob ntoo

Pom tseeb, yuav ua li cas thiaj nrhiav tau qhov tsawg kawg nkaus / siab tshaj tus nqi ntawm tsob ntoo - koj yuav tsum tau ua raws li cov saw hlau ntawm sab laug / sab xis ntawm tsob ntoo, feem; thaum koj mus rau nplooj ntawv, nws yuav yog qhov tsawg kawg nkaus / qhov siab tshaj plaws.

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

Complexity - O(log(n))

Symmetric Bypass

Traversal yog mus ntsib txhua qhov ntawm tsob ntoo kom ua ib yam dab tsi nrog nws.

Recursive symmetrical traversal algorithm:

Ua ib qho kev txiav txim ntawm tus me nyuam sab laug
Ua ib qho kev txiav txim nrog koj tus kheej
Ua ib qho kev txiav txim rau tus me nyuam txoj cai

Txoj Cai:

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

xaus

Thaum kawg! Yog tias kuv tsis tau piav qhia qee yam lossis muaj lus pom, ces kuv tos hauv cov lus. Raws li tau cog lus tseg, ntawm no yog cov lej tiav.

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

Degeneration rau O (n)

Ntau tus ntawm koj yuav tau pom: ua li cas yog tias koj ua rau tsob ntoo tsis sib npaug? Piv txwv li, muab cov nodes nyob rau hauv tsob ntoo nrog nce cov yuam sij: 1,2,3,4,5,6... Ces tsob ntoo yuav zoo li me ntsis reminiscent ntawm ib daim ntawv txuas. Thiab yog, tsob ntoo yuav plam nws cov qauv ntoo, thiab yog li qhov ua tau zoo ntawm cov ntaub ntawv nkag. Qhov nyuaj ntawm kev tshawb nrhiav, ntxig, thiab tshem tawm cov haujlwm yuav dhau los ua tib yam li cov npe sib txuas: O(n). Qhov no yog ib qho tseem ceeb tshaj plaws, hauv kuv lub tswv yim, qhov tsis zoo ntawm cov ntoo binary.

Tsuas yog cov neeg siv sau npe tuaj yeem koom nrog hauv daim ntawv ntsuam xyuas. Kos npe rau hauvthov.

Kuv tsis tau nyob rau Habré ntev heev, thiab kuv xav paub cov ntawv dab tsi ntawm cov ncauj lus dab tsi koj xav pom ntxiv?

Cov qauv ntaub ntawv
Algorithms (DP, recursion, cov ntaub ntawv compression, thiab lwm yam)
Kev siv cov ntaub ntawv tsim thiab algorithms hauv lub neej tiag tiag
Programming android applications hauv Java
Java Web Application Programming

2 cov neeg siv pov npav. 1 tus neeg siv abstained.

Tau qhov twg los: www.habr.com

Binary Tsob Ntoo los yog yuav ua li cas npaj ib tsob ntoo nrhiav binary