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.

Implantation

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 son sous-arbre gauche 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 sous-arbre gauche du dernier nœud racine et ce nœud 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 graphique d'un nouveau nœud et d'un nœud 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 graphique d'un nouveau nœud et d'un nœud racine avec un enfant droit. Le nœud racine est le current_node.

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 graphique d'un nœud racine avec un enfant droit et un enfant gauche. Le nœud racine est le current_node. 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 graphique d'un nouveau nœud et d'un arbre binaire de recherche avec quelques éléments. Le nœud racine est le current_node.

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 graphique d'un nouveau nœud et d'un arbre binaire de recherche avec quelques éléments. Le current_node 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 graphique 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 graphique d'un arbre binaire de recherche avec un sous-arbre gauche. Le nouveau nœud est maintenant 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 graphique 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 graphique d'un nouveau nœud et d'un arbre binaire de recherche avec quelques éléments. Le current_node 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 graphique d'un nouveau nœud et d'un arbre binaire de recherche avec quelques éléments. Le current_node est l'enfant droit de la racine. Le nouveau nœud est l'enfant gauche du current_node.

Suppression

Aucun enfant

Représentation graphique d'un arbre binaire de recherche avec quelques éléments. L'un des nœuds, sans enfant, est en rouge car il sera supprimé.

Suppression

Aucun enfant
- le supprimer

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

Suppression

Un enfant

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

Suppression

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

Représentation graphique 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 l'ancien nœud.

Suppression

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

Représentation graphique d'un arbre binaire de recherche.

Suppression

Deux enfants

Représentation graphique d'un arbre binaire de recherche où le nœud racine à supprimer est en rouge.

Suppression

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

Représentation graphique d'un arbre binaire de recherche où le nœud racine à supprimer est en rouge.

Suppression

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

Représentation graphique d'un arbre binaire de recherche où le nœud racine à supprimer est en rouge. L'enfant droit de la racine est en jaune.

Suppression

Deux enfants
- le remplacer par son successeur
  - le nœud ayant la plus petite valeur supérieure à celle du nœud
- trouver le successeur :
  - visiter l'enfant droit
  - continuer à visiter les nœuds gauches jusqu'à la fin

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

Suppression

Deux enfants
- le remplacer par son successeur
  - le nœud ayant la plus petite valeur supérieure à celle du nœud
- trouver le successeur :
  - visiter l'enfant droit
  - continuer à visiter les nœuds gauches jusqu'à la fin

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

Suppression

Deux enfants
- le remplacer par son successeur
  - le nœud ayant la plus petite valeur supérieure à celle du nœud
- trouver le successeur :
  - visiter l'enfant droit
  - continuer à visiter les nœuds gauches jusqu'à la fin

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

Suppression

Deux enfants
- le remplacer par son successeur
  - le nœud ayant la plus petite valeur supérieure à celle du nœud
- trouver le successeur :
  - visiter l'enfant droit
  - continuer à visiter les nœuds gauches jusqu'à la fin

Représentation graphique d'un arbre binaire de recherche. Le nœud racine a été remplacé par le successeur.

Suppression

Deux enfants
- le remplacer par son successeur
  - le nœud ayant la plus petite valeur supérieure à celle du nœud
- trouver le successeur :
  - visiter l'enfant droit
  - continuer à visiter les nœuds gauches jusqu'à la fin
  - si le successeur a un enfant droit :

Représentation graphique d'un arbre binaire de recherche où le nœud successeur a un enfant droit.

Suppression

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

Représentation graphique d'un arbre binaire de recherche où le nœud 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.

Usages

Ordonner des listes efficacement
Recherche beaucoup plus rapide que dans des tableaux et des listes chaînées
Insertion et suppression bien plus rapides que dans des tableaux
Sert à implanter des structures de données avancées :
- ensembles dynamiques
- tables de consultation
- files de priorité

Passons à la pratique !

Structures de données et algorithmes en Python