algorithm
Binära sökträd

Introduktion

Binary Search Tree - Insertion (Python)

Detta är en enkel implementering av Insättning av binärt sökträd med Python.

Ett exempel visas nedan:

Efter kodavsnittet visar varje bild exekveringsvisualiseringen vilket gör det lättare att visualisera hur den här koden fungerar.

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)    

Binary Search Tree - Radering (C ++)

Innan jag börjar med borttagning vill jag bara sätta några lampor på vad som är ett binärt sökträd (BST). Varje nod i en BST kan ha högst två noder (vänster och höger barn). Det vänstra underträdet i en nod har en nyckel som är mindre än eller lika med nyckelns överordnade nod. Det högra underträdet i en nod har en nyckel som är större än till dess huvudnodens nyckel.

Ta bort en nod i ett träd medan du behåller dess egendom för binär sökträd.

Det finns tre fall som ska beaktas när du tar bort en nod.

• Fall 1: Noden som ska raderas är bladnoden. (Nod med värde 22).
• Fall 2: Noden som ska raderas har ett barn (nod med värdet 26).
• Fall 3: Noden som ska raderas har båda barnen (nod med värdet 49).

Förklaring av ärenden:

1. När den nod som ska raderas är en bladnod raderar du bara noden och nullptr till dess överordnade nod.
2. När en nod som ska raderas endast har ett barn kopierar du barnvärdet till nodvärdet och raderar barnet (konverteras till fall 1)
3. När en nod som ska raderas har två barn kan minima från dess högra underträd kopieras till noden och då kan minimivärdet tas bort från nodens högra undertråd (Konverterat till fall 2)

Obs: Minimet i det högra underträdet kan ha högst ett barn och det för högra barnet om det har det vänstra barnet som betyder att det inte är minimivärdet eller inte följer BST-egenskapen.

Strukturen för en nod i ett träd och koden för radering:

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

Tidskomplexiteten för koden ovan är O ( h ), där h är trädets höjd.

Lägsta vanliga förfader i en BST

Tänk på BST:

Den lägsta vanliga förfäder till 22 och 26 är 24

Lågaste vanliga förfader av 26 och 49 är 46

Den lägsta vanliga förfäder till 22 och 24 är 24

Egenskaper för binär sökträd kan användas för att hitta noder för lägsta förfader

Psuedo-kod:

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

Binary Search Tree - 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

"" "Skapa annan nod och sätt in data i den" ""

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