algorithm
Drzewa wyszukiwania binarnego

Wprowadzenie

Drzewo wyszukiwania binarnego - wstawianie (Python)

Jest to prosta implementacja wstawiania drzewa wyszukiwania binarnego za pomocą Pythona.

Przykład jest pokazany poniżej:

Po fragmencie kodu każdy obraz pokazuje wizualizację wykonania, co ułatwia wizualizację działania tego kodu.

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)    

Drzewo wyszukiwania binarnego - usuwanie (C ++)

Zanim zacznę od usuwania, chcę po prostu zapalić trochę światła na czym jest drzewo wyszukiwania binarnego (BST). Każdy węzeł w BST może mieć maksymalnie dwa węzły (lewy i prawy potomek). Lewe pod-drzewo węzła ma klucz mniejszy lub równy kluczowi swojego węzła nadrzędnego. Prawe drzewo podrzędne węzła ma klucz większy niż klucz jego nadrzędnego węzła.

Usuwanie węzła z drzewa przy zachowaniu jego właściwości drzewa wyszukiwania binarnego.

Podczas usuwania węzła należy wziąć pod uwagę trzy przypadki.

• Przypadek 1: Węzłem do usunięcia jest węzeł liścia (węzeł o wartości 22).
• Przypadek 2: Węzeł do usunięcia ma jedno dziecko (Węzeł o wartości 26).
• Przypadek 3: Węzeł, który ma zostać usunięty, ma oboje dzieci (Węzeł o wartości 49).

Wyjaśnienie przypadków:

1. Gdy węzeł do usunięcia jest węzłem typu liść, po prostu usuń węzeł i przekaż nullptr do jego węzła nadrzędnego.
2. Jeśli węzeł, który ma zostać usunięty, ma tylko jedno dziecko, skopiuj wartość dziecka do wartości węzła i usuń dziecko (Przekształcony w przypadek 1)
3. Gdy węzeł, który ma zostać usunięty, ma dwa elementy potomne, to minimum z jego prawego poddrzewa można skopiować do węzła, a następnie minimalną wartość można usunąć z prawego poddrzewa węzła (przekonwertowane na przypadek 2)

Uwaga: Minimum w prawym drzewie podrzędnym może mieć maksymalnie jedno dziecko i to zbyt prawe dziecko, jeśli ma lewe dziecko, co oznacza, że nie jest to minimalna wartość lub nie jest zgodne z właściwością BST.

Struktura węzła w drzewie i kod do usunięcia:

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

Złożoność czasowa powyższego kodu wynosi O ( h ), gdzie h jest wysokością drzewa.

Najniższy wspólny przodek w BST

Rozważ BST:

Najniższy wspólny przodek 22 i 26 to 24

Najniższy wspólny przodek 26 i 49 to 46

Najniższy wspólny przodek 22 i 24 to 24

Właściwość drzewa wyszukiwania binarnego może być używana do znajdowania węzłów o najniższym przodku

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

Drzewo wyszukiwania binarnego - 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

„” „Utwórz inny węzeł i wstaw do niego dane” „”

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