Arbre binaire de recherche (ABR)

Structures de données et algorithmes en Python

Miriam Antona

Software engineer

Définition

Sous-arbre gauche d’un nœud :
- valeurs inférieures au nœud
Sous-arbre droit d’un nœud :
- valeurs supérieures au nœud
Les sous-arbres gauche et droit doivent être des ABR

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

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 de recherche binaire.

Recherche

Rechercher 72

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

Recherche

Rechercher 72

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

Recherche

Rechercher 72

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

Recherche

Rechercher 72

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

Recherche

Rechercher 72

Représentation schématique d’un arbre binaire de recherche où le nouveau nœud racine est coloré en jaune et le reste des nœuds en gris. Le nœud coloré porte le numéro 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 le 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 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 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 de recherche binaire avec certains éléments. Le nœud racine est 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 de recherche binaire avec certains é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 de recherche binaire 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 de recherche binaire 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 de certains éléments d’un arbre binaire de recherche.

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 de recherche binaire avec certains é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 de recherche binaire avec certains éléments. Le current_node est l'enfant droit de la racine. Le nouveau nœud est l'enfant gauche de current_node.

Suppression

Pas d’enfants

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

Suppression

Aucun enfant
- le supprimer

Représentation graphique d’un arbre de recherche binaire avec certains éléments. Le nœud qui devait être supprimé a disparu de l’arbre.

Suppression

Un enfant

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

Suppression

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

Représentation graphique d’un arbre de recherche binaire avec certains éléments. Le nœud qui devait être supprimé a disparu de l’arbre et le nœud racine pointe vers l'enfant droit du nœud supprimé.

Suppression

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

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

Suppression

Deux enfants

Représentation graphique d’un arbre de recherche binaire où le nœud racine va être supprimé et est coloré en rouge.

Suppression

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

Représentation graphique d’un arbre de recherche binaire où le nœud racine va être supprimé et est coloré en rouge.

Suppression

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

Représentation graphique d’un arbre de recherche binaire où le nœud racine va être supprimé et est coloré en rouge. L'enfant droit de la racine est coloré en jaune.

Suppression

Deux enfants
- le remplacer par son successeur
  - le nœud ayant la plus petite valeur supérieure à la valeur du nœud
- trouver successeur :
  - visiter l’enfant de droite
  - continuer à visiter les nœuds de gauche jusqu’à la fin

Représentation graphique d’un arbre de recherche binaire où le nœud racine va être supprimé et est coloré en rouge. Un autre nœud est coloré en jaune afin de trouver le successeur.

Suppression

Deux enfants
- le remplacer par son successeur
  - le nœud ayant la plus petite valeur supérieure à la valeur du nœud
- trouver successeur :
  - visiter l’enfant de droite
  - continuer à visiter les nœuds de gauche jusqu’à la fin

Représentation graphique d’un arbre de recherche binaire où le nœud racine va être supprimé et est coloré en rouge. Un autre nœud est coloré en jaune afin de trouver le successeur.

Suppression

Deux enfants
- le remplacer par son successeur
  - le nœud ayant la plus petite valeur supérieure à la valeur du nœud
- trouver successeur :
  - visiter l’enfant de droite
  - continuer à visiter les nœuds de gauche jusqu’à la fin

Représentation graphique d’un arbre de recherche binaire où le nœud racine va être supprimé et est coloré en rouge. Un autre nœud est coloré en jaune afin de trouver le successeur. Le successeur a été trouvé et c’est le numéro 13.

Suppression

Deux enfants
- le remplacer par son successeur
  - le nœud ayant la plus petite valeur supérieure à la valeur du nœud
- trouver successeur :
  - visiter l’enfant de droite
  - continuer à visiter les nœuds de gauche jusqu’à la fin

Représentation graphique d'un arbre de recherche binaire. 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 à la valeur du nœud
- trouver successeur :
  - visiter l’enfant de droite
  - continuer à visiter les nœuds de gauche jusqu’à la fin
  - si successeur a un enfant droit :

Représentation graphique d’un arbre de recherche binaire 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 à la valeur du nœud
- trouver successeur :
  - visiter l’enfant de droite
  - continuer à visiter les nœuds de gauche jusqu’à la fin
  - si successeur a un enfant droit :
    - l’enfant devient l’enfant gauche du parent du successeur.

Représentation graphique d’un arbre de recherche binaire où le nœud successeur avait un enfant droit. L’enfant successeur est devenu l’enfant gauche du parent du successeur et le nœud racine a été remplacé par le nœud successeur.

Utilisations

Ordonner listes efficacement
Plus rapide pour recherche que tables et listes chaînées
Plus rapide pour insérer et supprimer que tables
Utilisé pour implémenter structures plus avancées :
- ensembles dynamiques
- tables de recherche
- files d’attente prioritaires

Passons à la pratique !

Structures de données et algorithmes en Python