Bagaimana untuk melaksanakan pepohon carian binari dalam Python

Binary Search Tree (BST) ialah algoritma carian berdasarkan pepohon binari. Cirinya ialah nilai dalam subpokok kiri setiap nod dalam pokok adalah lebih kecil daripada nilai nod ini, manakala nilai dalam subpohon kanan lebih besar daripada nilai nod ini. Oleh itu, kerumitan masa operasi carian dan sisipan BST ialah O(logN).

Kaedah melaksanakan pepohon carian binari dalam Python agak mudah, kerana Python mempunyai dua struktur data terbina dalam, senarai dan kamus, yang kedua-duanya boleh digunakan untuk melaksanakan pepohon binari. Di sini kami akan menerangkan cara melaksanakan pepohon carian binari menggunakan senarai.

Pertama, kita perlu mentakrifkan kelas Nod untuk mewakili nilai, subpokok kiri dan subpokok kanan setiap nod:

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

Seterusnya, kita boleh menentukan kelas Pokok carian binari, yang mengandungi dua kaedah: masukkan dan cari. Dalam kaedah sisipan, kita mulakan dari nod akar dan bandingkan nilai nod satu demi satu Jika nilai yang baru dimasukkan adalah lebih kecil daripada nilai nod semasa, teruskan mencari di subpohon kiri, jika tidak, cari. dalam subpokok kanan. Apabila subpokok kiri (atau kanan) nod didapati kosong, ini bermakna nod yang akan dimasukkan harus diletakkan pada kedudukan ini.

class BinarySearchTree:
    def __init__(self):
        self.root = None
    
    def insert(self, value):
        new_node = Node(value)
        if self.root is None:
            self.root = new_node
        else:
            current_node = self.root
            while True:
                if value <= current_node.value:
                    if current_node.left is None:
                        current_node.left = new_node
                        break
                    else:
                        current_node = current_node.left
                else:
                    if current_node.right is None:
                        current_node.right = new_node
                        break
                    else:
                        current_node = current_node.right
    
    def search(self, value):
        current_node = self.root
        while current_node is not None:
            if value == current_node.value:
                return True
            elif value < current_node.value:
                current_node = current_node.left
            else:
                current_node = current_node.right
        return False

Kini, kita boleh mencipta pepohon dan memasukkan berbilang nod, dan kemudian menguji fungsi carian:

bst = BinarySearchTree()
bst.insert(9)
bst.insert(3)
bst.insert(12)
bst.insert(1)
bst.insert(4)
bst.insert(10)
bst.insert(15)

print(bst.search(4))  # True
print(bst.search(7))  # False

Seperti yang anda lihat, untuk pepohon carian binari ini, apabila kita mencari 4 , mengembalikan Benar; dan apabila kita mencari 7, ia mengembalikan Salah, menunjukkan bahawa 7 tiada dalam pokok.

Apabila melaksanakan pepohon carian binari, anda perlu memberi perhatian kepada beberapa isu. Pertama, kerumitan masa operasi penyisipan dan carian bergantung pada ketinggian pokok, jadi dalam operasi praktikal, adalah sangat penting untuk mengekalkan ketinggian pokok sekecil mungkin. Kedua, untuk set data yang besar, pepohon carian binari mungkin menjadi tidak seimbang (iaitu, menjadi lebih seperti senarai daripada pepohon), menghasilkan carian yang lebih perlahan, jadi algoritma yang lebih maju seperti pepohon carian binari seimbang diperlukan.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan pepohon carian binari dalam Python. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!