algorithm
Alberi di ricerca binaria

introduzione

Albero di ricerca binario - Insertion (Python)

Questa è una semplice implementazione di Binary Search Tree Insertion usando Python.

Un esempio è mostrato di seguito:

Seguendo lo snippet di codice ogni immagine mostra la visualizzazione dell'esecuzione che rende più facile visualizzare come funziona questo codice.

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)    

Albero di ricerca binario - Eliminazione (C ++)

Prima di iniziare con la cancellazione voglio solo mettere un po 'di luce su cosa è un albero di ricerca binario (BST), Ogni nodo in un BST può avere un massimo di due nodi (figlio sinistro e destro). Il sottoalbero sinistro di un nodo ha un chiave minore o uguale alla chiave del suo nodo genitore. Il sottoalbero destro di un nodo ha una chiave maggiore rispetto alla chiave del suo nodo genitore.

Eliminazione di un nodo in un albero mantenendo la proprietà della struttura di ricerca binaria.

Ci sono tre casi da considerare durante l'eliminazione di un nodo.

• Caso 1: il nodo da eliminare è il nodo foglia (nodo con valore 22).
• Caso 2: il nodo da eliminare ha un figlio (il nodo con valore 26).
• Caso 3: il nodo da cancellare ha entrambi i figli. (Nodo con valore 49).

Spiegazione dei casi:

1. Quando il nodo da eliminare è un nodo foglia, elimina semplicemente il nodo e passa nullptr al nodo principale.
2. Quando un nodo da eliminare ha un solo figlio, copia il valore figlio sul valore del nodo ed elimina il figlio (Convertito in caso 1)
3. Quando un nodo da eliminare ha due figli, il minimo dalla sua sottostruttura di destra può essere copiato sul nodo e quindi il valore minimo può essere eliminato dalla sottostruttura di destra del nodo (convertito in caso 2)

Nota: il minimo nell'albero secondario destro può avere un massimo di un figlio e anche quello di destra se ha il figlio sinistro che significa che non è il valore minimo o che non sta seguendo la proprietà BST.

La struttura di un nodo in un albero e il codice per l'eliminazione:

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 complessità temporale del codice precedente è O ( h ), dove h è l'altezza dell'albero.

Il più basso antenato comune in una BST

Considera il BST:

Il più basso antenato comune tra 22 e 26 è 24

Il più basso antenato comune tra 26 e 49 è 46

L'antenato più comune di 22 e 24 è 24

La proprietà dell'albero di ricerca binaria può essere utilizzata per trovare l'antenato più basso dei nodi

Codice 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);
      }
        }

Albero di ricerca binario - 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

"" "Crea un nodo diverso e inserisci i dati in esso" ""

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))