İkili Arama Ağacı (BST)

Python'da Veri Yapıları ve Algoritmalar

Miriam Antona

Software engineer

Tanım

Bir düğümün sol alt ağacı:
- düğümün değerinden küçük değerler
Bir düğümün sağ alt ağacı:
- düğümün değerinden büyük değerler
Sol ve sağ alt ağaçlar da ikili arama ağacı olmalıdır

İkili arama ağacının şematik gösterimi.

Uygulama

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

Arama

72'yi ara

İkili arama ağacının şematik gösterimi.

Arama

72'yi ara

Kök düğümü sarı renkte olan bir ikili arama ağacının şematik gösterimi.

Arama

72'yi ara

İkili arama ağacının şematik gösterimi; kök düğüm ve kökün sol alt ağacı gri, sağ alt ağacın ilk düğümü sarı renkte.

Arama

72'yi ara

İkili arama ağacının şematik gösterimi. Son kök düğüm ve onun sol alt ağacı gri, yeni kök düğüm sarı renkte.

Arama

72'yi ara

İkili arama ağacının şematik gösterimi; yeni kök düğüm sarı, diğer düğümler gri renkte.

Arama

72'yi ara

İkili arama ağacının şematik gösterimi; yeni kök düğüm sarı, diğer düğümler gri renkte. Renklendirilen düğüm 72'dir ve vurgulanmıştır.

Arama

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

Ekleme

def insert(self, data):

  new_node = TreeNode(data)

  if self.root == None:

Yeni bir düğümün görsel gösterimi.

Ekleme

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

Kök düğüm olan yeni düğümün görsel gösterimi.

Ekleme

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

Yeni bir düğüm ve sağ çocuğu olan bir kök düğümün görsel gösterimi.

Ekleme

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:

Yeni bir düğüm ve sağ çocuğu olan bir kök düğümün görsel gösterimi. Kök düğüm current_node'dur.

Ekleme

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

Sağ ve sol çocuğu olan bir kök düğümün görsel gösterimi. Kök düğüm current_node'dur. Yeni düğüm sol çocuktur.

Ekleme

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:

Bazı öğeleri olan bir ikili arama ağacı ve yeni düğümün görsel gösterimi. Kök düğüm current_node'dur.

Ekleme

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

Bazı öğeleri olan bir ikili arama ağacı ve yeni düğümün görsel gösterimi. current_node, kökün sol çocuğudur.

Ekleme

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:

Sol alt ağacı olan bir ikili arama ağacının ve yeni düğümün görsel gösterimi.

Ekleme

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

Sol alt ağacı olan bir ikili arama ağacının görsel gösterimi. Yeni düğüm artık kökün sağ çocuğudur.

Ekleme

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:

Bazı öğeleri olan bir ikili arama ağacı ve yeni düğümün görsel gösterimi.

Ekleme

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

Bazı öğeleri olan bir ikili arama ağacı ve yeni düğümün görsel gösterimi. current_node, kökün sağ çocuğudur.

Ekleme

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

Bazı öğeleri olan bir ikili arama ağacı ve yeni düğümün görsel gösterimi. current_node, kökün sağ çocuğudur. Yeni düğüm, current_node'un sol çocuğudur.

Silme

Çocuğu yok

Bazı öğeleri olan bir ikili arama ağacının görsel gösterimi. Kırmızı renkle gösterilen düğüm silinecektir. Bu düğümün çocuğu yoktur.

Silme

Çocuğu yok
- silin

Bazı öğeleri olan bir ikili arama ağacının görsel gösterimi. Silinecek düğüm ağaçtan kaldırılmıştır.

Silme

Tek çocuk

Bazı öğeleri olan bir ikili arama ağacının görsel gösterimi. Kırmızı düğüm silinecektir. Bu düğümün sağ çocuğu vardır.

Silme

Tek çocuk
- silin
- çocuğu düğümün ebeveynine bağlayın

Bazı öğeleri olan bir ikili arama ağacının görsel gösterimi. Silinen düğüm yok olmuştur ve kök düğüm, silinen düğümün sağ çocuğuna bağlanır.

Silme

Tek çocuk
- silin
- çocuğu düğümün ebeveynine bağlayın

İkili arama ağacının şematik gösterimi.

Silme

İki çocuk

Kök düğümü silinecek ve kırmızı renkte gösterilen bir ikili arama ağacının görseli.

Silme

İki çocuk
- halefiyle değiştirin
  - düğüm değerinden daha büyük en küçük değere sahip düğüm
- halefi bulun:

Kök düğümü silinecek ve kırmızı renkte gösterilen bir ikili arama ağacının görseli.

Silme

İki çocuk
- halefiyle değiştirin
  - düğüm değerinden daha büyük en küçük değere sahip düğüm
- halefi bulun:
  - sağ çocuğa gidin

Kök düğümü silinecek ve kırmızı renkte gösterilen bir ikili arama ağacının görseli. Kökün sağ çocuğu sarı renkte.

Silme

İki çocuk
- halefiyle değiştirin
  - düğüm değerinden daha büyük en küçük değere sahip düğüm
- halefi bulun:
  - sağ çocuğa gidin
  - sona kadar sol düğümleri takip edin

Kök düğümü silinecek ve kırmızı renkte gösterilen bir ikili arama ağacının görseli. Halef bulunması için başka bir düğüm sarı renkte.

Silme

İki çocuk
- halefiyle değiştirin
  - düğüm değerinden daha büyük en küçük değere sahip düğüm
- halefi bulun:
  - sağ çocuğa gidin
  - sona kadar sol düğümleri takip edin

Kök düğümü silinecek ve kırmızı renkte gösterilen bir ikili arama ağacının görseli. Halef bulunması için başka bir düğüm sarı renkte.

Silme

İki çocuk
- halefiyle değiştirin
  - düğüm değerinden daha büyük en küçük değere sahip düğüm
- halefi bulun:
  - sağ çocuğa gidin
  - sona kadar sol düğümleri takip edin

Kök düğümü silinecek ve kırmızı renkte gösterilen bir ikili arama ağacının görseli. Halefi bulmak için sarı düğüm. Halef 13 olarak bulunmuştur.

Silme

İki çocuk
- halefiyle değiştirin
  - düğüm değerinden daha büyük en küçük değere sahip düğüm
- halefi bulun:
  - sağ çocuğa gidin
  - sona kadar sol düğümleri takip edin

İkili arama ağacının görseli. Kök düğüm halef ile değiştirilmiştir.

Silme

İki çocuk
- halefiyle değiştirin
  - düğüm değerinden daha büyük en küçük değere sahip düğüm
- halefi bulun:
  - sağ çocuğa gidin
  - sona kadar sol düğümleri takip edin
  - eğer halefin sağ çocuğu varsa:

Halef düğümün sağ çocuğu olan bir ikili arama ağacının görsel gösterimi.

Silme

İki çocuk
- halefiyle değiştirin
  - düğüm değerinden daha büyük en küçük değere sahip düğüm
- halefi bulun:
  - sağ çocuğa gidin
  - sona kadar sol düğümleri takip edin
  - eğer halefin sağ çocuğu varsa:
    - çocuk, halefin ebeveyninin sol çocuğu olur.

Halef düğümün sağ çocuğu olan bir ikili arama ağacı. Halefin çocuğu, halefin ebeveyninin sol çocuğu olmuş ve kök halef ile değiştirilmiştir.

Kullanımlar

Listeleri verimli sıralar
Diziler ve bağlı listelere göre aramada çok daha hızlıdır
Dizilere göre ekleme ve silmede çok daha hızlıdır
Daha gelişmiş veri yapıları için kullanılır:
- dinamik kümeler
- arama(tablosu) yapıları
- öncelik kuyrukları

Haydi pratik yapalım!

Python'da Veri Yapıları ve Algoritmalar