🥇Binary Tree atanapi kumaha nyiapkeun tangkal milarian binér

Prelude

Artikel ieu ngeunaan tangkal pilarian binér. Kuring nembe nulis artikel ngeunaan komprési data ku métode Huffman. Di dinya kuring henteu merhatikeun tangkal binér, sabab cara milarian, nyelapkeun, ngahapus henteu relevan. Ayeuna kuring mutuskeun pikeun nulis artikel ngeunaan tangkal. Sugan urang mimitian.

Tangkal mangrupikeun struktur data anu diwangun ku titik-titik anu dihubungkeun ku sisi-sisi. Urang tiasa nyarios yén tangkal mangrupikeun kasus khusus tina grafik. Ieu conto tangkal:

Ieu lain tangkal pilarian binér! Sagalana aya dina cut!

Terminologi

Akar

Akar tangkal mangrupa titik pangluhurna. Dina conto, ieu titik A. Dina tangkal, ngan hiji jalur bisa ngakibatkeun ti akar kana sagala titik séjén! Kanyataanna, sagala titik bisa dianggap salaku akar subtree pakait jeung titik ieu.

Kolot/turunan

Kabéh titik iwal akar boga persis hiji ujung ngarah nepi ka titik sejen. Titik luhureun titik ayeuna disebut kolot titik ieu. Titik anu aya di handapeun anu ayeuna sareng dihubungkeun sareng éta disebut katurunan titik ieu. Hayu urang nyandak conto. Candak titik B, teras indungna janten titik A, sareng anakna janten titik D, E, sareng F.

lambaran

Titik nu teu boga anak disebut daun tangkal. Dina conto, titik D, E, F, G, I, J, K bakal daun.

Ieu terminologi dasar. Konsep séjén bakal dibahas engké. Janten, tangkal binér mangrupikeun tangkal anu masing-masing titik bakal gaduh teu langkung ti dua anak. Sakumaha anu ditebak, tangkal tina conto moal binér, sabab titik B sareng H gaduh langkung ti dua murangkalih. Ieu conto tangkal binér:

Titik tangkal tiasa ngandung inpormasi naon waé. Tangkal pamilarian binér nyaéta tangkal binér anu ngagaduhan sipat-sipat ieu:

Duanana subtrees kénca jeung katuhu mangrupakeun tangkal pilarian binér.
Sadaya titik dina subtree kénca titik X gaduh nilai konci data kirang ti nilai konci data titik X sorangan.
Sadaya titik subtree katuhu tina titik X gaduh nilai konci data langkung ageung atanapi sami sareng nilai konci data titik X sorangan.

konci - sababaraha karakteristik titik (contona, nomer). Koncina diperyogikeun supados tiasa mendakan unsur tangkal anu cocog sareng konci ieu. conto tangkal pilarian binér:

view tangkal

Nalika kuring ngiringan, kuring bakal ngalebetkeun sababaraha potongan kode (panginten teu lengkep) pikeun ningkatkeun pamahaman anjeun. Kodeu lengkep bakal aya dina tungtung tulisan.

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

Unggal titik boga dua barudak (éta rada mungkin nu leftChild jeung/atawa rightChild barudak bakal null). Anjeun meureun ngarti yén dina hal ieu data angka nyaéta data nu disimpen dina titik; konci - konci titik.

Urang terang cangreud, ayeuna hayu urang ngobrolkeun masalah-masalah anu mendesak ngeunaan tangkal. Di dieu jeung di handap, kecap "tangkal" bakal hartosna konsép tangkal pilarian binér. Struktur tangkal binér:

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

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

Salaku widang kelas, urang ngan butuh akar tangkal, sabab tina akar, ngagunakeun getLeftChild () jeung getRightChild () métode, anjeun bisa meunang ka sagala titik tangkal.

Algoritma tangkal

Поиск

Hayu urang nyebutkeun anjeun boga tangkal diwangun. Kumaha mendakan unsur anu nganggo konci konci? Anjeun kedah sacara berurutan ngalih tina akar ka handap tangkal sareng ngabandingkeun nilai konci sareng konci titik salajengna: upami konci langkung handap tina konci titik salajengna, teras angkat ka turunan kénca titik, upami langkung - ka katuhu, lamun kenop sarua - titik nu dipikahoyong kapanggih! Kodeu relevan:

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

Upami arus janten nol, maka iterasi parantos dugi ka tungtung tangkal (dina tingkat konseptual, anjeun aya dina tempat anu henteu aya dina tangkal - anak daun).

Mertimbangkeun efisiensi tina algoritma pilarian dina tangkal saimbang (tangkal nu titik nu disebarkeun leuwih atawa kurang merata). Mangka efisiensi pilarian bakal O(log(n)), sarta logaritma dasar 2. Tempo: lamun aya n elemen dina tangkal saimbang, mangka ieu ngandung harti yén bakal aya log(n) dasar 2 tingkat tangkal. Sarta dina pilarian, pikeun hiji hambalan siklus, Anjeun turun hiji tingkat.

ngasupkeun

Upami anjeun parantos ngartos hakekat milarian, maka anjeun moal sesah ngartos sisipan. Anjeun ngan perlu turun ka daun tangkal (nurutkeun aturan turunan dijelaskeun dina pilarian) jeung jadi turunan na - kénca atawa katuhu, gumantung kana konci. Palaksanaan:

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

Dina hal ieu, salian ti titik ayeuna, perlu pikeun nyimpen informasi ngeunaan indungna titik ayeuna. Nalika ayeuna janten null, variabel indungna bakal ngandung lambaran anu urang peryogikeun.
Efisiensi sisipan écés bakal sarua jeung nu pilarian - O(log(n)).

Ngahapus

Ngahapus mangrupikeun operasi anu paling rumit anu kedah dilakukeun ku tangkal. Ieu jelas yén mimitina eta bakal diperlukeun pikeun manggihan unsur nu urang bade cabut. Tapi lajeng naon? Upami urang ngan saukur nyetél rujukanna kana nol, maka urang bakal leungit inpormasi ngeunaan subtree anu akarna titik ieu. Métode panyabutan tangkal dibagi kana tilu kasus.

Kasus kahiji. Node nu bakal dipiceun teu boga anak.

Upami simpul anu badé dipupus teu gaduh anak, hartosna éta daun. Ku alatan éta, anjeun ngan saukur tiasa nyetél widang leftChild atanapi rightChild indungna ka null.

Kasus kadua. Pucuk anu bakal dipiceun ngagaduhan anak hiji

Kasus ieu ogé henteu hésé pisan. Hayu urang balik deui ka conto urang. Anggap urang kudu mupus unsur kalawan konci 14. Satuju yén saprak éta anak katuhu tina titik kalawan konci 10, lajeng salah sahiji turunan na (dina hal ieu, katuhu) bakal boga konci leuwih gede ti 10, jadi Anjeun bisa kalayan gampang "motong" eta tina tangkal, tur sambungkeun indungna langsung ka anak titik nu keur dihapus, i.e. sambungkeun titik kalayan konci 10 mun titik 13. kaayaan bakal sarupa lamun urang kudu mupus titik nu mangrupakeun anak kénca indungna. Pikirkeun éta pikeun diri anjeun - analogi anu pasti.

Kasus katilu. Node gaduh dua murangkalih

Kasus anu paling hese. Hayu urang nempo conto anyar.

Pilarian pikeun panerusna

Hayu urang nyebutkeun urang kudu miceun titik kalayan konci 25. Saha urang kudu nempatkeun dina tempatna? Salah sahiji pengikutna (turunan atawa turunan turunan) kudu jadi panerusna(anu bakal ngagentos titik anu dipiceun).

Kumaha anjeun terang saha anu kedah janten panerusna? Sacara intuitif, ieu mangrupikeun titik dina tangkal anu koncina mangrupikeun panggedena salajengna tina titik anu dipiceun. Algoritma nyaéta kieu. Anjeun kedah angkat ka anak katuhuna (salawasna ka katuhu, sabab parantos nyarios yén konci panerusna langkung ageung tibatan konci node anu dihapus), teras ngalangkungan ranté anak kénca katuhu ieu. anaking. Dina conto, urang kudu indit ka titik kalayan konci 35, lajeng turun ranté anak kénca na kana daun - dina hal ieu, ranté ieu ngan diwangun ku titik kalayan konci 30. Tegesna, urang pilari. titik pangleutikna dina susunan titik leuwih gede ti titik nu dipikahoyong.

Kodeu métode pilarian panerusna:

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

Kodeu lengkep metode ngahapus:

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

Pajeulitna tiasa dideukeutan ka O(log(n)).

Manggihan maksimum / minimum dina tangkal

Jelas, kumaha carana manggihan nilai minimum / maksimum dina tangkal - Anjeun kudu sequentially ngaliwatan ranté unsur kénca / katuhu tangkal, masing-masing; mun anjeun meunang ka daun, eta bakal minimum / unsur maksimum.

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

Kompleksitas - O(log(n))

Bypass simetris

Traversal nyaéta kunjungan ka unggal titik tangkal pikeun ngalakukeun hiji hal sareng éta.

Algoritma traversal simetris rekursif:

Jieun hiji aksi dina anak kénca
Jieun hiji aksi kalawan diri
Jieun hiji aksi dina anak katuhu

Kode:

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

kacindekan

Tungtungna! Upami kuring henteu ngajelaskeun hiji hal atanapi gaduh koméntar, maka kuring ngantosan dina koméntar. Salaku jangji, ieu kode lengkep.

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

Degenerasi ka O(n)

Seueur anu anjeun perhatikeun: kumaha upami anjeun ngajantenkeun tangkal henteu saimbang? Contona, nempatkeun titik dina tangkal kalayan ngaronjatna konci: 1,2,3,4,5,6 ... Lajeng tangkal bakal rada reminiscent tina daptar numbu. Na enya, tangkal bakal leungit struktur tangkal na, sarta ku kituna efisiensi aksés data. Pajeulitna operasi pilarian, sisipan, jeung ngahapus bakal jadi sarua jeung daptar numbu: O(n). Ieu mangrupikeun salah sahiji anu paling penting, dina pamanggih kuring, kalemahan tangkal binér.

Ngan pamaké nu kadaptar bisa ilubiung dina survey. Daptar, Punten.

Kuring geus lila teu di Habré, jeung Abdi hoyong terang naon artikel dina jejer naon anjeun hoyong ningali deui?

Struktur Data
Algoritma (DP, rekursi, komprési data, jsb.)
Aplikasi struktur data sareng algoritma dina kahirupan nyata
Pemrograman aplikasi android di Java
Pemrograman Aplikasi Wéb Java

2 pamaké milih. 1 pamaké abstained.

Sumber: www.habr.com

Tangkal binér atanapi kumaha nyiapkeun tangkal milarian binér