algorithm
Arbres de recherche binaire

Introduction

Arbre de recherche binaire - Insertion (Python)

Ceci est une implémentation simple de l'insertion d'arbre de recherche binaire utilisant Python.

Un exemple est présenté ci-dessous:

Suivant l'extrait de code, chaque image montre la visualisation de l'exécution, ce qui facilite la visualisation de son fonctionnement.

class Node:
    def __init__(self, val):
        self.l_child = None
        self.r_child = None
        self.data = val

def insert(root, node):
    if root is None:
        root = node
    else:
        if root.data > node.data:
            if root.l_child is None:
                root.l_child = node
            else:
                insert(root.l_child, node)
        else:
            if root.r_child is None:
                root.r_child = node
            else:
                insert(root.r_child, node)

def in_order_print(root):
    if not root:
        return
    in_order_print(root.l_child)
    print root.data
    in_order_print(root.r_child)

def pre_order_print(root):
    if not root:
        return        
    print root.data
    pre_order_print(root.l_child)
    pre_order_print(root.r_child)    

Arbre de recherche binaire - Suppression (C ++)

Avant de commencer avec la suppression, je veux juste mettre quelques lumières sur ce qu'est un arbre de recherche binaire (BST). Chaque nœud dans un fichier BST peut avoir au maximum deux nœuds (enfant gauche et droit). Le sous-arbre gauche d'un nœud a un clé inférieure ou égale à la clé de son nœud parent. Le sous-arbre droit d'un nœud a une clé plus grande que la clé de son nœud parent.

Suppression d'un nœud dans une arborescence tout en conservant sa propriété d'arborescence de recherche binaire.

Il y a trois cas à prendre en compte lors de la suppression d'un nœud.

• Cas 1: Le nœud à supprimer est le nœud feuille (nœud avec la valeur 22).
• Cas 2: le nœud à supprimer a un enfant (nœud avec la valeur 26).
• Cas 3: le nœud à supprimer comporte les deux enfants (nœud avec la valeur 49).

Explication des cas:

1. Lorsque le nœud à supprimer est un nœud feuille, supprimez simplement le nœud et transmettez nullptr à son nœud parent.
2. Lorsqu'un noeud à supprimer ne possède qu'un seul enfant, copiez la valeur enfant dans la valeur du noeud et supprimez le fils (converti en cas 1).
3. Lorsqu'un nœud à supprimer possède deux enfants, le minimum de son sous-arbre droit peut être copié sur le nœud, puis la valeur minimale peut être supprimée du sous-arbre droit du nœud (converti en cas 2).

Remarque: Le minimum dans la sous-arborescence de droite peut avoir au maximum un enfant et cet enfant si c'est le cas si l'enfant de gauche signifie qu'il ne s'agit pas de la valeur minimale ou s'il ne suit pas la propriété BST.

La structure d'un nœud dans un arbre et le code pour la suppression:

struct node
{
    int data;
    node *left, *right;
};

node* delete_node(node *root, int data)
{
  if(root == nullptr) return root;
  else if(data < root->data) root->left  = delete_node(root->left, data);
  else if(data > root->data) root->right = delete_node(root->right, data);

  else
  {
    if(root->left == nullptr && root->right == nullptr) // Case 1
    {
      free(root);
      root = nullptr;
    }
    else if(root->left == nullptr)       // Case 2
    {
       node* temp = root;
       root= root->right;
       free(temp);
    }
    else if(root->right == nullptr)      // Case 2
    {
       node* temp = root;
       root = root->left;
       free(temp);
    }
    else                                 // Case 3
    {
       node* temp = root->right;

       while(temp->left != nullptr) temp = temp->left;

       root->data = temp->data;
       root->right = delete_node(root->right, temp->data);
    }
  }
  return root;
}

La complexité temporelle du code ci-dessus est O ( h ), où h est la hauteur de l'arbre.

Ancêtre commun le plus bas dans un BST

Considérons le BST:

Le plus petit ancêtre commun de 22 et 26 est de 24

Le plus petit ancêtre commun de 26 et 49 est de 46

Le plus petit ancêtre commun de 22 et 24 est de 24

La propriété d'arbre de recherche binaire peut être utilisée pour trouver l'ancêtre le plus bas des noeuds

Code Psuedo:

lowestCommonAncestor(root,node1, node2){

if(root == NULL)    
return NULL;



 else if(node1->data == root->data || node2->data== root->data)    
    return root;
    
    else if((node1->data <= root->data && node2->data > root->data)
              || (node2->data <= root->data && node1->data > root->data)){
        
             return root;
    }
    
    else if(root->data > max(node1->data,node2->data)){
            return lowestCommonAncestor(root->left, node1, node2);
    }
        
        else {
            return lowestCommonAncestor(root->right, node1, node2);
      }
        }

Arbre de recherche binaire - Python

class Node(object):
    def __init__(self, val):
        self.l_child = None
        self.r_child = None
        self.val = val


class BinarySearchTree(object):
    def insert(self, root, node):
        if root is None:
            return node

        if root.val < node.val:
            root.r_child = self.insert(root.r_child, node)
        else:
            root.l_child = self.insert(root.l_child, node)

        return root


    def in_order_place(self, root):
        if not root:
            return None
        else:
            self.in_order_place(root.l_child)
            print root.val
            self.in_order_place(root.r_child)

    def pre_order_place(self, root):
        if not root:
            return None
        else:
            print root.val
            self.pre_order_place(root.l_child)
            self.pre_order_place(root.r_child)

    def post_order_place(self, root):
        if not root:
            return None
        else:
            self.post_order_place(root.l_child)
            self.post_order_place(root.r_child)
            print root.val

"" "Créer un noeud différent et y insérer des données" ""

r = Node(3)
node = BinarySearchTree()
nodeList = [1, 8, 5, 12, 14, 6, 15, 7, 16, 8]

for nd in nodeList:
    node.insert(r, Node(nd))

print "------In order ---------"
print (node.in_order_place(r))
print "------Pre order ---------"
print (node.pre_order_place(r))
print "------Post order ---------"
print (node.post_order_place(r))