Arbre binaire de recherche (BST)

Structures de données et algorithmes en Python

Miriam Antona

Software engineer

Définition

Sous-arbre gauche d’un nœud :
- valeurs inférieures à ce nœud
Sous-arbre droit d’un nœud :
- valeurs supérieures à ce nœud
Les sous-arbres gauche et droit doivent être des arbres binaires de recherche

Représentation schématique d’un arbre binaire de recherche.

Implémentation

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

Recherche

Rechercher 72

Représentation schématique d’un arbre binaire de recherche.

Recherche

Rechercher 72

Représentation schématique d’un arbre binaire de recherche où le nœud racine est en jaune.

Recherche

Rechercher 72

Représentation schématique d’un arbre binaire de recherche où le nœud racine et le sous-arbre gauche de la racine sont en gris. Le premier nœud du sous-arbre droit est en jaune.

Recherche

Rechercher 72

Représentation schématique d’un arbre binaire de recherche. Le dernier nœud racine et son sous-arbre gauche sont en gris. Le nouveau nœud racine est en jaune.

Recherche

Rechercher 72

Représentation schématique d’un arbre binaire de recherche où le nouveau nœud racine est en jaune et le reste en gris.

Recherche

Rechercher 72

Représentation schématique d’un arbre binaire de recherche où le nouveau nœud racine est en jaune et le reste en gris. Le nœud coloré porte le nombre 72 et est mis en évidence.

Recherche

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

Insertion

def insert(self, data):

  new_node = TreeNode(data)

  if self.root == None:

Représentation graphique d’un nouveau nœud.

Insertion

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

Représentation graphique du nouveau nœud devenu nœud racine.

Insertion

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

Représentation d’un nouveau nœud et d’une racine avec un enfant droit.

Insertion

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:

Représentation d’un nouveau nœud et d’une racine avec un enfant droit. Le nœud courant est la racine.

Insertion

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

Représentation d’une racine avec un enfant droit et un enfant gauche. Le nœud courant est la racine. Le nouveau nœud est l’enfant gauche.

Insertion

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:

Représentation d’un nouveau nœud et d’un arbre binaire de recherche avec quelques éléments. Le nœud courant est la racine.

Insertion

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

Représentation d’un nouveau nœud et d’un arbre binaire de recherche avec quelques éléments. Le nœud courant est l’enfant gauche de la racine.

Insertion

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:

Représentation d’un nouveau nœud et d’un arbre binaire de recherche avec un sous-arbre gauche.

Insertion

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

Représentation d’un arbre binaire de recherche avec un sous-arbre gauche. Le nouveau nœud est désormais l’enfant droit de la racine.

Insertion

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:

Représentation d’un nouveau nœud et d’un arbre binaire de recherche avec quelques éléments.

Insertion

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

Représentation d’un nouveau nœud et d’un arbre binaire de recherche avec quelques éléments. Le nœud courant est l’enfant droit de la racine.

Insertion

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

Représentation d’un nouveau nœud et d’un arbre binaire de recherche avec quelques éléments. Le nœud courant est l’enfant droit de la racine. Le nouveau nœud est l’enfant gauche du nœud courant.

Suppression

Sans enfants

Représentation d’un arbre binaire de recherche avec quelques éléments. L’un des nœuds est en rouge car il va être supprimé. Ce nœud n’a pas d’enfants.

Suppression

Sans enfants
- le supprimer

Représentation d’un arbre binaire de recherche avec quelques éléments. Le nœud à supprimer a disparu de l’arbre.

Suppression

Un enfant

Représentation d’un arbre binaire de recherche avec quelques éléments. L’un des nœuds est en rouge car il va être supprimé. Ce nœud a un enfant droit.

Suppression

Un enfant
- le supprimer
- relier l’enfant au parent du nœud

Représentation d’un arbre binaire de recherche avec quelques éléments. Le nœud supprimé a disparu et la racine pointe vers l’enfant droit de ce nœud.

Suppression

Un enfant
- le supprimer
- relier l’enfant au parent du nœud

Représentation d’un arbre binaire de recherche.

Suppression

Deux enfants

Représentation d’un arbre binaire de recherche où la racine à supprimer est en rouge.

Suppression

Deux enfants
- le remplacer par son successeur
  - nœud de valeur la plus petite supérieure à celle du nœud
- trouver le successeur :

Représentation d’un arbre binaire de recherche où la racine à supprimer est en rouge.

Suppression

Deux enfants
- le remplacer par son successeur
  - nœud de valeur la plus petite supérieure à celle du nœud
- trouver le successeur :
  - visiter l’enfant droit

Représentation d’un arbre binaire de recherche où la racine à supprimer est en rouge. L’enfant droit de la racine est en jaune.

Suppression

Deux enfants
- le remplacer par son successeur
  - nœud de valeur la plus petite supérieure à celle du nœud
- trouver le successeur :
  - visiter l’enfant droit
  - poursuivre à gauche jusqu’à la fin

Représentation d’un arbre binaire de recherche où la racine à supprimer est en rouge. Un autre nœud est en jaune pour trouver le successeur.

Suppression

Deux enfants
- le remplacer par son successeur
  - nœud de valeur la plus petite supérieure à celle du nœud
- trouver le successeur :
  - visiter l’enfant droit
  - poursuivre à gauche jusqu’à la fin

Représentation d’un arbre binaire de recherche où la racine à supprimer est en rouge. Un autre nœud est en jaune pour trouver le successeur.

Suppression

Deux enfants
- le remplacer par son successeur
  - nœud de valeur la plus petite supérieure à celle du nœud
- trouver le successeur :
  - visiter l’enfant droit
  - poursuivre à gauche jusqu’à la fin

Représentation d’un arbre binaire de recherche où la racine à supprimer est en rouge. Un autre nœud est en jaune pour trouver le successeur. Le successeur a été trouvé : 13.

Suppression

Deux enfants
- le remplacer par son successeur
  - nœud de valeur la plus petite supérieure à celle du nœud
- trouver le successeur :
  - visiter l’enfant droit
  - poursuivre à gauche jusqu’à la fin

Représentation d’un arbre binaire de recherche. La racine a été remplacée par le successeur.

Suppression

Deux enfants
- le remplacer par son successeur
  - nœud de valeur la plus petite supérieure à celle du nœud
- trouver le successeur :
  - visiter l’enfant droit
  - poursuivre à gauche jusqu’à la fin
  - si le successeur a un enfant droit :

Représentation d’un arbre binaire de recherche où le successeur a un enfant droit.

Suppression

Deux enfants
- le remplacer par son successeur
  - nœud de valeur la plus petite supérieure à celle du nœud
- trouver le successeur :
  - visiter l’enfant droit
  - poursuivre à gauche jusqu’à la fin
  - si le successeur a un enfant droit :
    - l’enfant devient l’enfant gauche du parent du successeur.

Représentation d’un arbre binaire de recherche où le successeur avait un enfant droit. Cet enfant est devenu l’enfant gauche du parent du successeur et la racine a été remplacée par le successeur.

Utilisations

Trier des listes efficacement
Recherche bien plus rapide que dans les tableaux et les listes chaînées
Insertion et suppression bien plus rapides que dans les tableaux
Sert à implémenter des structures plus avancées :
- ensembles dynamiques
- tables de hachage
- files de priorité

Passons à la pratique !

Structures de données et algorithmes en Python