Binaarotsingupuu

Lang L: none (table-of-contents)

Otsinguoperatsioon
Sisesta toiming
Kustutustoiming
Pythoni, Java ja C / C ++ näited
Binaarotsingupuu keerukus
Binaarotsingupuu rakendused

Selles õpetuses saate teada, kuidas binaarne otsingupuu töötab. Samuti leiate toimivaid näiteid binaarotsingupuust C, C ++, Java ja Python.

Binaarotsingupuu on andmestruktuur, mis võimaldab meil kiiresti pidada järjestatud arvude loendit.

Seda nimetatakse binaarpuuks, kuna igas puu sõlmes on maksimaalselt kaks last.
Seda nimetatakse otsingupuuks, kuna seda saab kasutada arvu olemasolu O(log(n))õigeaegseks otsimiseks .

Binaarotsingupuud tavalisest binaarpuust eraldavad omadused on

Kõik vasaku alampuu sõlmed on väiksemad kui juursõlm
Kõik parempoolse alampuu sõlmed on rohkem kui juursõlm
Samuti on iga sõlme mõlemad alampuud BST-d, st neil on kaks ülaltoodud omadust

Puu, millel on parem alampuu, mille üks väärtus on juurest väiksem, näidatakse, et see ei ole kehtiv binaarotsingupuu

Parempoolne binaarpuu ei ole binaarotsingupuu, kuna sõlme "3" parem alampuu sisaldab sellest väiksemat väärtust.

Binaarotsingupuul saate teha kahte põhitoimingut:

Otsinguoperatsioon

Algoritm sõltub BST omadusest, et kui igal vasakpoolsel alampuul on väärtused juure all ja igal paremal alamal on juure kohal.

Kui väärtus jääb juure alla, võime kindlalt öelda, et väärtus pole õiges alampuus; peame otsima ainult vasakust alampuust ja kui väärtus on juure kohal, võime kindlalt öelda, et väärtus pole vasakul alampuul; me peame otsima ainult õiges alampuus.

Algoritm:

 If root == NULL return NULL; If number == root->data return root->data; If number data return search(root->left) If number> root->data return search(root->right)

Proovime seda skeemiga visualiseerida.

4 ei leita, siis ei leita 8

4 vasakpoolset alampuud läbi, 3

4 parempoolse alampuu kaudu ei leita, siis leitakse 6

4 vasaku alampuu kaudu

Kui väärtus leitakse, tagastame väärtuse nii, et see leviks igas rekursioonietapis, nagu on näidatud alloleval pildil.

Kui olete märganud, oleme neli korda helistanud tagasipöördumise otsingu (struct node *). Kui tagastame kas uue sõlme või NULL, tagastatakse väärtus ikka ja jälle, kuni otsing (juur) tagastab lõpptulemuse.

Kui väärtus leitakse mõnes alampuus, levitatakse seda ülespoole nii, et see lõpuks tagastatakse, vastasel juhul tagastatakse null

Kui väärtust ei leita, jõuame lõpuks lehesõlme, mis on NULL, vasaku või parema lapseni ning see levib ja tagastatakse.

Sisesta toiming

Väärtuse sisestamine õigesse asendisse sarnaneb otsimisega, sest püüame säilitada reegli, et vasak alampuu on juurest väiksem ja parem alampuu on juurest suurem.

Jätkame kas paremale või vasakule alampuule sõltuvalt väärtusest ja kui jõuame punkti, on vasak või parem alampuu null, paneme uue sõlme sinna.

Algoritm:

 If node == NULL return createNode(data) if (data data) node->left = insert(node->left, data); else if (data> node->data) node->right = insert(node->right, data); return node;

Algoritm pole nii lihtne, kui see välja näeb. Proovime visualiseerida, kuidas lisame numbri olemasolevale BST-le.

4 <8 nii, põiki läbi 8

4> 3 vasaku lapse , põiki läbi 8

4 <6 parema lapse , põiki läbi 6 vasaku lapse põiki

4 Sisesta 4 kui 6 lapse vasak laps

Oleme sõlme kinnitanud, kuid peame siiski funktsioonist väljuma, kahjustamata ülejäänud puid. See on koht, kus return node;lõpp tuleb kasuks. Juhul NULL, kui vastloodud sõlm tagastatakse ja kinnitatakse vanemsõlmele, vastasel juhul tagastatakse sama sõlme ilma igasuguste muudatusteta, kui tõuseme üles, kuni jõuame tagasi juurte juurde.

See tagab, et kui liigume puust üles tagasi, ei muudeta muid sõlmeühendusi.

Pilt, mis näitab juurelemendi tagastamise olulisust lõpus, et elemendid ei kaotaks oma positsiooni ülespoole rekursioonisammul.

Kustutustoiming

Binaarotsingupuust sõlme kustutamiseks on kolm juhtumit.

I juhtum

Esimesel juhul on kustutatav sõlm lehesõlm. Sellisel juhul kustutage sõlm lihtsalt puust.

4 tuleb kustutada

Kustutage sõlm

II juhtum

Teisel juhul on kustutataval sõlmel üks alamsõlm. Sellisel juhul toimige järgmiselt.

Asendage see sõlm selle alamsõlmega.
Eemaldage lapse sõlm algsest asendist.

6 tuleb kustutada,

kopeerige tema lapse väärtus sõlme ja kustutage lapse

lõplik puu

III juhtum

Kolmandal juhul on kustutataval sõlmel kaks last. Sellisel juhul toimige järgmiselt.

Hankige selle sõlme järglane.
Asendage sõlm sisemise järeltulijaga.
Eemaldage tellimusjärglane oma algsest asendist.

3 tuleb kustutada

Kopeerige tellimusjärglase (4) väärtus sõlme.

Kustutage tellimusjärglane

Pythoni, Java ja C / C ++ näited

Python Java C C ++

 # Binary Search Tree operations in Python # Create a node class Node: def __init__(self, key): self.key = key self.left = None self.right = None # Inorder traversal def inorder(root): if root is not None: # Traverse left inorder(root.left) # Traverse root print(str(root.key) + "->", end=' ') # Traverse right inorder(root.right) # Insert a node def insert(node, key): # Return a new node if the tree is empty if node is None: return Node(key) # Traverse to the right place and insert the node if key < node.key: node.left = insert(node.left, key) else: node.right = insert(node.right, key) return node # Find the inorder successor def minValueNode(node): current = node # Find the leftmost leaf while(current.left is not None): current = current.left return current # Deleting a node def deleteNode(root, key): # Return if the tree is empty if root is None: return root # Find the node to be deleted if key root.key): root.right = deleteNode(root.right, key) else: # If the node is with only one child or no child if root.left is None: temp = root.right root = None return temp elif root.right is None: temp = root.left root = None return temp # If the node has two children, # place the inorder successor in position of the node to be deleted temp = minValueNode(root.right) root.key = temp.key # Delete the inorder successor root.right = deleteNode(root.right, temp.key) return root root = None root = insert(root, 8) root = insert(root, 3) root = insert(root, 1) root = insert(root, 6) root = insert(root, 7) root = insert(root, 10) root = insert(root, 14) root = insert(root, 4) print("Inorder traversal: ", end=' ') inorder(root) print("Delete 10") root = deleteNode(root, 10) print("Inorder traversal: ", end=' ') inorder(root)

 // Binary Search Tree operations in Java class BinarySearchTree ( class Node ( int key; Node left, right; public Node(int item) ( key = item; left = right = null; ) ) Node root; BinarySearchTree() ( root = null; ) void insert(int key) ( root = insertKey(root, key); ) // Insert key in the tree Node insertKey(Node root, int key) ( // Return a new node if the tree is empty if (root == null) ( root = new Node(key); return root; ) // Traverse to the right place and insert the node if (key root.key) root.right = insertKey(root.right, key); return root; ) void inorder() ( inorderRec(root); ) // Inorder Traversal void inorderRec(Node root) ( if (root != null) ( inorderRec(root.left); System.out.print(root.key + " -> "); inorderRec(root.right); ) ) void deleteKey(int key) ( root = deleteRec(root, key); ) Node deleteRec(Node root, int key) ( // Return if the tree is empty if (root == null) return root; // Find the node to be deleted if (key root.key) root.right = deleteRec(root.right, key); else ( // If the node is with only one child or no child if (root.left == null) return root.right; else if (root.right == null) return root.left; // If the node has two children // Place the inorder successor in position of the node to be deleted root.key = minValue(root.right); // Delete the inorder successor root.right = deleteRec(root.right, root.key); ) return root; ) // Find the inorder successor int minValue(Node root) ( int minv = root.key; while (root.left != null) ( minv = root.left.key; root = root.left; ) return minv; ) // Driver Program to test above functions public static void main(String() args) ( BinarySearchTree tree = new BinarySearchTree(); tree.insert(8); tree.insert(3); tree.insert(1); tree.insert(6); tree.insert(7); tree.insert(10); tree.insert(14); tree.insert(4); System.out.print("Inorder traversal: "); tree.inorder(); System.out.println("After deleting 10"); tree.deleteKey(10); System.out.print("Inorder traversal: "); tree.inorder(); ) )

 // Binary Search Tree operations in C #include #include struct node ( int key; struct node *left, *right; ); // Create a node struct node *newNode(int item) ( struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; ) // Inorder Traversal void inorder(struct node *root) ( if (root != NULL) ( // Traverse left inorder(root->left); // Traverse root printf("%d -> ", root->key); // Traverse right inorder(root->right); ) ) // Insert a node struct node *insert(struct node *node, int key) ( // Return a new node if the tree is empty if (node == NULL) return newNode(key); // Traverse to the right place and insert the node if (key key) node->left = insert(node->left, key); else node->right = insert(node->right, key); return node; ) // Find the inorder successor struct node *minValueNode(struct node *node) ( struct node *current = node; // Find the leftmost leaf while (current && current->left != NULL) current = current->left; return current; ) // Deleting a node struct node *deleteNode(struct node *root, int key) ( // Return if the tree is empty if (root == NULL) return root; // Find the node to be deleted if (key key) root->left = deleteNode(root->left, key); else if (key> root->key) root->right = deleteNode(root->right, key); else ( // If the node is with only one child or no child if (root->left == NULL) ( struct node *temp = root->right; free(root); return temp; ) else if (root->right == NULL) ( struct node *temp = root->left; free(root); return temp; ) // If the node has two children struct node *temp = minValueNode(root->right); // Place the inorder successor in position of the node to be deleted root->key = temp->key; // Delete the inorder successor root->right = deleteNode(root->right, temp->key); ) return root; ) // Driver code int main() ( struct node *root = NULL; root = insert(root, 8); root = insert(root, 3); root = insert(root, 1); root = insert(root, 6); root = insert(root, 7); root = insert(root, 10); root = insert(root, 14); root = insert(root, 4); printf("Inorder traversal: "); inorder(root); printf("After deleting 10"); root = deleteNode(root, 10); printf("Inorder traversal: "); inorder(root); )

 // Binary Search Tree operations in C++ #include using namespace std; struct node ( int key; struct node *left, *right; ); // Create a node struct node *newNode(int item) ( struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; ) // Inorder Traversal void inorder(struct node *root) ( if (root != NULL) ( // Traverse left inorder(root->left); // Traverse root cout  right); ) ) // Insert a node struct node *insert(struct node *node, int key) ( // Return a new node if the tree is empty if (node == NULL) return newNode(key); // Traverse to the right place and insert the node if (key key) node->left = insert(node->left, key); else node->right = insert(node->right, key); return node; ) // Find the inorder successor struct node *minValueNode(struct node *node) ( struct node *current = node; // Find the leftmost leaf while (current && current->left != NULL) current = current->left; return current; ) // Deleting a node struct node *deleteNode(struct node *root, int key) ( // Return if the tree is empty if (root == NULL) return root; // Find the node to be deleted if (key key) root->left = deleteNode(root->left, key); else if (key> root->key) root->right = deleteNode(root->right, key); else ( // If the node is with only one child or no child if (root->left == NULL) ( struct node *temp = root->right; free(root); return temp; ) else if (root->right == NULL) ( struct node *temp = root->left; free(root); return temp; ) // If the node has two children struct node *temp = minValueNode(root->right); // Place the inorder successor in position of the node to be deleted root->key = temp->key; // Delete the inorder successor root->right = deleteNode(root->right, temp->key); ) return root; ) // Driver code int main() ( struct node *root = NULL; root = insert(root, 8); root = insert(root, 3); root = insert(root, 1); root = insert(root, 6); root = insert(root, 7); root = insert(root, 10); root = insert(root, 14); root = insert(root, 4); cout << "Inorder traversal: "; inorder(root); cout << "After deleting 10"; root = deleteNode(root, 10); cout << "Inorder traversal: "; inorder(root); )