Pohon AVL: Panduan Lengkap dengan Implementasi Python

Ketidakseimbangan pada Binary Search Tree

Binary search tree (BST) adalah jenis pohon biner struktur data yang mengorganisasi data menggunakan aturan tertentu. Setiap node berisi nilai dan memiliki tautan ke maksimal dua node lain: anak kiri dan kanan. Pada BST, aturannya adalah nilai node anak kiri harus lebih kecil dari nilai node induknya, dan nilai node anak kanan harus lebih besar.

BST dapat sangat efisien untuk menemukan nilai tertentu karena memungkinkan kita menyingkirkan bagian besar pohon selama proses pencarian. Misalnya, jika kita mencari nilai satu pada pohon di atas, kita dapat mengabaikan semua node di sebelah kanan enam. Ini karena properti urutan menjamin bahwa semua nilai tersebut lebih besar dari enam.

Idealnya, setiap node membagi data menjadi dua, sehingga separuh nilai dieliminasi pada tiap langkah turun pohon. Ini menghasilkan pencarian yang sangat cepat. Namun, tergantung urutan penyisipan, kita bisa mendapatkan pohon yang tidak seimbang dan tidak membagi data secara efektif. Misalnya, menyisipkan nilai dari yang terkecil ke yang terbesar akan menghasilkan pohon linear, yang tidak lebih baik kinerjanya daripada sebuah daftar.

Apa Itu Pohon AVL

Pohon AVL adalah binary search tree dengan properti tambahan berikut:

Untuk setiap node, tinggi subtree kiri dan kanan berbeda paling banyak satu.

Merinci definisi ini, subtree kiri dari sebuah node mencakup semua node di sebelah kirinya, sedangkan subtree kanan mencakup semua node di sebelah kanannya. Tinggi sebuah pohon didefinisikan sebagai panjang jalur terpanjang dari node akar (node paling atas) ke salah satu daun keturunannya (node tanpa anak).

Faktor keseimbangan sebuah node dihitung sebagai selisih tinggi antara subtree kiri dan subtree kanannya:

balance(N) = height(subtree kiri N) - height(subtree kanan N)

Sebagai contoh, balance(6) = 1 - 3 = -2.

Pada diagram, node 6 memiliki faktor keseimbangan -2, yang menunjukkan bahwa pohon tersebut tidak memenuhi kriteria pohon AVL. Agar sebuah pohon diklasifikasikan sebagai pohon AVL, faktor keseimbangan setiap node harus -1, 0, atau 1.

Mengapa Menggunakan Pohon AVL

Efisiensi kueri pada binary search tree bergantung pada tinggi pohon. Dalam skenario terburuk, jumlah node yang perlu diperiksa sama dengan tinggi pohon. Masalah utama pada BST adalah tinggi pohon dapat menyamai jumlah node, yang berarti sebuah kueri mungkin mengharuskan memeriksa setiap node.

Misalkan M(h) menyatakan jumlah minimum node yang diperlukan untuk ditambahkan ke sebuah binary search tree agar mencapai tinggi h. Untuk BST sederhana, kita mengamati bahwa M(h) = h, artinya kita dapat mencapai tinggi h hanya dengan h node. Ini menyiratkan bahwa tinggi sebuah BST dapat meningkat secara linear terhadap jumlah node, sehingga waktu kueri berbanding lurus dengan ukuran dataset.

Bukti bahwa pohon AVL memiliki tinggi logaritmik

Mari kita pertimbangkan jumlah minimum node, M(h), yang diperlukan untuk membuat pohon AVL dengan tinggi h. Karena ini adalah pohon AVL, perlu dicatat bahwa faktor keseimbangan setiap node hanya bisa -1, 0, atau 1.

Namun, dengan asumsi bahwa pohon memiliki jumlah node paling sedikit untuk mencapai tinggi h, akar tidak bisa memiliki keseimbangan 0. Jika iya, kita dapat menghapus satu node dari sisi kiri atau kanan untuk mendapatkan keseimbangan -1 atau 1, yang tetap menghasilkan pohon AVL yang valid.

Anggap keseimbangan akar adalah 1 (alasannya akan sama jika keseimbangannya -1). Ini menyiratkan bahwa pohon terstruktur sebagai berikut:

Di sisi lain, baik subtree kiri maupun kanan juga harus merupakan pohon AVL, masing-masing dengan jumlah node minimum untuk tinggi mereka (jika tidak, kita bisa menghapus node tambahan). Jumlah total node dalam pohon sama dengan 1 (untuk akar) ditambah jumlah node di subtree kiri dan jumlah node di subtree kanan.

M(h) = 1 + (node di L) + (node di R) = 1 + M(h - 1) + M(h - 2)

Seiring bertambahnya tinggi, kita perlu menambahkan lebih banyak node untuk mencapai tinggi tersebut. Maka:

M(h - 1) > M(h - 2)

Menggabungkan keduanya, kita dapat mengatakan bahwa:

M(h) = 1 + M(h - 1) + M(h - 2) > 1 + 2 × M(h - 2) > 2 × M(h - 2)

Kita dapat menerapkannya h/2 kali hingga mencapai M(1) = 1 atau M(2) = 2:

M(h) > 2 × M(h - 2) > 2 × 2 × M(h - 4) > 2 × 2 × 2 × M(h - 6) > … > 2(h/2)

Untuk kejelasan, gambar berikut menampilkan contoh khusus saat h = 7 dan h = 6:

Kita menyimpulkan bahwa jumlah minimum node dalam pohon AVL bertinggi h setidaknya 2(h/2):

M(h) > 2(h/2)

Dengan menerapkan logaritma basis dua pada kedua sisi, kita memperoleh:

log2(M(h)) > log2(2(h/2)) = h/2

Akibatnya, dengan mengalikan kedua sisi dengan dua, kita menyimpulkan bahwa tinggi paling besar dua kali logaritma basis-2 dari jumlah node:

2 × log2(M(h)) > h

Kita telah menunjukkan bahwa:

Tinggi pohon AVL yang berisi N node paling besar 2 × log2(N).

Ini menunjukkan bahwa kueri dalam pohon AVL hanya memerlukan pemeriksaan sebagian kecil dari dataset. Misalnya, dengan satu miliar entri, logaritmanya kira-kira 30, yang berarti bahkan dengan satu miliar data, hanya sekitar 60 titik data yang perlu diperiksa untuk menemukan satu entri spesifik. Ini merupakan peningkatan signifikan dibandingkan BST yang, dalam skenario terburuk, mengharuskan memeriksa seluruh satu miliar titik data.

Untuk pemahaman lebih mendalam tentang kompleksitas waktu algoritmik dan perbedaan antara kompleksitas linear dan logaritmik, lihat tulisan blog ini tentang Notasi Big-O dan Kompleksitas Waktu.

Menjaga Keseimbangan dengan Pohon AVL

Pohon AVL menjamin kueri cepat dengan menegakkan bahwa keseimbangan setiap node adalah -1, 0, atau 1. Untuk memastikan keseimbangan setiap node terjaga, kita perlu menyeimbangkan ulang pohon setelah menyisipkan nilai baru.

Penyisipan pada binary search tree dilakukan dengan mengikuti jalur dari akar ke bawah pohon. Kita pergi ke kiri saat nilai yang ingin kita sisipkan lebih kecil, dan ke kanan sebaliknya.

Sebuah penyisipan meningkatkan tinggi paling banyak satu. Jadi, jika properti keseimbangan tidak terpenuhi setelah penyisipan, berarti sebelumnya ada node dengan keseimbangan -1 yang kini menjadi -2, atau node dengan keseimbangan 1 yang kini menjadi 2. Kasus pertama terjadi pada contoh di atas.

Rotasi tunggal

Untuk mengembalikan keseimbangan, kita mengandalkan rotasi pohon. Rotasi kiri pada node A merestrukturisasi pohon dengan memutar A ke kiri, seperti ditunjukkan di bawah:

Pada diagram:

• BL merepresentasikan subtree kiri dari B
• BR adalah subtree kanan
• AL adalah subtree kiri dari A

Perhatikan bahwa setelah rotasi, urutan node tetap valid:

1. Node A lebih kecil dari B karena B sebelumnya adalah anak kanannya.
2. Node dalam BL lebih besar daripada A karena mereka berada di kanan A.
3. Node dalam AL lebih kecil daripada B karena mereka lebih kecil daripada A.

Rotasi kanan bekerja secara simetris dengan memutar A ke kanan.

Mari lihat contoh konkret dengan memperbaiki ketidakseimbangan pohon setelah menyisipkan 19 menggunakan rotasi kiri pada node 6.

Setelah penyisipan, kita akan memperbaiki ketidakseimbangan dengan memutar node yang memiliki keseimbangan -2 atau 2. Dalam kasus ini, faktor keseimbangan node 6 adalah -2, yang berarti pohon condong ke kanan, sehingga kita menerapkan rotasi kiri (berlawanan arah ketidakseimbangan). Jika sebaliknya keseimbangan bernilai 2, maka digunakan rotasi kanan.

Rotasi ganda

Pada contoh sebelumnya, pohon sepenuhnya condong ke kanan, sehingga satu rotasi kiri cukup untuk mengembalikan keseimbangan. Namun, dalam beberapa kasus, kita memiliki ketidakseimbangan tipe zig-zag di mana pohon condong ke satu sisi, tetapi subtree-nya condong ke sisi sebaliknya. Untuk melihat ini, mari kembali ke pohon semula sebelum kita menyisipkan 19 dan sisipkan 7 sebagai gantinya:

Dalam kasus ini, pohon masih condong ke kanan, tetapi subtree yang berakar di 10 condong ke kiri. Dalam kasus ini, pertama-tama kita perlu memutar node 10 ke kanan:

Perhatikan bahwa node B tidak memiliki anak kanan. Kami tetap menampilkannya dalam warna biru pada diagram untuk memudahkan visualisasi.

Setelah melakukan rotasi kanan, kita kembali ke kasus sebelumnya di mana rotasi kiri pada 6 akan memulihkan keseimbangan:

Cara Mengimplementasikan Pohon AVL di Python

Mari mulai dengan implementasi node.

Implementasi node

Setiap node pada pohon memiliki lima atribut:

• Nilai yang disimpannya (self.value)
• Node induk (self.parent)
• Anak kiri (self.left)
• Anak kanan (self.right)
• Tinggi subtree yang berakar pada node tersebut (self.height)

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

Kita menggunakan nilai None untuk merepresentasikan node yang hilang. Nilai default height diatur ke 1 karena pohon yang terdiri dari satu node memiliki tinggi 1.

Untuk memudahkan implementasi pohon, kita menambahkan beberapa metode ke kelas Node.

# Inside the Node class
  def left_height(self):
    # Get the heigth of the left subtree
    return 0 if self.left is None else self.left.height
  
  def right_height(self):
    # Get the height of the right subtree
    return 0 if self.right is None else self.right.height
  def balance_factor(self):
    # Get the balance factor
    return self.left_height() - self.right_height()
  def update_heigth(self):
    # Update the heigth of this node
    self.height = 1 + max(self.left_height(),self.right_height())
    
  def set_left(self, node):
    # Set the left child
    self.left = node
    if node is not None:
      node.parent = self
    self.update_heigth()
  
  def set_right(self, node):
    # Set the right child
    self.right = node
    if node is not None:
      node.parent = self
    self.update_heigth()
  def is_left_child(self):
    # Check whether this node is a left child
    return self.parent is not None and self.parent.left == self
  
  def is_right_child(self):
    # Check whether this node is a right child
    return self.parent is not None and self.parent.right == self

Perhatikan bahwa kita menggunakan metode .set_left() dan .set_right() untuk menetapkan anak kiri dan kanan. Alasan menggunakan metode ini, daripada langsung mengubah atribut self.left dan self.right, adalah karena setiap kali anak diubah, perlu juga memperbarui induk dari anak baru serta tinggi node.

Implementasi pohon AVL

Pohon AVL mempertahankan satu parameter, yaitu akar pohon, yang merupakan node paling atas.

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

Untuk menjaga keseimbangan pohon, kita perlu mengimplementasikan rotasi kiri dan kanan. Mari tinjau bagaimana rotasi kiri digambarkan pada diagram:

# Inside the AVLTree class
  
  def rotate_left(self, a):
    b = a.right
    # 1. The new right child of A becomes the left child of B
    a.set_right(b.left)
    # 2. The new left child of B becomes A
    b.set_left(a)
    return b # 3. Return B to replace A with it

Rotasi kanan diimplementasikan secara simetris:

# Inside the AVLTree class
  
  def rotate_right(self, a):
    b = a.left
    a.set_left(b.right)
    b.set_right(a)
    return b

Dengan rotasi, kita dapat menyeimbangkan ulang pohon. Sebuah node memerlukan penyeimbangan ulang ketika faktor keseimbangannya mencapai 2 (menandakan pohon condong ke kiri) atau -2 (menandakan pohon condong ke kanan). Secara keseluruhan, ada empat skenario yang perlu dipertimbangkan:

Kita mengimplementasikan keempat kasus tersebut dalam metode .rebalance().

# Inside the AVLTree class
  
  def rebalance(self, node):
    if node is None:
      # Empty tree, no rebalancing needed
      return None
    balance = node.balance_factor()
    if abs(balance) <= 1:
      # The node is already balanced, no rebalancing needed
      return node
    if balance == 2: 
      # Cases 1 and 2, the tree is leaning to the left
      if node.left.balance_factor() == -1: 
        # Case 2, we first do a left rotation
        node.set_left(self.rotate_left(node.left))
      return self.rotate_right(node)
    # Balance must be -2
    # Cases 3 and 4, the tree is leaning to the left
    if node.right.balance_factor() == 1:
      # Case 4, we first do a right rotation
      node.set_right(self.rotate_right(node.right)) 
    return self.rotate_left(node)

Perhatikan bahwa pada tiap kasus, metode mengembalikan akar dari subtree yang baru saja diseimbangkan. Akar subtree baru ini akan digunakan nanti untuk memperbarui anak-anak selama proses penyeimbangan.

Menambahkan node ke pohon AVL mirip dengan proses pada BST biasa, dengan tambahan pemulihan keseimbangan setelah node disisipkan. Untuk menambahkan node pada BST, kita mulai dari akar dan menelusuri ke bawah pohon. Pada setiap langkah, kita membandingkan nilai yang akan ditambahkan dengan nilai node saat ini. Jika nilainya lebih kecil, kita bergerak ke kiri; jika tidak, ke kanan. Saat turun, kita mencatat node induk agar dapat menyisipkan node baru sebagai anaknya.

Setelah kita mencapai node kosong, ada dua kasus:

1. Induk bernilai None yang berarti pohon kosong sehingga node baru menjadi akar pohon yang baru.
2. Kita menemukan induknya, sehingga perlu menetapkan node baru sebagai anak kiri atau kanan, tergantung pada nilai node.

# Inside the AVLTree class
  def add(self, value):
    self.size += 1
    parent = None
    current = self.root
    while current is not None:
      parent = current
      if value < current.value:
        # Value to insert is smaller than node value, go left
        current = current.left
      else:
        # Value to insert is larger than node value, go right
        current = current.right
    # We found the parent, create the new node
    new_node = Node(value, parent)
    # Case 1: The parent is None so the new node is the root
    if parent is None:
      self.root = new_node
    else:
      # Case 2: Set the new node as a child of the parent
      if value < parent.value:
        parent.left = new_node
      else:
        parent.right = new_node
    # After a new node is added, we need to restore balance
    self.restore_balance(new_node)

Satu-satunya perbedaan antara metode .add() pada BST dan pada pohon AVL terletak pada langkah terakhir. Ini melibatkan penelusuran kembali ke atas pohon dan menyeimbangkan ulang node, mulai dari node yang baru ditambahkan hingga akar, serta menyeimbangkan setiap node menggunakan metode .rebalance().

# Inside the AVLTree class
  def restore_balance(self, node):
    current = node
    # Go up the tree and rebalance left and right children
    while current is not None:
      current.set_left(self.rebalance(current.left))
      current.set_right(self.rebalance(current.right))
      current.update_heigth()
      current = current.parent
    self.root = self.rebalance(self.root)
    self.root.parent = None

Perhatikan bahwa metode .rebalance() tidak melakukan apa-apa saat node sudah seimbang—metode ini hanya mengembalikan node yang sama. Itulah sebabnya, saat naik ke atas pohon, kita dapat memanggilnya pada kedua sisi, meskipun hanya satu sisi yang mungkin tidak seimbang. Panggilan lainnya tidak mengubah pohon.

Ingat bahwa kita mengimplementasikan metode .rebalance() sehingga ia mengembalikan (berpotensi) akar baru dari subtree. Alasannya adalah agar kita bisa memperbarui anak kiri dan kanan dari node saat ini ketika naik memulihkan keseimbangan.

Diagram berikut menunjukkan langkah-langkah .restore_balance() saat naik ke atas pohon.

Pada contoh yang diberikan, pertama kita menambahkan node 8. Kemudian, proses pemulihan keseimbangan dimulai dari node ini dan bergerak naik ke atas pohon, memeriksa dan menyeimbangkan ulang anak kiri dan kanan dari setiap node yang ditemui. Ini berlanjut hingga mencapai node 10. Sampai titik ini, tidak ada pemanggilan metode .rebalance() yang berdampak karena node-node tetap seimbang.

Namun, saat mencapai node 10, terlihat bahwa anak kirinya, node 7, memiliki faktor keseimbangan -2, menunjukkan perlunya penyeimbangan ulang. Akibatnya, .rebalance(7) dipanggil, yang menghasilkan penggantian anak kiri node 10 dengan akar baru subtree kiri, yaitu node 8, sehingga memulihkan keseimbangan pohon.

Operasi Tambahan pada Pohon AVL

Selain menambah dan menghapus elemen sambil menjaga keseimbangan pohon, pohon AVL mendukung beberapa operasi penting lainnya.

Minimum dan maksimum

Karena sifat BST yang terurut, nilai minimum dapat ditemukan pada node paling kiri dari pohon, sedangkan nilai maksimum berada pada node paling kanan.

Kami mengimplementasikan dua fungsi pembantu yang mengidentifikasi node paling kiri dan paling kanan mulai dari node tertentu. Fungsi-fungsi ini berguna untuk memudahkan implementasi penghapusan node.

# Inside the AVLTree class
  
  def leftmost(self, starting_node):
    # Find the leftmost node from a given starting node
    previous = None
    current = starting_node
    while current is not None:
      previous = current
      current = current.left
    return previous
  def minimum(self):
    # Return the minimum value in the tree
    if self.root is None:
      raise Exception("Empty tree")
    return self.leftmost(self.root).value

# Inside the AVLTree class
 
  def rightmost(self, starting_node):
    # Find the rightmost node from a given starting node
    previous = None
    current = starting_node
    while current is not None:
      previous = current
      current = current.right
    return previous
  
  def maximum(self):
    # Fidn the maximum value in the tree
    if self.root is None:
      raise Exception("Empty tree")
    return self.rightmost(self.root).value

Contains

Untuk menentukan apakah sebuah pohon memuat nilai tertentu, kita memanfaatkan properti urutan pohon untuk memandu pencarian. Mulai dari akar, kita menelusuri ke kiri jika nilai yang dicari lebih kecil daripada node saat ini dan ke kanan jika lebih besar. Jika kita mencapai ujung pohon tanpa menemukan nilai yang diinginkan, itu menandakan bahwa nilai tersebut tidak ada di dalam pohon.

Untuk memudahkan proses ini, kami mengimplementasikan metode pembantu bernama .locate_node(). Metode ini berguna tidak hanya untuk pencarian, tetapi juga untuk operasi seperti menghapus nilai dari pohon. Selain itu, kami menggunakan metode .__contains__(), yang memungkinkan kita menggunakan operator in untuk mempermudah pemeriksaan keberadaan nilai dalam pohon.

# Inside the AVLTree class

  def locate_node(self, value):

    # Returns the node containing a given value or None if no

    # such node exists

    current = self.root

    while current is not None:

      if value == current.value:

        return current

      if value < current.value:

        current = current.left

      else:

        current = current.right

    return None

  def __contains__(self, value):

    node = self.locate_node(value)

    return node is not None

Penghapusan

Menghapus node pada pohon AVL bisa sangat menantang ketika node berada di tengah pohon. Jika node adalah daun, artinya tidak memiliki anak, kita dapat dengan mudah menghapusnya dengan mengatur penunjuk anak kiri atau kanan induknya ke None berdasarkan apakah node tersebut anak kiri atau kanan.

Kasus khusus muncul ketika node yang akan dihapus adalah akar pohon. Dalam skenario ini, kita dapat menghapus node dengan mengatur akar menjadi None.

# Inside the AVLTree class

  def delete_leaf(self, node):

    if node.parent is None:

      self.root = None

    elif node.is_left_child():

      node.parent.left = None

      node.parent = None

    else:

      node.parent.right = None

      node.parent = None

Untuk menghapus sebuah nilai dari pohon AVL, pertama-tama kita harus menemukan node yang berisi nilai tersebut menggunakan metode .locate_node(). Setelah node ditemukan, kita dapat menghapusnya dengan metode .delete_leaf() jika itu adalah node daun. Jika bukan node daun, penghapusan langsung akan mengganggu struktur pohon. Untuk mengatasinya, kita mencari node pengganti yang sesuai. Jika node yang akan dihapus memiliki anak kiri, kita memilih node paling kanan pada subtree kirinya. Pendekatan ini memastikan pohon mempertahankan struktur terurutnya.

Diagram di bawah ini mencontohkan penghapusan node 10 dari sebuah pohon. Karena memiliki anak kiri, kita menggantinya dengan node paling kanan pada subtree kiri. Setelah penggantian, penting untuk menyeimbangkan ulang pohon, mulai dari induk dari node yang baru digantikan.

Dalam contoh ini, node pengganti adalah node daun. Namun, jika node pengganti memiliki anak, perlu untuk menetapkan ulang mereka ke induk dari node pengganti. Karena node pengganti adalah node ekstrem (paling kiri atau paling kanan), ia hanya dapat memiliki satu anak. Oleh karena itu, penetapan ulang ini selalu memungkinkan.

# Inside the AVLTree class

  def delete(self, value):

    # Delete a value from the tree

    node = self.locate_node(value)

    if node is None:

      raise Exception("Value not stored in tree")

    replacement = None

    rebalance_node = node.parent

    if node.left is not None:

      # There's a left child so we replace with rightmost node

      replacement = self.rightmost(node.left)

      # Check if reparenting is needed

      if replacement.is_left_child():

        replacement.parent.set_left(replacement.left)

      else:

        replacement.parent.set_right(replacement.left)

    elif node.right is not None:

      # There's a right child so we replace with the leftmost node

      replacement = self.leftmost(node.right)

      # Check if reparenting is needed

      if replacement.is_left_child():

        replacement.parent.set_left(replacement.right)

      else:

        replacement.parent.set_right(replacement.right)

    if replacement:

      # We found a replacement so replace the value

      node.value = replacement.value

      rebalance_node = replacement.parent

    else:

      # No replacement so it means the node to delete is a leaf

      self.delete_leaf(node)

    if rebalance_node is not None:

      self.restore_balance(rebalance_node)

Kueri rentang

Kueri rentang melibatkan identifikasi semua nilai yang berada di antara dua nilai tertentu. Karena sifat pohon AVL yang terurut, kita dapat menemukan nilai-nilai ini secara efisien.

Untuk menemukan semua nilai dalam rentang yang ditentukan oleh batas bawah lb dan batas atas ub, kita menggunakan pendekatan rekursif untuk menelusuri pohon. Untuk setiap node yang ditemui, jika nilainya berada dalam rentang ini, kita memasukkannya ke hasil. Selanjutnya, kita telusuri subtree kiri dan kanan untuk melanjutkan pencarian.

Kita mengabaikan subtree kiri jika nilai node lebih kecil dari batas bawah karena semua nilai dalam subtree kiri lebih kecil dari nilai node. Demikian pula, kita mengabaikan subtree kanan jika nilai node lebih besar dari batas atas, karena semua nilai dalam subtree kanan akan lebih besar dari nilai node.

  def search(self, node, lb, ub, results):

    # Search for values between lower bound and upper bound

    if node is None:

      return

    if lb <= node.value and node.value <= ub:

      results.append(node.value)

    if node.value >= lb:

      self.search(node.left, lb, ub, results)

    if node.value <= ub:

      self.search(node.right, lb, ub, results)

  def range_query(self, lb, ub):

    # Search for values between lower bound and upper bound

    results = []

    self.search(self.root, lb, ub, results)

    return results

Pohon Penyeimbang Diri Lainnya

Kita telah mengimplementasikan pohon AVL yang mampu melakukan operasi berikut:

• Menambahkan nilai
• Menghapus nilai
• Mencari nilai
• Mencari nilai minimum dan maksimum
• Mengambil semua nilai yang berada di antara dua nilai

Paket avltree menawarkan implementasi Python yang mencerminkan kemampuan ini.

Pohon pencarian biner penyeimbang diri lainnya, seperti red-black tree, splay tree, dan B-tree, menyediakan fungsionalitas serupa. Secara umum, kinerjanya sebanding di sebagian besar aplikasi, karena semuanya mempertahankan tinggi logaritmik yang terjamin. Namun, pohon AVL lebih seimbang secara halus, mengoptimalkan operasi pencarian dengan biaya penyisipan yang berpotensi lebih lambat karena kebutuhan penyeimbangan yang ketat.

Splay tree sangat efektif pada skenario di mana elemen yang baru diakses sering digunakan kembali, menjadikannya pilihan yang sangat baik untuk implementasi cache.

B-tree dirancang khusus untuk bekerja secara efisien di media penyimpanan (disk) alih-alih memori, sehingga sangat berharga untuk mengelola dataset besar yang melampaui kapasitas memori, seperti pada pembuatan indeks basis data.

Peningkatan lebih lanjut

Ada beberapa cara untuk meningkatkan implementasi kita. Berikut beberapa saran latihan untuk memperdalam pemahaman Anda tentang pohon AVL:

• Dalam implementasi saat ini, node hanya menyimpan satu nilai. Untuk digunakan sebagai indeks basis data, perlu menyimpan seluruh baris karena nilai akan sesuai dengan salah satu kolom tabel. Kita dapat meningkatkan implementasi agar pohon AVL berfungsi mirip kamus, memetakan nilai ke baris yang bersesuaian.
• Implementasi kita tidak mendukung nilai duplikat. Namun, ini dapat dimodifikasi untuk memungkinkan beberapa node berbagi nilai yang sama.
• Biasanya, pohon AVL diimplementasikan secara rekursif. Kami memilih untuk menghindari pendekatan ini untuk menyingkirkan kebutuhan pemahaman mendalam tentang rekursi. Meskipun implementasi rekursif umumnya lebih elegan dan ringkas, implementasi tersebut memerlukan pemahaman yang kuat tentang konsep rekursi.

Kesimpulan

BST adalah jenis struktur data pohon biner yang mengorganisasi data mengikuti urutan tertentu. Pengorganisasian ini memungkinkan untuk menghindari pemeriksaan seluruh dataset saat mencari nilai tertentu. Namun, BST dapat menjadi tidak seimbang, yang menurunkan kinerja dan dalam beberapa skenario dapat mengharuskan memeriksa seluruh dataset.

Pohon AVL menyelesaikan masalah ini dengan menegakkan properti keseimbangan tambahan melalui rotasi. Properti ini memastikan bahwa tinggi pohon tetap logaritmik terhadap ukuran dataset, memberikan peningkatan yang signifikan.

Kompleksitas waktu logaritmik merupakan peningkatan besar dibandingkan kompleksitas linear, menjadikan pohon AVL sangat efisien untuk penyelesaian kueri. Bahkan pada dataset dengan miliaran entri, pohon AVL hanya memerlukan pemeriksaan sedikit titik data untuk menemukan sebuah elemen, sehingga jauh lebih efisien.