algorithm
Binaire zoekbomen

Invoering

Binaire zoekboom - Invoegen (Python)

Dit is een eenvoudige implementatie van Binary Search Tree Insertion met Python.

Hieronder ziet u een voorbeeld:

Volgend op het codefragment toont elke afbeelding de uitvoeringvisualisatie die het gemakkelijker maakt om te visualiseren hoe deze code werkt.

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)    

Binaire zoekboom - Verwijdering (C ++)

Voordat ik begin met verwijderen, wil ik alleen wat lichten plaatsen op wat een binaire zoekboom is (BST), elke knoop in een BST kan maximaal twee knooppunten hebben (linker en rechter kind). De linker subboom van een knoop heeft een sleutel kleiner dan of gelijk aan de sleutel van het bovenliggende knooppunt. De rechter substructuur van een knoop heeft een sleutel die groter is dan die van de sleutel van de bovenliggende knoop.

Een knooppunt in een boom verwijderen met behoud van de eigenschap Binaire zoekboom.

Er zijn drie gevallen waarmee rekening moet worden gehouden bij het verwijderen van een knooppunt.

• Geval 1: te verwijderen knoop is de bladknoop (knoop met waarde 22).
• Geval 2: te verwijderen knoop heeft één kind (knoop met waarde 26).
• Geval 3: het te verwijderen knooppunt heeft beide kinderen (knooppunt met waarde 49).

Verklaring van zaken:

1. Wanneer het te verwijderen knooppunt een bladknooppunt is, verwijdert u eenvoudig het knooppunt en geeft u nullptr aan het bovenliggende knooppunt.
2. Wanneer een te verwijderen knoop slechts één kind heeft, kopieert u de onderliggende waarde naar de knooppuntwaarde en verwijdert u het onderliggende (geconverteerd naar case 1)
3. Als een te verwijderen knoop twee childs heeft, kan het minimum uit de juiste subboom worden gekopieerd naar de knoop en vervolgens kan de minimumwaarde worden verwijderd uit de juiste substructuur van de knoop (omgezet in geval 2)

Opmerking: het minimum in de rechter subboom kan maximaal één kind hebben en dat te juiste kind als het het linker kind heeft, wat betekent dat dit niet de minimumwaarde is of dat het de eigenschap BST niet volgt.

De structuur van een knooppunt in een boom en de code voor verwijdering:

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

Tijdcomplexiteit van bovenstaande code is O ( h ), waarbij h de hoogte van de boom is.

Laagste gemeenschappelijke voorouder in een BST

Overweeg de BST:

De laagste gemeenschappelijke voorouder van 22 en 26 is 24

De laagste gemeenschappelijke voorouder van 26 en 49 is 46

De laagste gemeenschappelijke voorouder van 22 en 24 is 24

Binaire zoekboomeigenschap kan worden gebruikt voor het vinden van de laagste voorouder van knooppunten

Psuedo-code:

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

Binaire zoekboom - 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

"" "Maak een ander knooppunt en voeg gegevens erin" ""

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