Pohon Pencarian Biner (BST)

Struktur Data dan Algoritma di Python

Miriam Antona

Software engineer

Definisi

Subtree kiri suatu simpul:
- nilai lebih kecil dari simpul itu sendiri
Subtree kanan suatu simpul:
- nilai lebih besar dari simpul itu sendiri
Subtree kiri dan kanan harus berupa pohon pencarian biner

Representasi skematis pohon pencarian biner.

Implementasi

class TreeNode:  
  def __init__(self, data, left=None, right=None):
    self.data = data
    self.left_child = left
    self.right_child = right

class BinarySearchTree:
  def __init__(self):
    self.root = None

Pencarian

Cari 72

Representasi skematis pohon pencarian biner.

Pencarian

Cari 72

Representasi skematis pohon pencarian biner; simpul akar berwarna kuning.

Pencarian

Cari 72

Representasi skematis pohon pencarian biner; simpul akar dan subtree kiri berwarna abu-abu. Simpul pertama subtree kanan berwarna kuning.

Pencarian

Cari 72

Representasi skematis pohon pencarian biner. Subtree kiri dari akar terakhir dan akar terakhir berwarna abu-abu. Akar baru berwarna kuning.

Pencarian

Cari 72

Representasi skematis pohon pencarian biner; akar baru berwarna kuning dan simpul lain berwarna abu-abu.

Pencarian

Cari 72

Representasi skematis pohon pencarian biner; akar baru berwarna kuning dan simpul lain berwarna abu-abu. Simpul bernomor 72 disorot.

Pencarian

def search(self, search_value):

    current_node = self.root

    while current_node:

      if search_value == current_node.data:

        return True

      elif search_value < current_node.data:

        current_node = current_node.left_child

      else:

        current_node = current_node.right_child

    return False

Penyisipan

def insert(self, data):

  new_node = TreeNode(data)

  if self.root == None:

Representasi grafis simpul baru.

Penyisipan

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return

Representasi grafis simpul baru yang menjadi akar.

Penyisipan

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:

Representasi grafis simpul baru dan akar dengan anak kanan.

Penyisipan

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root

    while True:

      if data < current_node.data:

        if current_node.left_child == None:

Representasi grafis simpul baru dan akar dengan anak kanan. current_node adalah akar.

Penyisipan

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return

Representasi grafis akar dengan anak kanan dan kiri. current_node adalah akar. Simpul baru adalah anak kiri.

Penyisipan

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None: 
          current_node.left_child = new_node
          return
        else:

Representasi grafis simpul baru dan BST dengan beberapa elemen. current_node adalah akar.

Penyisipan

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None: 
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child

Representasi grafis simpul baru dan BST dengan beberapa elemen. current_node adalah anak kiri akar.

Penyisipan

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:

        if current_node.right_child == None:

Representasi grafis simpul baru dan BST dengan subtree kiri.

Penyisipan

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return

Representasi grafis BST dengan subtree kiri. Simpul baru kini menjadi anak kanan akar.

Penyisipan

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return
        else:

Representasi grafis simpul baru dan BST dengan beberapa elemen.

Penyisipan

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return
        else:
          current_node = current_node.right_child

Representasi grafis simpul baru dan BST dengan beberapa elemen. current_node adalah anak kanan akar.

Penyisipan

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return 
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return
        else:
          current_node = current_node.right_child

Representasi grafis simpul baru dan BST dengan beberapa elemen. current_node adalah anak kanan akar. Simpul baru adalah anak kiri current_node.

Penghapusan

Tanpa anak

Representasi grafis BST dengan beberapa elemen. Salah satu simpul berwarna merah karena akan dihapus. Simpul ini tidak memiliki anak.

Penghapusan

Tanpa anak
- hapus

Representasi grafis BST dengan beberapa elemen. Simpul yang akan dihapus telah hilang dari pohon.

Penghapusan

Satu anak

Representasi grafis BST dengan beberapa elemen. Salah satu simpul berwarna merah karena akan dihapus. Simpul ini memiliki anak kanan.

Penghapusan

Satu anak
- hapus
- hubungkan anak ke induk simpul

Representasi grafis BST dengan beberapa elemen. Simpul yang akan dihapus hilang dan akar menunjuk ke anak kanan simpul yang dihapus.

Penghapusan

Satu anak
- hapus
- hubungkan anak ke induk simpul

Representasi skematis pohon pencarian biner.

Penghapusan

Dua anak

Representasi grafis BST di mana simpul akar akan dihapus dan berwarna merah.

Penghapusan

Dua anak
- ganti dengan suksesor
  - simpul dengan nilai terkecil yang lebih besar dari nilai simpul
- cari suksesor:

Representasi grafis BST di mana simpul akar akan dihapus dan berwarna merah.

Penghapusan

Dua anak
- ganti dengan suksesor
  - simpul dengan nilai terkecil yang lebih besar dari nilai simpul
- cari suksesor:
  - kunjungi anak kanan

Representasi grafis BST di mana simpul akar akan dihapus dan berwarna merah. Anak kanan akar berwarna kuning.

Penghapusan

Dua anak
- ganti dengan suksesor
  - simpul dengan nilai terkecil yang lebih besar dari nilai simpul
- cari suksesor:
  - kunjungi anak kanan
  - terus kunjungi simpul kiri hingga akhir

Representasi grafis BST di mana simpul akar akan dihapus dan berwarna merah. Simpul lain berwarna kuning untuk mencari suksesor.

Penghapusan

Dua anak
- ganti dengan suksesor
  - simpul dengan nilai terkecil yang lebih besar dari nilai simpul
- cari suksesor:
  - kunjungi anak kanan
  - terus kunjungi simpul kiri hingga akhir

Representasi grafis BST di mana simpul akar akan dihapus dan berwarna merah. Simpul lain berwarna kuning untuk mencari suksesor.

Penghapusan

Dua anak
- ganti dengan suksesor
  - simpul dengan nilai terkecil yang lebih besar dari nilai simpul
- cari suksesor:
  - kunjungi anak kanan
  - terus kunjungi simpul kiri hingga akhir

Representasi grafis BST di mana simpul akar akan dihapus dan berwarna merah. Simpul lain berwarna kuning untuk mencari suksesor. Suksesor ditemukan: angka 13.

Penghapusan

Dua anak
- ganti dengan suksesor
  - simpul dengan nilai terkecil yang lebih besar dari nilai simpul
- cari suksesor:
  - kunjungi anak kanan
  - terus kunjungi simpul kiri hingga akhir

Representasi grafis BST. Simpul akar telah diganti dengan suksesor.

Penghapusan

Dua anak
- ganti dengan suksesor
  - simpul dengan nilai terkecil yang lebih besar dari nilai simpul
- cari suksesor:
  - kunjungi anak kanan
  - terus kunjungi simpul kiri hingga akhir
  - jika suksesor memiliki anak kanan:

Representasi grafis BST di mana simpul suksesor memiliki anak kanan.

Penghapusan

Dua anak
- ganti dengan suksesor
  - simpul dengan nilai terkecil yang lebih besar dari nilai simpul
- cari suksesor:
  - kunjungi anak kanan
  - terus kunjungi simpul kiri hingga akhir
  - jika suksesor memiliki anak kanan:
    - anak menjadi anak kiri dari induk suksesor.

Representasi grafis BST di mana simpul suksesor memiliki anak kanan. Anak suksesor menjadi anak kiri induk suksesor dan akar diganti dengan suksesor.

Kegunaan

Mengurutkan daftar secara efisien
Jauh lebih cepat mencari daripada array dan linked list
Jauh lebih cepat menyisipkan dan menghapus daripada array
Dipakai untuk membangun struktur data lanjutan:
- himpunan dinamis
- tabel lookup
- priority queue

Ayo berlatih!

Struktur Data dan Algoritma di Python