Apakah kaedah untuk melaksanakan pepohon carian binari dalam python

WBOY
Lepaskan: 2023-05-11 08:40:13
ke hadapan
1224 orang telah melayarinya

Pengenalan kepada pokok

Pokok adalah berbeza daripada senarai terpaut atau jadual cincang Ia adalah struktur data bukan linear yang dibahagikan kepada pokok binari, pokok carian binari, B-pokok, B+ pokok, pokok merah-hitam, dll.

Tree ialah struktur data, iaitu himpunan perhubungan hierarki yang terdiri daripada n nod terhad. Jika anda menggunakan gambar untuk mewakilinya, anda dapat melihat bahawa ia kelihatan seperti pokok terbalik. Oleh itu, kami secara kolektif memanggil jenis struktur data ini sebagai pokok, dengan akar di bahagian atas dan daun di bahagian bawah. Pokok am mempunyai ciri-ciri berikut:

  • Setiap nod mempunyai 0 atau lebih nod anak

  • Nod tanpa nod induk dipanggil root Nod

  • Setiap nod bukan akar mempunyai dan hanya mempunyai satu nod induk

  • Setiap nod anak boleh dibahagikan kepada berbilang anak bercabang

Takrif pokok binari ialah: setiap nod mempunyai paling banyak dua nod anak. Iaitu, setiap nod hanya boleh mempunyai empat situasi berikut:

  • Kedua-dua subpokok kiri dan subpokok kanan kosong

  • Hanya yang kiri subtree exists Tree

  • Hanya subtree kanan wujud

  • Kedua-dua subtree kiri dan subtree kanan wujud

Pokok carian binari

Pokok carian binari juga dipanggil pokok pengisihan binari Ia sama ada pokok kosong atau pokok binari dengan sifat berikut:

  • Jika. subpokok kirinya tidak kosong, maka nilai semua nod pada subpokok kiri adalah kurang daripada nilai nod akar Jika subpokok kanannya tidak kosong, maka nilai semua nod pada subpokok kanan adalah lebih besar daripada nilai nod akar. Python:

  • 1. Gunakan kelas dan fungsi rekursif untuk melaksanakan
  • Dengan mentakrifkan kelas nod, termasuk nilai nod, subnod kiri dan kanan serta atribut lain, dan kemudian menggunakan fungsi rekursif untuk melaksanakan penyisipan, carian, pemadaman dan operasi lain. Contoh kod adalah seperti berikut:

    class Node:
        def __init__(self, data):
            self.data = data
            self.left = None
            self.right = None
    
    class BST:
        def __init__(self):
            self.root = None
    
        def insert(self, value):
            if self.root is None:
                self.root = Node(value)
            else:
                self._insert(value, self.root)
    
        def _insert(self, value, node):
            if value < node.data:
                if node.left is None:
                    node.left = Node(value)
                else:
                    self._insert(value, node.left)
            elif value > node.data:
                if node.right is None:
                    node.right = Node(value)
                else:
                    self._insert(value, node.right)
    
        def search(self, value):
            if self.root is None:
                return False
            else:
                return self._search(value, self.root)
    
        def _search(self, value, node):
            if node is None:
                return False
            elif node.data == value:
                return True
            elif value < node.data:
                return self._search(value, node.left)
            else:
                return self._search(value, node.right)
    
        def delete(self, value):
            if self.root is None:
                return False
            else:
                self.root = self._delete(value, self.root)
    
        def _delete(self, value, node):
            if node is None:
                return node
            elif value < node.data:
                node.left = self._delete(value, node.left)
            elif value > node.data:
                node.right = self._delete(value, node.right)
            else:
                if node.left is None and node.right is None:
                    del node
                    return None
                elif node.left is None:
                    temp = node.right
                    del node
                    return temp
                elif node.right is None:
                    temp = node.left
                    del node
                    return temp
                else:
                    temp = self._find_min(node.right)
                    node.data = temp.data
                    node.right = self._delete(temp.data, node.right)
            return node
    
        def _find_min(self, node):
            while node.left is not None:
                node = node.left
            return node
    Salin selepas log masuk
  • 2 Gunakan senarai untuk melaksanakan

dengan menggunakan senarai untuk menyimpan elemen pepohon carian binari, dan kemudian melaksanakan sisipan, carian dan pemadaman. melalui hubungan kedudukan elemen dalam senarai Tunggu operasi. Contoh kod adalah seperti berikut:

class BST:
    def __init__(self):
        self.values = []

    def insert(self, value):
        if len(self.values) == 0:
            self.values.append(value)
        else:
            self._insert(value, 0)

    def _insert(self, value, index):
        if value < self.values[index]:
            left_child_index = 2 * index + 1
            if left_child_index >= len(self.values):
                self.values.extend([None] * (left_child_index - len(self.values) + 1))
            if self.values[left_child_index] is None:
                self.values[left_child_index] = value
            else:
                self._insert(value, left_child_index)
        else:
            right_child_index = 2 * index + 2
            if right_child_index >= len(self.values):
                self.values.extend([None] * (right_child_index - len(self.values) + 1))
            if self.values[right_child_index] is None:
                self.values[right_child_index] = value
            else:
                self._insert(value, right_child_index)

    def search(self, value):
        if value in self.values:
            return True
        else:
            return False

    def delete(self, value):
        if value not in self.values:
            return False
        else:
            index = self.values.index(value)
            self._delete(index)
            return True

    def _delete(self, index):
        left_child_index = 2 * index + 1
        right_child_index = 2 * index + 2
        if left_child_index < len(self.values) and self.values[left_child_index] is not None:
            self._delete(left_child_index)
        if right_child_index < len(self.values) and self.values[right_child_index] is not None:
            self
Salin selepas log masuk

3 Gunakan kamus untuk melaksanakan

di mana kunci kamus mewakili nilai nod, dan nilai kamus ialah kamus yang mengandungi sebelah kiri. dan nod anak kanan. Contoh kod adalah seperti berikut:

def insert(tree, value):
    if not tree:
        return {value: {}}
    elif value < list(tree.keys())[0]:
        tree[list(tree.keys())[0]] = insert(tree[list(tree.keys())[0]], value)
    else:
        tree[list(tree.keys())[0]][value] = {}
    return tree

def search(tree, value):
    if not tree:
        return False
    elif list(tree.keys())[0] == value:
        return True
    elif value < list(tree.keys())[0]:
        return search(tree[list(tree.keys())[0]], value)
    else:
        return search(tree[list(tree.keys())[0]].get(value), value)

def delete(tree, value):
    if not search(tree, value):
        return False
    else:
        if list(tree.keys())[0] == value:
            if not tree[list(tree.keys())[0]]:
                del tree[list(tree.keys())[0]]
            elif len(tree[list(tree.keys())[0]]) == 1:
                tree[list(tree.keys())[0]] = list(tree[list(tree.keys())[0]].values())[0]
            else:
                min_key = min(list(tree[list(tree.keys())[0]+1].keys()))
                tree[min_key] = tree[list(tree.keys())[0]+1][min_key]
                tree[min_key][list(tree.keys())[0]] = tree[list(tree.keys())[0]]
                del tree[list(tree.keys())[0]]
        elif value < list(tree.keys())[0]:
            tree[list(tree.keys())[0]] = delete(tree[list(tree.keys())[0]], value)
        else:
            tree[list(tree.keys())[0]][value] = delete(tree[list(tree.keys())[0]].get(value), value)
    return tree
Salin selepas log masuk

Memandangkan kamus tidak tersusun, pelaksanaan ini mungkin menyebabkan pepohon carian binari menjadi tidak seimbang, menjejaskan kecekapan operasi sisipan, carian dan pemadaman.

4. Gunakan tindanan untuk melaksanakan

Menggunakan tindanan (Timbunan) boleh melaksanakan pepohon carian binari yang mudah, yang boleh melaksanakan operasi sisipan, carian, pemadaman dan lain-lain melalui lelaran. Proses pelaksanaan khusus adalah seperti berikut:

Tentukan kelas nod, termasuk nilai nod, subnod kiri dan kanan serta atribut lain.

Tentukan tindanan dan mula-mula tolak nod akar pada tindanan.

  • Apabila tindanan tidak kosong, keluarkan elemen atas tindanan dan kendalikan padanya: jika nilai yang hendak dimasukkan kurang daripada nilai nod semasa, masukkan nilai ke disisipkan sebagai nod anak kiri, dan tolak nod anak kiri ke tindanan jika nilai yang akan dimasukkan lebih besar daripada nilai nod semasa, masukkan nilai yang akan dimasukkan sebagai nod anak kanan, dan tolak nod anak kanan; ke dalam timbunan; jika nilai yang akan ditemui atau dipadam adalah sama dengan nilai nod semasa, Kemudian kembalikan atau padamkan nod.

  • Selepas operasi selesai, teruskan ambil nod seterusnya daripada tindanan dan kendalikan sehingga tindanan kosong.

  • Perlu diingatkan bahawa dalam pelaksanaan ini, disebabkan penggunaan tindanan untuk menyimpan proses melintasi pokok, ia mungkin mengakibatkan penggunaan memori yang tinggi. Di samping itu, disebabkan oleh ciri-ciri tindanan, pelaksanaan ini hanya boleh menyokong traversal pertama mendalam (Depth-First Search, DFS) dan tidak boleh menyokong carian breadth-first (BFS).

  • Berikut ialah contoh pseudokod:
  • class Node:
        def __init__(self, data):
            self.data = data
            self.left = None
            self.right = None
    
    def insert(root, value):
        if not root:
            return Node(value)
        stack = [root]
        while stack:
            node = stack.pop()
            if value < node.data:
                if node.left is None:
                    node.left = Node(value)
                    break
                else:
                    stack.append(node.left)
            elif value > node.data:
                if node.right is None:
                    node.right = Node(value)
                    break
                else:
                    stack.append(node.right)
    
    def search(root, value):
        stack = [root]
        while stack:
            node = stack.pop()
            if node.data == value:
                return True
            elif value < node.data and node.left:
                stack.append(node.left)
            elif value > node.data and node.right:
                stack.append(node.right)
        return False
    
    def delete(root, value):
        if root is None:
            return None
        if value < root.data:
            root.left = delete(root.left, value)
        elif value > root.data:
            root.right = delete(root.right, value)
        else:
            if root.left is None:
                temp = root.right
                del root
                return temp
            elif root.right is None:
                temp = root.left
                del root
                return temp
            else:
                temp = root.right
                while temp.left is not None:
                    temp = temp.left
                root.data = temp.data
                root.right = delete(root.right, temp.data)
        return root
    Salin selepas log masuk

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

Label berkaitan:
sumber:yisu.com
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan