Memahami Pokok Carian Binari (BST)

Saya sedang menyelesaikan beberapa masalah berkaitan pokok carian binari dan fikir ia mungkin menarik untuk menyemak semula ingatan saya dan berkongsi apa yang saya pelajari dengan pengikut saya! Jadi begini:

Apakah itu Pokok Carian Binari (BST)

Pokok Carian Binari (BST) ialah struktur data asas dalam sains komputer yang membolehkan carian, pemasukan dan pemadaman data yang cekap. Ia adalah struktur berasaskan pokok di mana setiap nod mempunyai paling banyak dua anak, dan anak kiri sentiasa lebih kecil daripada nod induk, manakala anak kanan adalah lebih besar.

Ciri-ciri Utama BST

1. Pencarian Cekap: Dengan kerumitan masa O(log n) untuk pokok seimbang.

2. Struktur Dinamik: Nod boleh ditambah atau dialih keluar secara dinamik.

3. Perwakilan Hierarki: Berguna dalam perwakilan data hierarki, seperti sistem fail atau salasilah keluarga.

---

Mari kita selami pelaksanaan praktikal Pokok Carian Binari menggunakan TypeScript.

class Node {
    value: number;
    left: Node | null;
    right: Node | null;

    constructor(value: number) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    root: Node | null;

    constructor() {
        this.root = null;
    }

    insert(value: number): void {
        const newNode = new Node(value);
        if (this.root === null) {
            this.root = newNode;
            return;
        }

        let currentNode = this.root;
        while (true) {
            if (value < currentNode.value) {
                if (currentNode.left === null) {
                    currentNode.left = newNode;
                    return;
                }
                currentNode = currentNode.left;
            } else {
                if (currentNode.right === null) {
                    currentNode.right = newNode;
                    return;
                }
                currentNode = currentNode.right;
            }
        }
    }

    contains(value: number): boolean {
        let currentNode = this.root;

        while (currentNode !== null) {
            if (value === currentNode.value) return true;
            currentNode = value < currentNode.value ? currentNode.left : currentNode.right;
        }

        return false;
    }

    // In-order Traversal: Left -> Root -> Right
    inOrderTraversal(node: Node | null = this.root): void {
        if (node !== null) {
            this.inOrderTraversal(node.left);
            console.log(node.value);
            this.inOrderTraversal(node.right);
        }
    }
}

// Usage
const bst = new BinarySearchTree();
bst.insert(47);
bst.insert(21);
bst.insert(76);
bst.insert(18);
bst.insert(52);
bst.insert(82);

console.log("Contains 21:", bst.contains(21)); // true
console.log("Contains 99:", bst.contains(99)); // false

console.log("In-order Traversal:");
bst.inOrderTraversal();

---

Gambarajah Perwakilan BST

Beginilah rupa Pokok Carian Binari selepas memasukkan nilai 47, 21, 76, 18, 52, 82:

---

Bagaimana ia Berfungsi

1. Sisipkan: Nilai baharu diletakkan berdasarkan perbandingan. Nilai yang lebih kecil pergi ke kiri, dan nilai yang lebih besar pergi ke kanan.

2. Cari (Mengandungi): Traverse kiri atau kanan bergantung pada nilai sehingga nod ditemui atau traversal berakhir pada nod null.

3. Traversal: Traversal tertib melawat nod dalam tertib diisih (Kiri -> Root -> Kanan).

---

Mengapa Menggunakan Pokok Carian Binari?

1. Pencarian Cekap: Pencarian dalam BST boleh menjadi sangat cekap apabila pokok itu seimbang.

2. Saiz Dinamik: Anda boleh menambah atau mengalih keluar elemen tanpa perlu mengubah saiz tatasusunan atau menganjak elemen.

3. Data Isih: Traversals menyediakan data dalam tertib diisih, berguna dalam senario seperti baris gilir keutamaan dan pangkalan data dalam memori.

---

Kes Tepi yang Perlu Diingati

1. Pendua: BST standard tidak mengendalikan nilai pendua secara lalai. Anda mungkin perlu melaksanakan logik untuk membenarkan atau menolak pendua, seperti menyimpan kiraan dalam setiap nod atau melangkau sisipan pendua.

2. Pokok Tidak Seimbang: Jika nilai dimasukkan dalam tertib diisih (cth., 1, 2, 3, 4, ...), BST menjadi condong dan merosot kepada senarai terpaut dengan kerumitan masa O(n) untuk operasi. Menggunakan BST pengimbangan diri (cth., pokok AVL, pokok Merah-Hitam) membantu mengurangkan isu ini.

3. Pokok Kosong: Sentiasa semak kes di mana pokok itu kosong (iaitu, this.root === null) untuk mengelakkan ralat masa jalan semasa operasi seperti mengandungi atau traversal.

4. Nod Tepi: Dalam senario seperti mengalih keluar nod, pertimbangkan kes tepi seperti nod dengan hanya seorang anak, tiada anak atau menjadi nod akar.

5. Prestasi: Jika set data anda besar atau terdapat dalam ketulan diisih, pertimbangkan untuk mengimbangi semula atau menggunakan struktur data yang lebih sesuai untuk carian yang cekap.

Untuk memastikan kecekapan, BST harus kekal seimbang. Pokok yang tidak seimbang boleh menurunkan prestasi kepada O(n). Pertimbangkan untuk menggunakan pokok pengimbangan diri seperti AVL atau Pokok Merah-Hitam untuk prestasi yang dioptimumkan secara konsisten. Saya akan membincangkan tentang pokok-pokok lain dalam siaran kemudian.

---

Kes Penggunaan BST dalam Aplikasi Perisian

Pokok Carian Perduaan (BST) lebih daripada sekadar struktur data yang anda temui dalam buku teks—ia mempunyai banyak aplikasi dunia sebenar! Berikut ialah beberapa cara praktikal BST digunakan dalam sains komputer:

• Pangkalan Data dan Pengindeksan: BST Seimbang (seperti AVL atau Pokok Merah-Hitam) sering berada di belakang tabir dalam pengindeksan pangkalan data. Mereka menjadikan pertanyaan julat dan carian sangat cekap.

• Data Isih Dalam Memori: Perlu memastikan data diisih semasa menambah dan mencari secara dinamik? BST adalah pilihan anda. Fikirkan analitis atau sistem pemantauan masa nyata.

• Jadual Simbol dalam Penyusun: Penyusun bergantung pada BST untuk melaksanakan jadual simbol untuk menyimpan dan mengakses pengecam dan atributnya dengan pantas.

• Autolengkap dan Penyemak Ejaan: Pernah terfikir bagaimana autolengkap berfungsi? Variasi BST, seperti Ternary Search Trees, digunakan untuk menyusun kamus perkataan dengan cekap.

• Penjadualan Keutamaan: Walaupun timbunan adalah lebih biasa, BST juga boleh digunakan dalam sistem penjadualan dinamik di mana keutamaan sentiasa berubah.

• Data Geografi (GIS): BST membantu dalam sistem GIS dengan menyimpan dan mendapatkan semula data spatial—seperti mencari lokasi berdekatan atau menapis mengikut julat.

• Mampatan Data: Pengekodan Huffman, bahagian penting algoritma pemampatan data, menggunakan jenis pepohon binari khas untuk menetapkan kod panjang boleh ubah kepada simbol data.

• Sistem Permainan: BST membolehkan papan pendahulu dan papan skor dinamik dengan memastikan markah disusun dan mendapatkan semula kedudukan dalam masa nyata.

• Rangkaian dan Penghalaan: Jadual penghalaan kadangkala bergantung pada struktur seperti BST untuk menentukan laluan yang cekap untuk pemindahan data.

• Sistem Kawalan Versi: Sistem seperti Git menggunakan struktur seperti pokok (berinspirasikan BST) untuk mengurus komitmen dan versi dengan cekap dalam Directed Acyclic Graph (DAG).

BST ada di mana-mana, daripada menjanakan alatan yang kami gunakan setiap hari kepada menyelesaikan masalah pengiraan yang kompleks. Agak hebat, bukan?

Tetapi adalah penting untuk mengambil kira had dan kes kelebihannya. Memahami nuansa ini boleh membantu anda mereka bentuk sistem yang lebih cekap dan boleh dipercayai.

Adakah anda menghadapi sebarang cabaran atau penyelesaian yang menarik semasa bekerja dengan BST? Mari kita bincangkan di bawah! ?

Atas ialah kandungan terperinci Memahami Pokok Carian Binari (BST). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!