🥇Binary Tree atau cara menyediakan pokok carian binari

Foreplay

Artikel ini adalah mengenai pokok carian binari. Saya baru-baru ini menulis artikel tentang pemampatan data dengan kaedah Huffman. Di sana saya tidak benar-benar memberi perhatian kepada pokok binari, kerana kaedah mencari, memasukkan, memadam tidak relevan. Sekarang saya memutuskan untuk menulis artikel tentang pokok. Mungkin kita akan mulakan.

Pokok ialah struktur data yang terdiri daripada nod yang disambungkan oleh tepi. Kita boleh mengatakan bahawa pokok ialah kes khas graf. Berikut adalah contoh pokok:

Ini bukan pokok carian binari! Segala-galanya di bawah pemotongan!

Terminologi

Root

Akar pokok ialah nod paling atas. Dalam contoh, ini ialah nod A. Dalam pokok, hanya satu laluan boleh membawa dari akar ke mana-mana nod lain! Malah, mana-mana nod boleh dianggap sebagai punca subtree yang sepadan dengan nod ini.

Ibu bapa/anak

Semua nod kecuali akar mempunyai tepat satu tepi yang menuju ke nod lain. Nod di atas nod semasa dipanggil ibu bapa nod ini. Nod yang terletak di bawah nod semasa dan disambungkan kepadanya dipanggil keturunan nod ini. Mari kita ambil contoh. Ambil nod B, maka induknya akan menjadi nod A, dan anak-anaknya akan menjadi nod D, E dan F.

Daun

Nod yang tidak mempunyai anak dipanggil daun pokok. Dalam contoh, nod D, E, F, G, I, J, K akan menjadi daun.

Ini adalah istilah asas. Konsep lain akan dibincangkan kemudian. Jadi, pokok binari ialah pokok di mana setiap nod akan mempunyai tidak lebih daripada dua anak. Seperti yang anda duga, pokok dari contoh tidak akan menjadi binari, kerana nod B dan H mempunyai lebih daripada dua anak. Berikut adalah contoh pokok binari:

Nod pokok boleh mengandungi sebarang maklumat. Pokok carian binari ialah pokok binari yang mempunyai sifat berikut:

Kedua-dua subpokok kiri dan kanan ialah pokok carian binari.
Semua nod subpokok kiri nod X sewenang-wenangnya mempunyai nilai kunci data kurang daripada nilai kunci data nod X itu sendiri.
Semua nod subpokok kanan nod X sewenang-wenangnya mempunyai nilai kunci data lebih besar daripada atau sama dengan nilai kunci data nod X itu sendiri.

Kunci - beberapa ciri nod (contohnya, nombor). Kunci diperlukan untuk dapat mencari elemen pokok yang sepadan dengan kunci ini. Contoh pokok carian binari:

pemandangan pokok

Semasa saya meneruskan, saya akan memasukkan beberapa (mungkin tidak lengkap) keping kod untuk meningkatkan pemahaman anda. Kod penuh akan berada di penghujung artikel.

Pokok itu terdiri daripada nod. Struktur nod:

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

Setiap nod mempunyai dua anak (ada kemungkinan anak kiri dan/atau anak kanan akan menjadi batal). Anda mungkin faham bahawa dalam kes ini data nombor ialah data yang disimpan dalam nod; kunci - kunci nod.

Kami mengetahui simpulannya, sekarang mari kita bercakap tentang masalah mendesak mengenai pokok. Di sini dan di bawah, perkataan "pokok" bermaksud konsep pokok carian binari. Struktur pokok binari:

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

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

Sebagai medan kelas, kita hanya memerlukan akar pokok, kerana daripada akar, menggunakan kaedah getLeftChild() dan getRightChild(), anda boleh sampai ke mana-mana nod pokok.

Algoritma Pokok

carian

Katakan anda mempunyai pokok yang dibina. Bagaimana untuk mencari elemen dengan kunci kekunci? Anda perlu bergerak secara berurutan dari akar ke bawah pokok dan bandingkan nilai kunci dengan kunci nod seterusnya: jika kunci kurang daripada kunci nod seterusnya, kemudian pergi ke keturunan kiri nod, jika lebih - ke kanan, jika kekunci adalah sama - nod yang dikehendaki ditemui! Kod yang berkaitan:

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

Jika arus menjadi batal, maka lelaran telah mencapai penghujung pokok (pada tahap konsep, anda berada di tempat yang tidak wujud di dalam pokok - anak daun).

Pertimbangkan kecekapan algoritma carian pada pokok seimbang (pokok di mana nod diagihkan lebih kurang sama rata). Kemudian kecekapan carian ialah O(log(n)), dan logaritma asas 2. Lihat: jika terdapat n elemen dalam pokok seimbang, maka ini bermakna akan terdapat log(n) asas 2 aras pokok itu. Dan dalam carian, untuk satu langkah kitaran, anda turun satu tahap.

memasukkan

Jika anda telah memahami intipati carian, maka tidak sukar bagi anda untuk memahami sisipan. Anda hanya perlu turun ke daun pokok (mengikut peraturan keturunan yang diterangkan dalam carian) dan menjadi keturunannya - kiri atau kanan, bergantung pada kunci. Pelaksanaan:

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

Dalam kes ini, sebagai tambahan kepada nod semasa, adalah perlu untuk menyimpan maklumat tentang induk nod semasa. Apabila arus menjadi nol, pembolehubah induk akan mengandungi helaian yang kami perlukan.
Kecekapan sisipan jelas akan sama dengan carian - O(log(n)).

Pemadaman

Pemadaman ialah operasi paling kompleks yang perlu dilakukan dengan pokok. Adalah jelas bahawa pertama sekali adalah perlu untuk mencari elemen yang akan kami alih keluar. Tetapi kemudian apa? Jika kita hanya menetapkan rujukannya kepada null, maka kita akan kehilangan maklumat tentang subpokok yang akarnya ialah nod ini. Kaedah penyingkiran pokok dibahagikan kepada tiga kes.

Kes pertama. Nod yang akan dialih keluar tidak mempunyai anak.

Jika nod yang akan dipadamkan tidak mempunyai anak, ia bermakna ia adalah daun. Oleh itu, anda hanya boleh menetapkan medan leftChild atau rightChild bagi induknya kepada null.

Kes kedua. Nod yang akan dialih keluar mempunyai seorang anak

Kes ini juga tidaklah susah sangat. Mari kita kembali kepada contoh kita. Katakan kita perlu memadamkan elemen dengan kunci 14. Setuju bahawa kerana ia adalah anak kanan nod dengan kunci 10, maka mana-mana keturunannya (dalam kes ini, yang betul) akan mempunyai kunci yang lebih besar daripada 10, jadi anda boleh "memotong" dengan mudah dari pokok, dan menyambungkan induk terus kepada anak nod yang dipadamkan, i.e. sambungkan nod dengan kekunci 10 ke nod 13. Situasi akan sama jika kita terpaksa memadamkan nod yang merupakan anak kiri induknya. Fikirkan sendiri - analogi yang tepat.

Kes ketiga. Node mempunyai dua anak

Kes yang paling sukar. Mari kita lihat contoh baharu.

Cari pengganti

Katakan kita perlu mengeluarkan nod dengan kekunci 25. Siapakah yang akan kita letakkan di tempatnya? Salah seorang pengikutnya (keturunan atau keturunan keturunan) mesti menjadi pengganti(orang yang akan mengambil tempat nod yang dikeluarkan).

Bagaimana anda tahu siapa yang sepatutnya menjadi pengganti? Secara intuitif, ini ialah nod dalam pokok yang kuncinya adalah yang terbesar seterusnya daripada nod yang dialih keluar. Algoritmanya adalah seperti berikut. Anda perlu pergi ke anak kanannya (sentiasa ke kanan, kerana telah dikatakan bahawa kunci pengganti lebih besar daripada kunci nod yang dipadamkan), dan kemudian pergi melalui rantaian anak kiri kanan ini anak. Dalam contoh, kita mesti pergi ke nod dengan kunci 35, dan kemudian turun rantai anak kirinya ke daun - dalam kes ini, rantai ini hanya terdiri daripada nod dengan kunci 30. Tegasnya, kami sedang mencari nod terkecil dalam set nod yang lebih besar daripada nod yang dikehendaki.

Kod kaedah carian pengganti:

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

Kod lengkap kaedah padam:

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

Kerumitan boleh dianggarkan kepada O(log(n)).

Mencari maksimum/minimum dalam pokok

Jelas sekali, bagaimana untuk mencari nilai minimum / maksimum dalam pokok - anda perlu secara berurutan melalui rantaian unsur kiri / kanan pokok itu, masing-masing; apabila anda sampai ke daun, ia akan menjadi elemen minimum/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;
    }

Kerumitan - O(log(n))

Pintasan simetri

Traversal ialah lawatan ke setiap nod pokok untuk melakukan sesuatu dengannya.

Algoritma lintasan simetri rekursif:

Buat tindakan pada anak kiri
Buat tindakan dengan diri sendiri
Buat tindakan pada anak yang betul

Kod:

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

Kesimpulan

Akhirnya! Jika saya tidak menjelaskan sesuatu atau mempunyai sebarang komen, maka saya menunggu dalam ulasan. Seperti yang dijanjikan, berikut adalah kod lengkapnya.

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 kepada O(n)

Ramai daripada anda mungkin perasan: bagaimana jika anda membuat pokok itu menjadi tidak seimbang? Sebagai contoh, letakkan nod dalam pepohon dengan kekunci yang semakin meningkat: 1,2,3,4,5,6... Kemudian pepohon itu akan agak mengingatkan senarai terpaut. Dan ya, pokok itu akan kehilangan struktur pokoknya, dan oleh itu kecekapan akses data. Kerumitan operasi carian, sisipan dan pemadaman akan menjadi sama seperti senarai terpaut: O(n). Ini adalah salah satu yang paling penting, pada pendapat saya, kelemahan pokok binari.

Hanya pengguna berdaftar boleh mengambil bahagian dalam tinjauan. Log masuk, Sama-sama.

Saya sudah lama tidak menggunakan Habré, dan saya ingin tahu artikel tentang topik apakah yang anda ingin lihat lebih lanjut?

Struktur Data
Algoritma (DP, rekursi, pemampatan data, dll.)
Aplikasi struktur data dan algoritma dalam kehidupan sebenar
Memprogramkan aplikasi android dalam Java
Pengaturcaraan Aplikasi Web Java

2 pengguna mengundi. 1 pengguna berpantang.

Sumber: www.habr.com

Pokok Binari atau bagaimana untuk menyediakan pokok carian binari