AVL Ağacı: Python Uygulamasıyla Eksiksiz Rehber

İkili Arama Ağaçlarında Dengesizlik

İkili arama ağaçları (BST), belirli bir sıralama kullanarak veriyi düzenleyen bir ikili ağaç veri yapısıdır. Her düğüm bir değer içerir ve en fazla iki düğüme bağlanır: sol ve sağ çocuklar. Bir BST’de kural, sol çocuk düğümünün değerinin ebeveyninden küçük, sağ çocuk düğümünün değerinin ise büyük olmasıdır.

BST’ler, arama sürecinde ağacın büyük bölümlerini elemeye olanak tanıdıkları için belirli değerleri bulmada oldukça etkilidir. Örneğin, yukarıdaki ağaçta bir değerini arıyorsak, altının sağındaki tüm düğümleri göz ardı edebiliriz. Çünkü sıralama özelliği, bu değerlerin tamamının altıdan büyük olacağını garanti eder.

İdeal olarak her düğüm veriyi ikiye bölmelidir; böylece ağaçta her adımda değerlerin yarısı elenir. Bu, son derece hızlı aramalara yol açar. Ancak ekleme sırasına bağlı olarak, veriyi etkili biçimde bölemeyen dengesiz bir ağaçla karşılaşmak mümkündür. Örneğin, değerleri küçükten büyüğe eklemek, listeyle aynı performansa sahip doğrusal bir ağaç oluşturur.

AVL Ağacı Nedir

AVL ağacı, aşağıdaki ek özelliğe sahip bir ikili arama ağacıdır:

Her düğüm için sol ve sağ alt ağaçların yüksekliği en fazla bir fark eder.

Bu tanımı açarsak, bir düğümün sol alt ağacı solunda kalan tüm düğümleri, sağ alt ağacı ise sağında kalan tüm düğümleri kapsar. Bir ağacın yüksekliği, kök düğümden (en üstteki düğüm) herhangi bir yaprak düğüme (çocuğu olmayan düğüm) uzanan en uzun yolun uzunluğu olarak tanımlanır.

Bir düğümün denge faktörü, sol ve sağ alt ağaçlarının yükseklik farkı olarak hesaplanır:

balance(N) = height(N’in sol alt ağacı) - height(N’in sağ alt ağacı)

Örneğin, balance(6) = 1 - 3 = -2.

Şemada, 6 düğümünün denge faktörü -2’dir; bu da ağacın AVL kriterlerini sağlamadığını gösterir. Bir ağacın AVL olarak sınıflandırılması için her düğümün denge faktörü -1, 0 veya 1 olmalıdır.

Neden AVL Ağaçları Kullanılır

Bir ikili arama ağacında sorguların verimliliği ağacın yüksekliğine bağlıdır. En kötü durumda, incelenmesi gereken düğüm sayısı ağacın yüksekliğine eşittir. BST’lerdeki temel sorun, ağacın yüksekliğinin düğüm sayısıyla aynı olabilmesidir; bu da bir sorgunun tüm düğümlerin tek tek incelenmesini gerektirebileceği anlamına gelir.

M(h), bir ikili arama ağacına yüksekliği h olacak şekilde eklenmesi gereken asgari düğüm sayısını göstersin. Basit BST’lerde M(h) = h gözlemlenir; yani h yüksekliğine yalnızca h düğümle ulaşılabilir. Bu da BST yüksekliğinin düğüm sayısıyla doğrusal artabileceği ve sorgu süresinin veri kümesinin boyutuyla orantılı olabileceği anlamına gelir.

AVL ağaçlarının yüksekliğinin logaritmik olduğunun kanıtı

Yüksekliği h olan bir AVL ağacı oluşturmak için gereken asgari düğüm sayısı M(h)’yi ele alalım. AVL ağacı olduğundan, her düğümün denge faktörünün yalnızca -1, 0 veya 1 olabileceğini not etmek önemlidir.

Ancak, ağacın h yüksekliğine ulaşmak için mümkün olan en az düğüme sahip olduğunu varsaydığımızdan, kökün dengesi 0 olamaz. Öyle olsaydı, soldan veya sağdan bir düğüm çıkararak dengeyi -1 veya 1’e getirebilir ve yine de geçerli bir AVL ağacı elde edebilirdik.

Kökün dengesinin 1 olduğunu varsayalım (denge -1 olsaydı akıl yürütme aynı olurdu). Bu, ağacın aşağıdaki gibi yapılandığını ima eder:

Öte yandan, sol ve sağ alt ağaçların her biri de kendi yükseklikleri için gerekli asgari düğüm sayısına sahip AVL ağaçları olmalıdır (aksi halde ilave düğümler çıkarılabilirdi). Ağaçtaki toplam düğüm sayısı, 1 (kök) artı sol alt ağaçtaki düğümlerin sayısı artı sağ alt ağaçtaki düğümlerin sayısına eşittir.

M(h) = 1 + (L’deki düğümler) + (R’deki düğümler) = 1 + M(h - 1) + M(h - 2)

Yükseklik arttıkça, o yüksekliğe ulaşmak için daha fazla düğüm eklememiz gerekir. Dolayısıyla:

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

İkisini birleştirirsek şunu söyleyebiliriz:

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

Bunu h/2 kez uygulayabiliriz; M(1) = 1 veya M(2) = 2’ye ulaşana kadar:

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

Açıklık için, aşağıdaki görsel h = 7 ve h = 6 için belirli örnekleri gösterir:

Sonuç olarak, yüksekliği h olan bir AVL ağacındaki asgari düğüm sayısı en az 2(h/2)’dir:

M(h) > 2(h/2)

Her iki tarafa da taban 2 logaritması uygularsak şunu elde ederiz:

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

Dolayısıyla, her iki tarafı iki ile çarparak, yüksekliğin düğüm sayısının taban 2 logaritmasının en fazla iki katı olduğunu çıkarırız:

2 × log2(M(h)) > h

Şunu göstermiş olduk:

N düğüm içeren bir AVL ağacının yüksekliği en fazla 2 × log2(N)’dir.

Bu, bir AVL ağacındaki sorguların veri kümesinin yalnızca küçük bir bölümünün incelenmesini gerektirdiğini gösterir. Örneğin, bir milyar kayıt için logaritma yaklaşık 30’dur; yani bir milyar veri noktasında bile belirli bir girdiyi bulmak için yalnızca yaklaşık 60 veri noktasını incelemek gerekir. Bu, en kötü durumda tüm bir milyar veri noktasının incelenmesini gerektirebilecek BST’lere kıyasla önemli bir gelişmedir.

Algoritmik zaman karmaşıklığını ve doğrusal zaman karmaşıklığı ile logaritmik karmaşıklık arasındaki farkı daha derinlemesine anlamak için şu blog yazısına göz atın: Büyük-O Gösterimi ve Zaman Karmaşıklığı.

AVL Ağaçlarıyla Dengeyi Korumak

AVL ağaçları, her düğümün dengesinin -1, 0 veya 1 olmasını zorunlu kılarak hızlı sorguları garanti eder. Her düğümün dengesinin korunmasını sağlamak için, yeni bir değer ekledikten sonra ağacı yeniden dengelememiz gerekir.

İkili arama ağaçlarında ekleme, kökten aşağıya doğru yolu izleyerek yapılır. Eklemek istediğimiz değer küçükse sola, aksi halde sağa gideriz.

Bir ekleme, yüksekliği en fazla bir artırır. Dolayısıyla, ekleme sonrası denge özelliği sağlanmıyorsa, ya denge -1 olan bir düğümün dengesi -2 olmuştur ya da denge 1 olan bir düğümün dengesi 2 olmuştur. Yukarıdaki örnekte ilk durum gerçekleşmektedir.

Tekil döndürmeler

Dengeyi geri getirmek için ağaç döndürmelerine başvururuz. Bir sola döndürme, A düğümünde, A’yı sola döndürerek ağacı yeniden yapılandırır; aşağıda gösterildiği gibi:

Şemada:

• BL, B’nin sol alt ağacını temsil eder
• BR sağ alt ağaçtır
• AL, A’nın sol alt ağacıdır

Döndürmeden sonra düğüm sırasının hâlâ geçerli olduğunu unutmayın:

1. A düğümü, B’den küçüktür; çünkü B onun sağ çocuğuydu.
2. BL’deki düğümler, A’dan büyüktür; çünkü A’nın sağ tarafındaydılar.
3. AL’deki düğümler, B’den küçüktür; çünkü A’dan küçüktürler.

Sağa döndürme, A’yı sağa döndürerek simetrik şekilde çalışır.

Somut bir örnek görelim: 19 eklendikten sonra, 6 düğümünde sola döndürme kullanarak ağaçtaki dengesizliği giderelim.

Eklemeden sonra, dengesi -2 veya 2 olan bir düğümü döndürerek dengesizliği gidereceğiz. Bu durumda, 6 düğümünün denge faktörü -2 idi; bu da ağacın sağa doğru eğildiği anlamına gelir, bu yüzden sola döndürme (dengesizliğin ters yönünde) uyguladık. Eğer denge 2 olsaydı, bunun yerine sağa döndürme kullanılırdı.

Çiftli döndürmeler

Önceki örnekte ağaç tamamen sağa eğildiğinden, tek bir sola döndürme dengeyi geri getirmek için yeterliydi. Ancak bazı durumlarda ağaç bir tarafa, alt ağaç ise diğer tarafa eğildiği zikzak türünde bir dengesizlik olabilir. Bunu görmek için, 19 eklemeden önceki orijinal ağaca dönelim ve bunun yerine 7 ekleyelim:

Bu durumda ağaç hâlâ sağa eğiliyor, ancak 10 köküne sahip alt ağaç sola eğiliyor. Bu durumda önce 10 düğümünü sağa döndürmemiz gerekir:

B düğümünün sağ çocuğunun olmadığını unutmayın. Görselleştirmeyi kolaylaştırmak için diyagramda yine de mavi renkle gösteriyoruz. 

Sağa döndürmeden sonra, 6 üzerinde sola döndürmenin dengeyi geri getireceği önceki duruma geri döneriz:

Python’da AVL Ağacı Nasıl Uygulanır

Düğüm uygulamasından başlayalım.

Düğüm (Node) uygulaması

Ağaçtaki her düğüm beş öznitelik taşır:

• Sakladığı değer (self.value)
• Ebeveyn düğüm (self.parent)
• Sol çocuk (self.left)
• Sağ çocuk (self.right)
• Bu düğümde köklenen alt ağacın yüksekliği (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

Eksik düğümleri temsil etmek için None değerini kullanıyoruz. Varsayılan height 1’dir; çünkü tek bir düğümden oluşan bir ağacın yüksekliği 1’dir. 

Ağaç uygulamasını kolaylaştırmak için Node sınıfına birkaç yöntem ekliyoruz.

# 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

Sol ve sağ çocukları atamak için .set_left() ve .set_right() yöntemlerini kullandığımıza dikkat edin. self.left ve self.right özniteliklerini doğrudan değiştirmek yerine bu yöntemleri kullanmamızın gerekçesi, bir çocuk değiştirildiğinde yeni çocuğun ebeveyninin ve düğümün yüksekliğinin de güncellenmesinin gerekmesidir.

AVL ağaç uygulaması

AVL ağacı, ağacın tepesindeki düğüm olan kökü parametre olarak tutar.

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

Ağacın dengesini korumak için sola ve sağa döndürmeleri uygulamamız gerekir. Bir sola döndürme diyagramda şu şekilde gösterilir, hatırlayalım:

# 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

Sağa döndürmeler simetrik şekilde uygulanır:

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

Döndürmeleri kullanarak ağacı yeniden dengeleyebiliriz. Bir düğümün denge faktörü 2’ye (ağacın sola eğildiğini gösterir) ya da -2’ye (ağacın sağa eğildiğini gösterir) ulaştığında yeniden dengeleme gerekir. Toplamda dikkate almamız gereken dört senaryo vardır:

Bu dört durumu .rebalance() yönteminde uyguluyoruz.

# 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)

Her durumda yöntemin, yeni dengelenmiş alt ağacın kökünü döndürdüğünü unutmayın. Bu yeni alt ağaç kökü, yeniden dengeleme sürecinde çocukları güncellemek için daha sonra kullanılacaktır.

Bir düğümü AVL ağacına eklemek, düğüm eklendikten sonra dengeyi geri kazandırma adımı eklenmiş bir BST’ye eklemeye benzer. BST’de bir düğüm eklemek için kökten başlayıp ağaç boyunca ilerleriz. Her adımda eklenecek değeri mevcut düğümün değeriyle karşılaştırırız. Eklenecek değer küçükse sola, değilse sağa gideriz. Aşağı inerken, yeni düğümü çocuğu olarak ekleyebilmek için ebeveyn düğümü takip ederiz.

Boş bir düğüme ulaştığımızda iki durum vardır:

1. Ebeveyn None’dır; bu durumda ağaç boştur ve yeni düğüm ağacın yeni köküdür.
2. Ebeveyni bulmuşuzdur; değerlerine bağlı olarak yeni düğümü sol veya sağ çocuk olarak ayarlamamız gerekir.

# 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)

Bir BST’nin .add() yöntemiyle bir AVL ağacının .add() yöntemi arasındaki tek fark son adımdadır. Bu, ağaçta yukarı doğru ilerleyerek yeni düğümden köke kadar düğümleri .rebalance() yöntemini kullanarak yeniden dengelemeyi içerir.

# 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

.rebalance() yöntemi, düğüm zaten dengedeyse hiçbir şey yapmaz—aynı düğümü geri döndürür. Bu nedenle ağaçta yukarı çıkarken her iki tarafta da çağırabiliriz; her ne kadar yalnızca bir taraf dengesiz olabilse de, diğer çağrı ağacı olduğu gibi bırakır.

Unutmayın, .rebalance() yöntemini, (potansiyel) yeni alt ağaç kökünü döndürecek şekilde uygulamıştık. Bunun nedeni, dengeyi geri kazandırırken mevcut düğümlerin sol ve sağ çocuklarını güncelleyebilmemiz içindi.

Aşağıdaki diyagram, ağacın yukarılarında .restore_balance() adımlarını gösterir.

Verilen örnekte önce 8 düğümünü ekliyoruz. Ardından, dengeyi geri yükleme süreci bu düğümden başlayıp ağaç boyunca yukarı doğru ilerler; karşılaşılan her düğümün sol ve sağ çocuklarını kontrol eder ve yeniden dengeler. Bu işlem 10 düğümüne kadar sürer. Bu noktaya kadar, .rebalance() çağrılarının hiçbiri etkili olmaz; çünkü düğümler dengededir.

Ancak 10 düğümüne ulaşıldığında, sol çocuğu 7 düğümünün denge faktörünün -2 olduğu görülür ve yeniden dengeleme gerekir. Bunun sonucunda .rebalance(7) çağrılır ve 10 düğümünün sol çocuğu, sol alt ağacın yeni kökü olan 8 ile değiştirilir; böylece ağacın dengesi geri kazanılır.

Ek AVL Ağacı İşlemleri

Ağacın dengesini korurken öğe ekleme ve silmenin yanı sıra, AVL ağaçları birkaç temel işlevi daha destekler.

Minimum ve maksimum

BST’nin sıralı doğası gereği, en küçük değer ağacın en soldaki düğümünde, en büyük değer ise en sağdaki düğümünde bulunur.

Belirli bir düğümden başlayarak en soldaki ve en sağdaki düğümleri belirleyen iki yardımcı işlev uyguladık. Bu işlevler, düğüm silme işleminin uygulanmasını kolaylaştırmak için kullanışlıdır.

# 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

İçerir mi (Contains)

Bir ağacın belirli bir değeri içerip içermediğini belirlemek için ağacın sıralama özelliğini aramayı yönlendirmek üzere kullanırız. Kökten başlayarak, aradığımız değer mevcut düğümden küçükse sola, büyükse sağa ilerleriz. Aranan değeri bulamadan ağacın sonuna ulaşırsak, o değerin ağaçta bulunmadığı sonucuna varırız.

Bu süreci kolaylaştırmak için .locate_node() adlı bir yardımcı yöntem uygularız. Bu yöntem yalnızca arama için değil, aynı zamanda ağaçtan değer silme gibi işlemler için de yararlıdır. Ayrıca, ağaçta bir değerin bulunup bulunmadığını kontrol etmeyi basitleştirmek için in işleciyle kullanılabilen .__contains__() yöntemini de kullanırız.

# 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

Silme

Bir AVL ağacında bir düğümü silmek, düğüm ağacın ortasında yer aldığında özellikle zorlu olabilir. Düğüm bir yapraksa, yani çocuğu yoksa, sol ya da sağ çocuk oluşuna göre ebeveyninin sol veya sağ çocuk işaretçisini None yaparak kolayca silebiliriz.

Silinecek düğüm ağacın kökü olduğunda özel bir durum ortaya çıkar. Bu senaryoda, kökü None yaparak düğümü kaldırabiliriz.

# 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

Bir AVL ağacından bir değeri silmek için önce .locate_node() yöntemiyle bu değeri içeren düğümü bulmalıyız. Düğüm bulunduğunda, yaprak düğümse .delete_leaf() yöntemiyle silebiliriz. Yaprak değilse, doğrudan kaldırmak ağacın yapısını bozar. Bunu çözmek için uygun bir yedek düğüm buluruz. Silinecek düğümün sol çocuğu varsa, sol alt ağacındaki en sağdaki düğümü seçeriz. Bu yaklaşım, ağacın sıralı yapısını korur.

Aşağıdaki diyagram bir ağaçtan 10 düğümünün kaldırılmasını örneklemektedir. Sol çocuğu olduğundan, sol alt ağaçtaki en sağdaki düğümle değiştirilir. Değiştirmenin ardından, yeni yerleştirilen düğümün ebeveyninden başlayarak ağacı yeniden dengelemek önemlidir.

Bu örnekte yedek düğüm bir yaprak düğümdür. Ancak yedek düğümün çocukları varsa, bunları yedek düğümün ebeveynine yeniden atamak gerekir. Yedek düğüm uç bir düğüm (en sol veya en sağ) olduğundan, en fazla bir çocuğu olabilir. Bu nedenle bu yeniden atama her zaman mümkündür.

# 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)

Aralık sorgusu

Aralık sorguları, iki değer arasında kalan tüm değerlerin belirlenmesini içerir. AVL ağaçlarının sıralı yapısı sayesinde bu değerleri verimli şekilde bulabiliriz.

Alt sınır lb ve üst sınır ub ile belirlenen aralıktaki tüm değerleri bulmak için ağacı özyinelemeli olarak ararız. Karşılaşılan her düğüm için, değeri bu aralıkta ise sonuçlara ekleriz. Ardından aramaya devam etmek için hem sol hem de sağ alt ağaçları keşfederiz.

Düğümün değeri alt sınırdan küçükse, sol alt ağacı yok sayarız; çünkü sol alt ağaçtaki tüm değerler düğümün değerinden küçüktür. Benzer şekilde, düğümün değeri üst sınırdan büyükse, sağ alt ağacı yok sayarız; çünkü sağ alt ağaçtaki tüm değerler düğümün değerinden büyük olacaktır.

  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

Diğer Kendi Kendini Dengeleyen Ağaçlar

Aşağıdaki işlemleri gerçekleştirebilen bir AVL ağacı uyguladık:

• Değer ekleme
• Değer silme
• Değer arama
• Minimum ve maksimumu sorgulama
• İki değer arasına düşen tüm değerleri sorgulama

avltree paketi bu yetenekleri yansıtan bir Python uygulaması sunar.

Kırmızı-siyah ağaçlar, splay ağaçları ve B-ağaçları gibi diğer kendi kendini dengeleyen ikili arama ağaçları benzer işlevler sağlar. Genel olarak, hepsi garantili logaritmik yükseklik sağladıklarından çoğu uygulamada performansları karşılaştırılabilirdir. Ancak AVL ağaçları daha sıkı dengelenir; bu da arama işlemlerini optimize ederken, katı yeniden dengeleme gereklilikleri nedeniyle eklemeleri potansiyel olarak yavaşlatır.

Splay ağaçları, yakın zamanda erişilen öğelerin sıkça tekrarlandığı senaryolarda özellikle etkilidir; bu da onları önbellek uygulamaları için mükemmel bir seçim yapar.

B-ağaçları, bellekte değil de diskte verimli çalışacak şekilde özel olarak tasarlanmıştır; bu da bellek kapasitesini aşan büyük veri kümelerini yönetmek, örneğin veritabanı indeksleri oluşturmak için onları çok değerli kılar.

İleri düzey iyileştirmeler

Uygulamamızın geliştirilebileceği çeşitli yollar vardır. AVL ağaçlarını daha iyi kavramak için birkaç alıştırma önerisi:

• Mevcut uygulamamızda düğümler tek bir değer saklıyor. Veritabanı indeksleri olarak kullanımda, değerin tablodaki sütunlardan birine karşılık gelmesi nedeniyle tüm satırların saklanması gerekir. Uygulamamızı, AVL ağacını değerleri ilgili satırlara eşleyen bir sözlük gibi çalışacak şekilde geliştirebiliriz.
• Uygulamamız yinelenen değerlere izin vermiyor. Ancak, birden fazla düğümün aynı değeri paylaşmasına izin verecek şekilde değiştirilebilir.
• Genellikle AVL ağaçları özyinelemeli olarak uygulanır. Biz, özyinelemeyi derinlemesine anlamaya ihtiyaç duymamak için bu yaklaşımdan kaçındık. Özyinelemeli uygulamalar genelde daha zarif ve kısadır; ancak güçlü bir özyineleme kavrayışı gerektirir.

Sonuç

BST’ler, veriyi belirli bir düzene göre organize eden bir ikili ağaç veri yapısıdır. Bu organizasyon, belirli değerleri ararken tüm veri kümesinin incelenmesini önlemeyi sağlar. Ancak BST’ler dengesiz hale gelebilir ve performansın bozulmasına yol açabilir; bazı senaryolarda tüm veri kümesini incelemeyi gerektirebilir.

AVL ağaçları, döndürmeler yoluyla ek denge özelliklerini zorunlu kılarak bu sorunu çözer. Bu özellikler, ağacın yüksekliğinin veri kümesinin boyutuna göre logaritmik kalmasını sağlar ve önemli bir iyileşme sunar.

Logaritmik zaman karmaşıklığı, doğrusal zaman karmaşıklığına kıyasla kayda değer bir iyileşmedir ve AVL ağaçlarını sorgu çözümlemede son derece verimli kılar. Milyarlarca kayıttan oluşan veri kümelerinde bile, bir öğeyi bulmak için yalnızca birkaç veri noktasının incelenmesi yeterlidir; bu da onları çok daha verimli hale getirir.