logo

TechCodeview

Sletning i binært søgetræ (BST)

Givet en BST , opgaven er at slette en node i denne BST , som kan opdeles i 3 scenarier:

Tilfælde 1. Slet en bladknude i BST

d1

Sletning i BST




Case 2. Slet en node med enkelt barn i BST

Sletning af en enkelt underordnet node er også enkel i BST. Kopier barnet til noden og slet noden .




fil

Sletning i BST


Tilfælde 3. Slet en node med begge børn i BST

Det er ikke så nemt at slette en node med begge børn. Her skal vi slet noden er sådan, at det resulterende træ følger egenskaberne for en BST.



mylivecricket ind til live cricket

Tricket er at finde nodens efterfølger i uorden. Kopier indholdet af inorder-efterfølgeren til noden, og slet inorder-efterfølgeren.

Bemærk: Inorder forgænger kan også bruges.


d3

Sletning i binært træ


hiba bukhari

Bemærk: Efterfølger er kun nødvendig, når det rigtige barn ikke er tomt. I dette særlige tilfælde kan den inordnede efterfølger fås ved at finde minimumsværdien i nodens højre underordnede.

Anbefalet praksis Slet en node fra BST Prøv det!

Implementering af sletningsoperation i en BST:

C++ 
#include  using namespace std; struct Node {  int key;  struct Node *left, *right; }; // A utility function to create a new BST node Node* newNode(int item) {  Node* temp = new Node;  temp->nøgle = vare;  temp->venstre = temp->højre = NULL;  retur temp; } // En hjælpefunktion til at udføre inorder-gennemgang af BST void inorder(Node* root) { if (root != NULL) { inorder(root->left);  printf('%d ', root->nøgle);  inorder(rod->højre);  } } /* En hjælpefunktion til at indsætte en ny node med givet nøgle i * BST */ Node* insert(Node* node, int key) { /* Hvis træet er tomt, returner en ny node */ if (node ​​= = NULL) returner nyNode(nøgle);  /* Ellers går du igen ned i træet */ if (tast< node->key) node->venstre = indsæt(node->venstre, nøgle);  else node->right = insert(node->right, key);  /* returner (uændret) nodemarkør */ return node; } /* Givet et binært søgetræ og en nøgle, sletter denne funktion nøglen og returnerer den nye rod */ Node* deleteNode(Node* rod, int k) { // Base case if (root == NULL) return rod;  // Hvis nøglen, der skal slettes, er mindre end rodens nøgle, // så ligger den i venstre undertræ, hvis (k< root->key) { root->left = deleteNode(rod->venstre, k);  returnere rod;  } // Hvis nøglen, der skal slettes, er større end rodens nøgle, // så ligger den i det højre undertræ ellers hvis (k> root->key) { root->right = deleteNode(root->right , k);  returnere rod;  } // Hvis nøglen er den samme som root's nøgle, så er dette noden, der skal slettes // Node med kun ét underordnet eller intet underordnet, hvis (rod->venstre == NULL) { Node* temp = root-> højre;  slet rod;  retur temp;  } else if (rod->højre == NULL) { Node* temp = root->venstre;  slet rod;  retur temp;  } // Node med to børn: Hent efterfølgeren i uorden (mindst // i højre undertræ) Node* succParent = root;  Node* succ = root->right;  while (succ->venstre != NULL) { succParent = succ;  succ = succ->venstre;  } // Kopier efterfølgerens indhold til denne node root->key = succ->key;  // Delete the inorder successor if (succParent->left == succ) succParent->left = succ->right;  else succParent->right = succ->right;    slette succ;  returnere rod; } // Driverkode int main() { /* Lad os oprette følgende BST 50 /  30 70 /  /  20 40 60 80 */ Node* root = NULL;  root = indsæt(rod, 50);  root = indsæt(rod, 30);  root = indsæt(rod, 20);  root = indsæt(rod, 40);  root = indsæt(rod, 70);  root = indsæt(rod, 60);  root = indsæt(rod, 80);  printf('Original BST: ');  inorder(rod);    printf('

Slet en bladknude: 20
');  root = deleteNode(rod, 20);  printf('Ændret BST-træ efter sletning af Leaf Node:
');  inorder(rod);  printf('

Slet node med enkelt barn: 70
');  root = deleteNode(rod, 70);  printf('Ændret BST-træ efter sletning af enkelt underordnet node:
');  inorder(rod);  printf('

Slet node med begge underordnede: 50
');  root = deleteNode(rod, 50);  printf('Ændret BST-træ efter sletning af begge underordnede Node:
');  inorder(rod);  retur 0; }>
C 
#include  #include  struct Node {  int key;  struct Node *left, *right; }; // A utility function to create a new BST node struct Node* newNode(int item) {  struct Node* temp = (struct Node*)malloc(sizeof(struct Node));  temp->nøgle = vare;  temp->venstre = temp->højre = NULL;  retur temp; } // En hjælpefunktion til at udføre inorder-gennemgang af BST void inorder(struct Node* root) { if (root != NULL) { inorder(root->left);  printf('%d ', root->nøgle);  inorder(rod->højre);  } } /* En hjælpefunktion til at indsætte en ny node med en given nøgle i BST */ struct Node* insert(struct Node* node, int key) { /* Hvis træet er tomt, returner en ny node */ if (node == NULL) returner nyNode(nøgle);  /* Ellers går du igen ned i træet */ if (tast< node->key) node->venstre = indsæt(node->venstre, nøgle);  else node->right = insert(node->right, key);  /* returner (uændret) nodemarkør */ return node; } /* Givet et binært søgetræ og en nøgle, sletter denne funktion nøglen og returnerer den nye rod */ struct Node* deleteNode(struct Node* root, int k) { // Base case if (root == NULL) return rod;  // Hvis nøglen, der skal slettes, er mindre end rodens nøgle, så ligger den i venstre undertræ, hvis (k< root->key) { root->left = deleteNode(rod->venstre, k);  returnere rod;  } // Hvis nøglen, der skal slettes, er større end rodens nøgle, så ligger den i det højre undertræ ellers hvis (k> root->key) { root->right = deleteNode(root->right, k );  returnere rod;  } // Hvis nøglen er den samme som root's nøgle, så er dette noden, der skal slettes // Node med kun ét underordnet eller intet underordnet, hvis (root->venstre == NULL) { struct Node* temp = root-> højre;  fri(rod);  retur temp;  } else if (rod->højre == NULL) { struct Node* temp = root->venstre;  fri(rod);  retur temp;  } // Node med to børn: Hent efterfølgeren i uorden (mindst i højre undertræ) struct Node* succParent = root;  struct Node* succ = root->right;  while (succ->venstre != NULL) { succParent = succ;  succ = succ->venstre;  } // Kopier efterfølgerens indhold til denne node root->key = succ->key;  // Delete the inorder successor if (succParent->left == succ) succParent->left = succ->right;  else succParent->right = succ->right;  fri(succ);  returnere rod; } // Driverkode int main() { /* Lad os oprette følgende BST 50 /  30 70 /  /  20 40 60 80 */ struct Node* root = NULL;  root = indsæt(rod, 50);  indsæt(rod, 30);  indsæt(rod, 20);  indsæt(rod, 40);  indsæt(rod, 70);  indsætte(rod, 60);  indsæt(rod, 80);  printf('Original BST: ');  inorder(rod);    printf('

Slet en bladknude: 20
');  root = deleteNode(rod, 20);  printf('Ændret BST-træ efter sletning af Leaf Node:
');  inorder(rod);  printf('

Slet node med enkelt barn: 70
');  root = deleteNode(rod, 70);  printf('Ændret BST-træ efter sletning af enkelt underordnet node:
');  inorder(rod);  printf('

Slet node med begge underordnede: 50
');  root = deleteNode(rod, 50);  printf('Ændret BST-træ efter sletning af begge underordnede Node:
');  inorder(rod);  retur 0; }>
Java 
class Node {  int key;  Node left, right;  Node(int item) {  key = item;  left = right = null;  } } class BinaryTree {  Node root;  BinaryTree() {  root = null;  }  // A utility function to insert a new node with the given key  Node insert(Node node, int key) {  // If the tree is empty, return a new node  if (node == null) {  return new Node(key);  }  // Otherwise, recur down the tree  if (key < node.key) {  node.left = insert(node.left, key);  } else if (key>node.key) { node.right = insert(node.right, key);  } // returnere (uændret) node pointer return node;  } // En hjælpefunktion til at udføre inorder-gennemgang af BST void inorder(Node root) { if (root != null) { inorder(root.left);  System.out.print(root.key + ' ');  inorder(root.right);  } } // Givet et binært søgetræ og en nøgle, sletter denne funktion nøglen og returnerer den nye root Node deleteNode(Node root, int key) { // Grundtal if (root == null) { return root;  } // Hvis nøglen, der skal slettes, er mindre end rodens nøgle, så ligger den i venstre undertræ, hvis (nøgle< root.key) {  root.left = deleteNode(root.left, key);  }  // If the key to be deleted is greater than the root's key, then it lies in the right subtree  else if (key>root.key) { root.right = deleteNode(root.right, nøgle);  } // Hvis nøglen er den samme som root's nøgle, så er dette noden, der skal slettes ellers { // Node med kun ét underordnet eller intet underordnet if (root.left == null) { return root.right;  } else if (root.right == null) { return root.left;  } // Node med to børn: Hent efterfølgeren i uorden (mindst i højre undertræ) root.key = minValue(root.right);  // Delete the inorder successor root.right = deleteNode(root.right, root.key);  } returnere rod;  } int minValue(Node rod) { int minv = root.key;  while (root.left != null) { minv = root.left.key;  root = root.venstre;  } returner minv;  } // Driver Code public static void main(String[] args) { BinaryTree tree = new BinaryTree();  /* Lad os oprette følgende BST 50 /  30 70 /  /  20 40 60 80 */ tree.root = tree.insert(tree.root, 50);  tree.insert(tree.root, 30);  træ.indsæt(træ.rod, 20);  træ.indsæt(træ.rod, 40);  træ.indsæt(træ.rod, 70);  træ.indsæt(træ.rod, 60);  træ.indsæt(træ.rod, 80);  System.out.print('Original BST: ');  træ.inorder(træ.rod);  System.out.println();  System.out.println('
Slet en bladknude: 20');  tree.root = tree.deleteNode(træ.rod, 20);  System.out.print('Ændret BST-træ efter sletning af Leaf Node:
');  træ.inorder(træ.rod);  System.out.println();  System.out.println('
Slet node med enkelt barn: 70');  tree.root = tree.deleteNode(træ.rod, 70);  System.out.print('Ændret BST-træ efter sletning af enkelt underordnet node:
');  træ.inorder(træ.rod);  System.out.println();  System.out.println('
Slet node med begge underordnede: 50');  tree.root = tree.deleteNode(træ.rod, 50);  System.out.print('Ændret BST-træ efter sletning af begge underordnede Node:
');  træ.inorder(træ.rod);  } }>
Python3 
class Node: def __init__(self, key): self.key = key self.left = None self.right = None class BinaryTree: def __init__(self): self.root = None # A utility function to insert a new node with the given key def insert(self, node, key): # If the tree is empty, return a new node if node is None: return Node(key) # Otherwise, recur down the tree if key < node.key: node.left = self.insert(node.left, key) elif key>node.key: node.right = self.insert(node.right, key) # returner den (uændrede) node pointer return node # En hjælpefunktion til at udføre en rækkefølgegennemgang af BST def inorder(self, root): if root: self .inorder(root.left) print(root.key, end=' ') self.inorder(root.right) # Givet et binært søgetræ og en nøgle, sletter denne funktion nøglen og returnerer den nye root def deleteNode (selv, rod, nøgle): # Grundbogstav, hvis rod er Ingen: returner rod # Hvis nøglen, der skal slettes, er mindre end rodnøgle, så ligger den i venstre undertræ, hvis nøgle< root.key: root.left = self.deleteNode(root.left, key) # If the key to be deleted is greater than the root's key, then it lies in the right subtree elif key>root.key: root.right = self.deleteNode(root.right, key) # Hvis nøglen er den samme som roots nøgle, så er dette den node, der ellers skal slettes: # Node med kun et underordnet eller intet underordnet, hvis root.left er Ingen: return root.right elif root.right er Ingen: return root.left # Node med to børn: Hent efterfølgeren i rækkefølgen (mindst i højre undertræ) root.key = self.minValue(root.right) # Slet efterfølgeren root.right = self.deleteNode(root.right, root.key) returner root def minValue(self, root): minv = root.key mens root.left: minv = root.left.key root = root.left returner minv # Driverkode hvis __navn__ == '__main__': træ = BinaryTree() # Lad os oprette følgende BST # 50 # /  # 30 70 # /  /  # 20 40 60 80 tree.root = træ.indsæt(træ.rod, 50) træ.indsæt(træ.rod, 30) træ.indsæt(træ.rod, 20) træ.indsæt(træ.rod, 40) træ.indsæt(træ.rod, 70 ) tree.insert(tree.root, 60) tree.insert(tree.root, 80) print('Original BST:', end=' ') tree.inorder(tree.root) print() print ('
Slet en Leaf Node: 20') tree.root = tree.deleteNode(tree.root, 20) print('Ændret BST-træ efter sletning af Leaf Node:') tree.inorder(tree.root) print() print('
Slet node med enkelt underordnet: 70') tree.root = tree.deleteNode(tree.root, 70) print('Ændret BST træ efter sletning af enkelt underordnet Node:') træ. inorder(tree.root) print() print('
Slet node med begge underordnede: 50') tree.root = tree.deleteNode(tree.root, 50) print('Ændret BST-træ efter sletning af begge underordnede noder :') tree.inorder(træ.rod)>
C# 
using System; public class Node {  public int key;  public Node left, right;  public Node(int item) {  key = item;  left = right = null;  } } public class BinaryTree {  public Node root;  // A utility function to insert a new node with the given key  public Node Insert(Node node, int key) {  // If the tree is empty, return a new node  if (node == null)  return new Node(key);  // Otherwise, recur down the tree  if (key < node.key)  node.left = Insert(node.left, key);  else if (key>node.key) node.right = Indsæt(node.højre, nøgle);  // returnere (uændret) node pointer return node;  } // En hjælpefunktion til at udføre inorder-gennemgang af BST public void Inorder(Node root) { if (root != null) { Inorder(root.left);  Console.Write(root.key + ' ');  Inorder(root.right);  } } // Givet et binært søgetræ og en nøgle, sletter denne funktion nøglen og returnerer den nye rod public Node DeleteNode(Node rod, int nøgle) { // Base case if (root == null) return rod;  // Hvis nøglen, der skal slettes, er mindre end rodens nøgle, så ligger den i venstre undertræ, hvis (nøgle< root.key)  root.left = DeleteNode(root.left, key);  // If the key to be deleted is greater than the root's key, then it lies in the right subtree  else if (key>root.key) root.right = DeleteNode(root.right, nøgle);  // Hvis nøglen er den samme som root's nøgle, så er dette den node, der skal slettes ellers { // Node med kun et underordnet eller intet underordnet, hvis (root.left == null) returnerer root.right;  else if (root.right == null) returner root.left;  // Node med to børn: Hent efterfølgeren i uorden (mindst i højre undertræ) root.key = MinValue(root.right);  // Delete the inorder successor root.right = DeleteNode(root.right, root.key);  } returnere rod;  } public int MinVærdi(Noderod) { int minv = root.key;  while (root.left != null) { minv = root.left.key;  root = root.venstre;  } returner minv;  } // Driver Code public static void Main(string[] args) { BinaryTree tree = new BinaryTree();  /* Lad os oprette følgende BST 50 /  30 70 /  /  20 40 60 80 */ tree.root = tree.Insert(tree.root, 50);  træ.Indsæt(træ.rod, 30);  træ.Indsæt(træ.rod, 20);  træ.Indsæt(træ.rod, 40);  træ.Indsæt(træ.rod, 70);  træ.Indsæt(træ.rod, 60);  træ.Indsæt(træ.rod, 80);  Console.Write('Original BST: ');  træ.Inorder(træ.rod);  Console.WriteLine();  Console.WriteLine('
Slet en Leaf Node: 20');  tree.root = træ.DeleteNode(træ.rod, 20);  Console.Write('Ændret BST-træ efter sletning af Leaf Node:
');  træ.Inorder(træ.rod);  Console.WriteLine();  Console.WriteLine('
Slet node med enkelt barn: 70');  tree.root = træ.DeleteNode(træ.rod, 70);  Console.Write('Ændret BST-træ efter sletning af enkelt underordnet node:
');  træ.Inorder(træ.rod);  Console.WriteLine();  Console.WriteLine('
Slet node med begge underordnede: 50');  tree.root = træ.DeleteNode(træ.rod, 50);  Console.Write('Ændret BST-træ efter sletning af begge underordnede Node:
');  træ.Inorder(træ.rod);  }>
Javascript 
class Node {  constructor(key) {  this.key = key;  this.left = null;  this.right = null;  } } class BinaryTree {  constructor() {  this.root = null;  }  // A utility function to insert a new node with the given key  insert(node, key) {  // If the tree is empty, return a new node  if (node === null)  return new Node(key);  // Otherwise, recur down the tree  if (key < node.key)  node.left = this.insert(node.left, key);  else if (key>node.key) node.right = this.insert(node.right, key);  // returnere (uændret) node pointer return node;  } // En hjælpefunktion til at lave inorder-gennemgang af BST inorder(node) { if (node ​​!== null) { this.inorder(node.left);  console.log(node.tast + ' ');  this.inorder(node.right);  } } // Givet et binært søgetræ og en nøgle, sletter denne funktion nøglen og returnerer den nye root deleteNode(root, key) { // Base case if (root === null) return root;  // Hvis nøglen, der skal slettes, er mindre end rodens nøgle, så ligger den i venstre undertræ, hvis (nøgle< root.key)  root.left = this.deleteNode(root.left, key);  // If the key to be deleted is greater than the root's key, then it lies in the right subtree  else if (key>root.key) root.right = this.deleteNode(root.right, nøgle);  // Hvis nøglen er den samme som root's nøgle, så er dette noden, der skal slettes ellers { // Node med kun ét underordnet eller intet underordnet, hvis (root.left === null) returnerer root.right;  else if (root.right === null) returner root.left;  // Node med to børn: Hent efterfølgeren i rækkefølgen (mindst i højre undertræ) root.key = this.minValue(root.right);  // Delete the inorder successor root.right = this.deleteNode(root.right, root.key);  } returnere rod;  } minValue(node) { lad minv = node.key;  while (node.left !== null) { minv = node.left.key;  node = node.venstre;  } returner minv;  } } // Driver Code let tree = new BinaryTree(); /* Lad os oprette følgende BST 50 /  30 70 /  /  20 40 60 80 */ tree.root = tree.insert(tree.root, 50); tree.insert(tree.root, 30); træ.indsæt(træ.rod, 20); træ.indsæt(træ.rod, 40); træ.indsæt(træ.rod, 70); træ.indsæt(træ.rod, 60); træ.indsæt(træ.rod, 80); console.log('Original BST:'); træ.inorder(træ.rod); console.log('

Slet en bladknude: 20'); tree.root = tree.deleteNode(træ.rod, 20); console.log('Ændret BST-træ efter sletning af Leaf Node:'); træ.inorder(træ.rod); console.log('

Slet node med enkelt barn: 70'); tree.root = tree.deleteNode(træ.rod, 70); console.log('Ændret BST-træ efter sletning af enkelt underordnet node:'); træ.inorder(træ.rod); console.log('

Slet node med begge underordnede: 50'); tree.root = tree.deleteNode(træ.rod, 50); console.log('Ændret BST-træ efter sletning af begge underordnede Node:'); træ.inorder(træ.rod);>
Produktion 
Original BST: 20 30 40 50 60 70 Delete a Leaf Node: 20 Modified BST tree after deleting Leaf Node: 30 40 50 60 70 Delete Node with single child: 70 Modified BST tree after deleting single child No...>

Tidskompleksitet: O(h), hvor h er højden af ​​BST.
Hjælpeplads: På).

Relaterede links: