Arbore binar de căutare (BST)

Structuri de date și algoritmi în Python

Miriam Antona

Software engineer

Definiție

Subarborele stâng al unui nod:
- valori mai mici decât nodul însuși
Subarborele drept al unui nod:
- valori mai mari decât nodul însuși
Subarborii stâng și drept trebuie să fie arbori binari de căutare

Reprezentare schematică a unui arbore binar de căutare.

Implementare

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

Căutare

Căutare pentru 72

Reprezentare schematică a unui arbore binar de căutare.

Căutare

Căutare pentru 72

Reprezentare schematică a unui arbore binar de căutare în care nodul rădăcină este colorat în galben.

Căutare

Căutare pentru 72

Reprezentare schematică a unui arbore binar de căutare în care nodul rădăcină și subarborele stâng al rădăcinii sunt colorate în gri. Primul nod al subarborelui drept este colorat în galben.

Căutare

Căutare pentru 72

Reprezentare schematică a unui arbore binar de căutare. Subarborele stâng al ultimului nod rădăcină și ultimul nod rădăcină sunt colorate în gri. Noul nod rădăcină este colorat în galben.

Căutare

Căutare pentru 72

Reprezentare schematică a unui arbore binar de căutare în care noul nod rădăcină este colorat în galben, iar restul nodurilor sunt colorate în gri.

Căutare

Căutare pentru 72

Reprezentare schematică a unui arbore binar de căutare în care noul nod rădăcină este colorat în galben, iar restul nodurilor sunt colorate în gri. Nodul colorat are valoarea 72 și este evidențiat.

Căutare

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

Inserare

def insert(self, data):

  new_node = TreeNode(data)

  if self.root == None:

Reprezentare grafică a unui nod nou.

Inserare

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

Reprezentare grafică a nodului nou care a devenit nodul rădăcină.

Inserare

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

Reprezentare grafică a unui nod nou și a unui nod rădăcină cu un copil drept.

Inserare

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:

Reprezentare grafică a unui nod nou și a unui nod rădăcină cu un copil drept. Nodul rădăcină este current_node.

Inserare

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

Reprezentare grafică a unui nod rădăcină cu copil drept și copil stâng. Nodul rădăcină este current_node. Nodul nou este copilul stâng.

Inserare

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:

Reprezentare grafică a unui nod nou și a unui arbore binar de căutare cu mai multe elemente. Nodul rădăcină este current_node.

Inserare

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

Reprezentare grafică a unui nod nou și a unui arbore binar de căutare cu mai multe elemente. current_node este copilul stâng al rădăcinii.

Inserare

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:

Reprezentare grafică a unui nod nou și a unui arbore binar de căutare cu un subarbore stâng.

Inserare

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

Reprezentare grafică a unui arbore binar de căutare cu un subarbore stâng. Nodul nou este acum copilul drept al rădăcinii.

Inserare

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:

Reprezentare grafică a unui nod nou și a unui arbore binar de căutare cu mai multe elemente.

Inserare

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

Reprezentare grafică a unui nod nou și a unui arbore binar de căutare cu mai multe elemente. current_node este copilul drept al rădăcinii.

Inserare

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

Reprezentare grafică a unui nod nou și a unui arbore binar de căutare cu mai multe elemente. current_node este copilul drept al rădăcinii. Nodul nou este copilul stâng al current_node.

Ștergere

Fără copii

Reprezentare grafică a unui arbore binar de căutare cu mai multe elemente. Unul dintre noduri este colorat în roșu deoarece urmează să fie eliminat. Acest nod nu are copii.

Ștergere

Fără copii
- se șterge

Reprezentare grafică a unui arbore binar de căutare cu mai multe elemente. Nodul care urma să fie eliminat a dispărut din arbore.

Ștergere

Un copil

Reprezentare grafică a unui arbore binar de căutare cu mai multe elemente. Unul dintre noduri este colorat în roșu deoarece urmează să fie eliminat. Acest nod are un copil drept.

Ștergere

Un copil
- se șterge
- copilul se conectează cu părintele nodului

Reprezentare grafică a unui arbore binar de căutare cu mai multe elemente. Nodul eliminat a dispărut din arbore, iar nodul rădăcină indică copilul drept al nodului eliminat.

Ștergere

Un copil
- se șterge
- copilul se conectează cu părintele nodului

Reprezentare grafică a unui arbore binar de căutare.

Ștergere

Doi copii

Reprezentare grafică a unui arbore binar de căutare în care nodul rădăcină urmează să fie șters și este colorat în roșu.

Ștergere

Doi copii
- se înlocuiește cu succesorul său
  - nodul cu cea mai mică valoare mai mare decât valoarea nodului
- găsirea succesorului:

Reprezentare grafică a unui arbore binar de căutare în care nodul rădăcină urmează să fie șters și este colorat în roșu.

Ștergere

Doi copii
- se înlocuiește cu succesorul său
  - nodul cu cea mai mică valoare mai mare decât valoarea nodului
- găsirea succesorului:
  - se vizitează copilul drept

Reprezentare grafică a unui arbore binar de căutare în care nodul rădăcină urmează să fie șters și este colorat în roșu. Copilul drept al rădăcinii este colorat în galben.

Ștergere

Doi copii
- se înlocuiește cu succesorul său
  - nodul cu cea mai mică valoare mai mare decât valoarea nodului
- găsirea succesorului:
  - se vizitează copilul drept
  - se continuă vizitarea nodurilor stângi până la capăt

Reprezentare grafică a unui arbore binar de căutare în care nodul rădăcină urmează să fie șters și este colorat în roșu. Un alt nod este colorat în galben pentru a găsi succesorul.

Ștergere

Doi copii
- se înlocuiește cu succesorul său
  - nodul cu cea mai mică valoare mai mare decât valoarea nodului
- găsirea succesorului:
  - se vizitează copilul drept
  - se continuă vizitarea nodurilor stângi până la capăt

Reprezentare grafică a unui arbore binar de căutare în care nodul rădăcină urmează să fie șters și este colorat în roșu. Un alt nod este colorat în galben pentru a găsi succesorul.

Ștergere

Doi copii
- se înlocuiește cu succesorul său
  - nodul cu cea mai mică valoare mai mare decât valoarea nodului
- găsirea succesorului:
  - se vizitează copilul drept
  - se continuă vizitarea nodurilor stângi până la capăt

Reprezentare grafică a unui arbore binar de căutare în care nodul rădăcină urmează să fie șters și este colorat în roșu. Un alt nod este colorat în galben pentru a găsi succesorul. Succesorul a fost găsit și are valoarea 13.

Ștergere

Doi copii
- se înlocuiește cu succesorul său
  - nodul cu cea mai mică valoare mai mare decât valoarea nodului
- găsirea succesorului:
  - se vizitează copilul drept
  - se continuă vizitarea nodurilor stângi până la capăt

Reprezentare grafică a unui arbore binar de căutare. Nodul rădăcină a fost înlocuit cu succesorul.

Ștergere

Doi copii
- se înlocuiește cu succesorul său
  - nodul cu cea mai mică valoare mai mare decât valoarea nodului
- găsirea succesorului:
  - se vizitează copilul drept
  - se continuă vizitarea nodurilor stângi până la capăt
  - dacă succesorul are un copil drept:

Reprezentare grafică a unui arbore binar de căutare în care nodul succesor are un copil drept.

Ștergere

Doi copii
- se înlocuiește cu succesorul său
  - nodul cu cea mai mică valoare mai mare decât valoarea nodului
- găsirea succesorului:
  - se vizitează copilul drept
  - se continuă vizitarea nodurilor stângi până la capăt
  - dacă succesorul are un copil drept:
    - copilul devine copilul stâng al părintelui succesorului.

Reprezentare grafică a unui arbore binar de căutare în care nodul succesor a avut un copil drept. Copilul succesorului a devenit copilul stâng al părintelui succesorului, iar nodul rădăcină a fost înlocuit cu nodul succesor.

Utilizări

Ordonează liste eficient
Mult mai rapid la căutare decât tablourile și listele înlănțuite
Mult mai rapid la inserare și ștergere decât tablourile
Utilizat pentru implementarea unor structuri de date avansate:
- mulțimi dinamice
- tabele de căutare
- cozi de priorități

Să exersăm!

Structuri de date și algoritmi în Python