Apakah kaedah untuk melaksanakan pepohon carian binari dalam python

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

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

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

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

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!