Šioje pamokoje sužinosite, kaip veikia dvejetainis paieškos medis. Taip pat rasite veikiančius dvejetainio paieškos medžio pavyzdžius C, C ++, Java ir Python.
Dvejetainis paieškos medis yra duomenų struktūra, leidžianti greitai išlaikyti surūšiuotą skaičių sąrašą.
- Jis vadinamas dvejetainiu medžiu, nes kiekviename medžio mazge yra daugiausia du vaikai.
- Jis vadinamas paieškos medžiu, nes juo galima laiku ieškoti skaičiaus buvimo
O(log(n)).
Savybės, skiriančios dvejetainį paieškos medį nuo įprasto dvejetainio medžio, yra
- Visi kairiojo potemio mazgai yra mažesni už šakninį mazgą
- Visi dešiniojo porūšio mazgai yra daugiau nei šakninis mazgas
- Abu kiekvieno mazgo potemiai taip pat yra BST, ty jie turi pirmiau nurodytas dvi savybes
Parodoma, kad medis, kurio dešinis potis yra vienas, mažesnis už šaknį, rodo, kad tai nėra tinkamas dvejetainis paieškos medis
Dešinysis dvejetainis medis nėra dvejetainis paieškos medis, nes dešiniajame mazgo „3“ medyje yra mažesnė už jį vertė.
Dvejetainiame paieškos medyje galite atlikti dvi pagrindines operacijas:
Paieškos operacija
Algoritmas priklauso nuo BST savybės, kad jei kiekvieno kairiojo potemio vertės yra žemiau šaknies, o kiekvieno dešiniojo potemio vertės yra virš šaknies.
Jei vertė yra žemiau šaknies, galime tiksliai pasakyti, kad reikšmė nėra dešiniajame pogrindyje; turime ieškoti tik kairiajame potemyje ir, jei reikšmė yra virš šaknies, galime tiksliai pasakyti, kad reikšmė nėra kairiajame potemyje; turime ieškoti tik tinkamame potemyje.
Algoritmas:
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)
Pabandykime tai pavaizduoti schema.
4 nerandama, kirsti per kairįjį 8 medį 
4 4 nerandama, nėra perėjimo per dešinįjį 3 
4 medį taip nėra, rastas per kairįjį 6 4 medį
Jei vertė randama, mes grąžiname vertę taip, kad ji būtų skleidžiama kiekviename rekurso etape, kaip parodyta paveikslėlyje žemiau.
Jei galbūt pastebėjote, mes keturis kartus iškvietėme grįžimo paiešką (struct node *). Kai grąžiname naują mazgą arba NULL, vertė vėl ir vėl grąžinama, kol paieška (šaknis) grąžins galutinį rezultatą.
Jei vertė randama bet kuriame iš pogrupių, ji perduodama taip, kad galų gale ji būtų grąžinta, kitaip grąžinama nulinė vertė
Jei reikšmė nerandama, galų gale pasiekiame kairįjį arba dešinįjį lapo mazgo, kuris yra NULL, vaiką ir jis gausinamas ir grąžinamas.
Įterpti operaciją
Vertės įterpimas į teisingą padėtį yra panašus į paiešką, nes mes stengiamės išlaikyti taisyklę, kad kairysis potis yra mažesnis už šaknį, o dešinysis - didesnis už šaknį.
Atsižvelgdami į vertę, mes einame į dešinįjį arba į kairįjį medį. Kai pasieksime tašką, kairysis arba dešinysis potis yra nulinis, mes įdėjome naują mazgą.
Algoritmas:
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;
Algoritmas nėra toks paprastas, kaip atrodo. Pabandykime įsivaizduoti, kaip prie esamo BST pridedame skaičių.
4 <8 taip, skersai per kairįjį 8 
4> 3 vaiką , skersai per dešinįjį 8 
4 <6 taip, skersai per kairįjį 6 vaikų 
įstatykite 4 kaip kairįjį 6 vaikų vaiką
Mes prijungėme mazgą, bet vis tiek turime išeiti iš funkcijos, nepadarydami žalos likusiam medžiui. Čia return node;praverčia pabaiga. Tuo atveju NULL, naujai sukurta mazgas grįžo ir prie patronuojančios mazgas, kitaip tas pats mazgas grįžo nekeičiant, kaip mes einame iki kol mes grįžti į šaknis.
Tai užtikrina, kad judant atgal į medį, kiti mazgų ryšiai nebus pakeisti.
Vaizdas, rodantis pagrindinio elemento grąžinimo svarbą pabaigoje, kad elementai neprarastų savo pozicijos atlikdami rekursijos į viršų žingsnį.
Ištrynimo operacija
Yra trys atvejai, kaip ištrinti mazgą iš dvejetainės paieškos medžio.
I atvejis
Pirmuoju atveju mazgas, kurį reikia ištrinti, yra lapo mazgas. Tokiu atveju paprasčiausiai ištrinkite mazgą iš medžio.
4 turi būti ištrintas 
Ištrinkite mazgą
II atvejis
Antruoju atveju mazgas, kurį reikia ištrinti, turi vieną antrinį mazgą. Tokiu atveju atlikite šiuos veiksmus:
- Pakeiskite tą mazgą jo antriniu mazgu.
- Nuimkite vaiko mazgą iš pradinės padėties.
6 turi būti ištrinta, 
nukopijuokite savo vaiko vertę į mazgą ir ištrinkite vaiko 
galutinį medį
III atvejis
Trečiu atveju ištrintinas mazgas turi du vaikus. Tokiu atveju atlikite šiuos veiksmus:
- Gaukite užsakymą to mazgo perėmėjui.
- Pakeiskite mazgą užsakymo perėmėju.
- Pašalinkite vidinį įpėdinį iš pradinės padėties.
3 turi būti ištrinta Kopijuokite užsakymo įpėdinio (4) vertę į mazgą 
Ištrinkite užsakymo perėmėją
„Python“, „Java“ ir „C / C ++“ pavyzdžiai
„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); )
Dvejetainių paieškos medžių kompleksai
Laiko kompleksiškumas
| Operacija | Geriausio atvejo sudėtingumas | Vidutinis atvejų sudėtingumas | Blogiausio atvejo sudėtingumas |
| Paieška | O (log n) | O (log n) | O (n) |
| Įterpimas | O (log n) | O (log n) | O (n) |
| Ištrinti | O (log n) | O (log n) | O (n) |
Čia n yra medžio mazgų skaičius.
Erdvės sudėtingumas
Visų operacijų erdvės sudėtingumas yra O (n).
Dvejetainių paieškos medžių programos
- Daugiapakopiame indeksavime duomenų bazėje
- Dinamiškam rūšiavimui
- Virtualioms atminties sritims „Unix“ branduolyje tvarkyti
