logo

TechCodeview

Sletting i binært søketre (BST)

Gitt en BST , er oppgaven å slette en node i denne BST , som kan deles inn i 3 scenarier:

Tilfelle 1. Slett en bladnode i BST

d1

Sletting i BST




Tilfelle 2. Slett en node med enkeltbarn i BST

Å slette en enkelt barnenode er også enkelt i BST. Kopier barnet til noden og slett noden .




fil

Sletting i BST


Tilfelle 3. Slett en node med begge barn i BST

Å slette en node med begge barna er ikke så enkelt. Her må vi slette noden er slik at det resulterende treet følger egenskapene til en BST.



mylivecricket inn for live cricket

Trikset er å finne nodens etterfølger i rekkefølge. Kopier innholdet av inorder-etterfølgeren til noden, og slett inorder-etterfølgeren.

Merk: Inorder forgjenger kan også brukes.


d3

Sletting i binært tre


hiba bukhari

Merk: Inorder-etterfølger er kun nødvendig når det rette barnet ikke er tomt. I dette spesielle tilfellet kan den inordnede etterfølgeren oppnås ved å finne minimumsverdien i høyre underordnet av noden.

Anbefalt praksis Slett en node fra BST Prøv det!

Implementering av sletteoperasjon 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økkel = element;  temp->venstre = temp->høyre = NULL;  retur temp; } // En verktøyfunksjon for å gjøre inorder-gjennomgang av BST void inorder(Node* root) { if (root != NULL) { inorder(root->venstre);  printf('%d ', root->nøkkel);  inorder(root->høyre);  } } /* En verktøyfunksjon for å sette inn en ny node med gitt nøkkel i * BST */ Node* insert(Node* node, int key) { /* Hvis treet er tomt, returner en ny node */ if (node ​​= = NULL) returner nyNode(nøkkel);  /* Ellers går du tilbake i treet */ if (tast< node->key) node->venstre = insert(node->venstre, nøkkel);  else node->right = insert(node->right, key);  /* returner (uendret) nodepekeren */ return node; } /* Gitt et binært søketre og en nøkkel, sletter denne funksjonen nøkkelen og returnerer den nye roten */ Node* deleteNode(Node* rot, int k) { // Base case if (root == NULL) return root;  // Hvis nøkkelen som skal slettes er mindre enn rotens nøkkel, // ligger den i det venstre undertreet hvis (k< root->key) { root->venstre = deleteNode(root->venstre, k);  returnere rot;  } // Hvis nøkkelen som skal slettes er større enn rotens nøkkel, // så ligger den i høyre undertreet ellers hvis (k> root->key) { root->right = deleteNode(root->right k);  returnere rot;  } // Hvis nøkkelen er den samme som rotnøkkelen, så er dette noden som skal slettes // Node med bare ett barn eller ingen underordnet hvis (root->venstre == NULL) { Node* temp = root-> Ikke sant;  slett rot;  retur temp;  } else if (rot->høyre == NULL) { Node* temp = rot->venstre;  slett rot;  retur temp;  } // Node med to barn: Få etterfølgeren i rekkefølgen (minste // i høyre undertre) Node* succParent = rot;  Node* succ = rot->høyre;  while (succ->venstre != NULL) { succParent = succ;  succ = succ->venstre;  } // Kopier innholdet til etterfølgeren til denne noden root->key = succ->key;  // Slett etterfølgeren i rekkefølgen hvis (succParent->venstre == succ) succParent->venstre = succ->høyre;  else succParent->right = succ->right;    slette succ;  returnere rot; } // Driverkode int main() { /* La oss lage følgende BST 50 /  30 70 /  /  20 40 60 80 */ Node* root = NULL;  root = insert(root, 50);  root = insert(root, 30);  root = insert(root, 20);  root = insert(root, 40);  root = insert(root, 70);  root = insert(root, 60);  root = insert(root, 80);  printf('Original BST: ');  inorder(root);    printf('

Slett en bladnode: 20
');  root = deleteNode(root, 20);  printf('Endret BST-tre etter sletting av Leaf Node:
');  inorder(root);  printf('

Slett node med enkelt barn: 70
');  root = deleteNode(root, 70);  printf('Endret BST-tre etter sletting av enkeltbarnsnode:
');  inorder(root);  printf('

Slett node med begge underordnede: 50
');  root = deleteNode(root, 50);  printf('Endret BST-tre etter sletting av begge underordnede Node:
');  inorder(root);  returner 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økkel = element;  temp->venstre = temp->høyre = NULL;  retur temp; } // En verktøyfunksjon for å gjøre inorder-gjennomgang av BST void inorder(struct Node* root) { if (root != NULL) { inorder(root->left);  printf('%d ', root->nøkkel);  inorder(root->høyre);  } } /* En verktøyfunksjon for å sette inn en ny node med gitt nøkkel i BST */ struct Node* insert(struct Node* node, int key) { /* Hvis treet er tomt, returner en ny node */ if (node == NULL) returner nyNode(nøkkel);  /* Ellers går du tilbake i treet */ if (tast< node->key) node->venstre = insert(node->venstre, nøkkel);  else node->right = insert(node->right, key);  /* returner (uendret) nodepekeren */ return node; } /* Gitt et binært søketre og en nøkkel, sletter denne funksjonen nøkkelen og returnerer den nye roten */ struct Node* deleteNode(struct Node* rot, int k) { // Base case if (root == NULL) return rot;  // Hvis nøkkelen som skal slettes er mindre enn rotens nøkkel, ligger den i det venstre undertreet hvis (k< root->key) { root->venstre = deleteNode(root->venstre, k);  returnere rot;  } // Hvis nøkkelen som skal slettes er større enn rotens nøkkel, så ligger den i høyre undertreet ellers hvis (k> root->key) { root->right = deleteNode(root->right, k );  returnere rot;  } // Hvis nøkkelen er den samme som rotnøkkelen, så er dette noden som skal slettes // Node med bare ett barn eller ingen underordnet hvis (root->venstre == NULL) { struct Node* temp = root-> høyre;  gratis(root);  retur temp;  } else if (rot->høyre == NULL) { struct Node* temp = rot->venstre;  gratis(root);  retur temp;  } // Node med to barn: Hent etterfølgeren i rekkefølgen (minst i høyre undertre) struct Node* succParent = rot;  struct Node* succ = rot->høyre;  while (succ->venstre != NULL) { succParent = succ;  succ = succ->venstre;  } // Kopier innholdet til etterfølgeren til denne noden root->key = succ->key;  // Slett etterfølgeren i rekkefølgen hvis (succParent->venstre == succ) succParent->venstre = succ->høyre;  else succParent->right = succ->right;  gratis(succ);  returnere rot; } // Driverkode int main() { /* La oss lage følgende BST 50 /  30 70 /  /  20 40 60 80 */ struct Node* root = NULL;  root = insert(root, 50);  insert(root, 30);  insert(root, 20);  insert(root, 40);  insert(root, 70);  insert(root, 60);  insert(root, 80);  printf('Original BST: ');  inorder(root);    printf('

Slett en bladnode: 20
');  root = deleteNode(root, 20);  printf('Endret BST-tre etter sletting av Leaf Node:
');  inorder(root);  printf('

Slett node med enkelt barn: 70
');  root = deleteNode(root, 70);  printf('Endret BST-tre etter sletting av enkeltbarnsnode:
');  inorder(root);  printf('

Slett node med begge underordnede: 50
');  root = deleteNode(root, 50);  printf('Endret BST-tre etter sletting av begge underordnede Node:
');  inorder(root);  returner 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);  } // returner (uendret) nodepeker returnode;  } // En verktøyfunksjon for å gjøre inorder-gjennomgang av BST void inorder(Node root) { if (root != null) { inorder(root.left);  System.out.print(root.key + ' ');  inorder(root.right);  } } // Gitt et binært søketre og en nøkkel, sletter denne funksjonen nøkkelen og returnerer den nye roten Node deleteNode(Node rot, int nøkkel) { // Grunntall if (root == null) { return root;  } // Hvis nøkkelen som skal slettes er mindre enn rotens nøkkel, ligger den i det venstre undertreet hvis (nøkkel< 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økkel);  } // Hvis nøkkelen er den samme som rotens nøkkel, så er dette noden som skal slettes else { // Node med bare ett barn eller ingen underordnet hvis (root.left == null) { return root.right;  } else if (root.right == null) { return root.left;  } // Node med to barn: Hent etterfølgeren i rekkefølgen (minst i høyre undertre) root.key = minValue(root.right);  // Delete the inorder successor root.right = deleteNode(root.right, root.key);  } returner rot;  } int minValue(Noderot) { int minv = rot.nøkkel;  while (root.left != null) { minv = root.left.key;  rot = rot.venstre;  } returner minv;  } // Driver Code public static void main(String[] args) { BinaryTree tree = new BinaryTree();  /* La oss lage følgende BST 50 /  30 70 /  /  20 40 60 80 */ tree.root = tree.insert(tree.root, 50);  tree.insert(tre.root, 30);  tree.insert(tre.root, 20);  tree.insert(tre.root, 40);  tree.insert(tre.root, 70);  tree.insert(tre.root, 60);  tree.insert(tre.root, 80);  System.out.print('Original BST: ');  tree.inorder(tre.rot);  System.out.println();  System.out.println('
Slett en bladnode: 20');  tree.root = tree.deleteNode(tree.root, 20);  System.out.print('Endret BST-tre etter sletting av Leaf Node:
');  tree.inorder(tre.rot);  System.out.println();  System.out.println('
Slett node med enkelt barn: 70');  tree.root = tree.deleteNode(tre.rot, 70);  System.out.print('Endret BST-tre etter sletting av enkeltbarnsnode:
');  tree.inorder(tre.rot);  System.out.println();  System.out.println('
Slett node med begge underordnede: 50');  tree.root = tree.deleteNode(tre.rot, 50);  System.out.print('Endret BST-tre etter sletting av begge underordnede Node:
');  tree.inorder(tre.rot);  } }>
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 (uendret) nodepeker returnode # En verktøyfunksjon for å gjøre inordre-gjennomgang av BST def inorder(self, root): if root: self .inorder(root.left) print(root.key, end=' ') self.inorder(root.right) # Gitt et binært søketre og en nøkkel, sletter denne funksjonen nøkkelen og returnerer den nye roten def deleteNode (selv, rot, nøkkel): # Grunntall hvis root er Ingen: returner rot # Hvis nøkkelen som skal slettes er mindre enn rotens nøkkel, ligger den i venstre undertre hvis nøkkel< 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, nøkkel) # Hvis nøkkelen er den samme som root-nøkkelen, så er dette noden som skal slettes ellers: # Node med bare ett barn eller ingen barn hvis root.left er Ingen: returner root.right elif root.right er Ingen: returner root.left # Node med to barn: Hent etterfølgeren i rekkefølgen (minst i høyre undertre) root.key = self.minValue(root.right) # Slett etterfø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 __name__ == '__main__': tre = BinaryTree() # La oss lage følgende BST # 50 # /  # 30 70 # /  /  # 20 40 60 80 tree.root = tree.insert(tre.rot, 50) tree.insert(tre.rot, 30) tree.insert(tre.rot, 20) tree.insert(tre.rot, 40) tree.insert(tre.rot, 70 ) tree.insert(tree.root, 60) tree.insert(tree.root, 80) print('Original BST:', end=' ') tree.inorder(tree.root) print() print ('
Slett en bladnode: 20') tree.root = tree.deleteNode(tree.root, 20) print('Endret BST-tre etter sletting av bladnode:') tree.inorder(tree.root) print() print('
Slett node med enkeltbarn: 70') tree.root = tree.deleteNode(tree.root, 70) print('Endret BST-tre etter sletting av enkeltbarnsnode:') tre. inorder(tree.root) print() print('
Slett node med begge underordnede: 50') tree.root = tree.deleteNode(tree.root, 50) print('Endret BST-tre etter sletting av begge underordnede nodene :') tree.inorder(tre.rot)>
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 = Sett inn(node.høyre, nøkkel);  // returner (uendret) nodepeker returnode;  } // En verktøyfunksjon for å gjøre inorder-gjennomgang av BST public void Inorder(Node root) { if (root != null) { Inorder(root.left);  Console.Write(root.key + ' ');  Inorder(root.right);  } } // Gitt et binært søketre og en nøkkel, sletter denne funksjonen nøkkelen og returnerer den nye roten public Node DeleteNode(Node root, int key) { // Base case if (root == null) return root;  // Hvis nøkkelen som skal slettes er mindre enn rotens nøkkel, ligger den i det venstre undertreet hvis (nøkkel< 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økkel);  // Hvis nøkkelen er den samme som rotnøkkelen, så er dette noden som skal slettes else { // Node med bare ett barn eller ingen underordnet hvis (root.left == null) returnerer root.right;  else if (root.right == null) returner root.left;  // Node med to barn: Hent etterfølgeren i rekkefølgen (minst i høyre undertre) root.key = MinValue(root.right);  // Delete the inorder successor root.right = DeleteNode(root.right, root.key);  } returner rot;  } public int MinVerdi(Noderot) { int minv = rot.nøkkel;  while (root.left != null) { minv = root.left.key;  rot = rot.venstre;  } returner minv;  } // Driver Code public static void Main(string[] args) { BinaryTree tree = new BinaryTree();  /* La oss lage følgende BST 50 /  30 70 /  /  20 40 60 80 */ tree.root = tree.Insert(tree.root, 50);  tre.Sett inn(tre.rot, 30);  tre.Sett inn(tre.rot, 20);  tre.Sett inn(tre.rot, 40);  tre.Sett inn(tre.rot, 70);  tre.Sett inn(tre.rot, 60);  tre.Sett inn(tre.rot, 80);  Console.Write('Original BST: ');  tre.Inorder(tre.rot);  Console.WriteLine();  Console.WriteLine('
Slett en bladnode: 20');  tree.root = tree.DeleteNode(tree.root, 20);  Console.Write('Modifisert BST-tre etter sletting av Leaf Node:
');  tre.Inorder(tre.rot);  Console.WriteLine();  Console.WriteLine('
Slett node med enkelt barn: 70');  tree.root = tree.DeleteNode(tree.root, 70);  Console.Write('Endret BST-tre etter sletting av enkeltbarnsnode:
');  tre.Inorder(tre.rot);  Console.WriteLine();  Console.WriteLine('
Slett node med begge barn: 50');  tree.root = tree.DeleteNode(tree.root, 50);  Console.Write('Modifisert BST-tre etter sletting av begge underordnede Node:
');  tre.Inorder(tre.rot);  }>
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);  // returner (uendret) nodepeker returnode;  } // En verktøyfunksjon for å gjøre inorder-gjennomgang av BST inorder(node) { if (node ​​!== null) { this.inorder(node.left);  console.log(node.tast + ' ');  this.inorder(node.right);  } } // Gitt et binært søketre og en nøkkel, sletter denne funksjonen nøkkelen og returnerer den nye roten deleteNode(root, key) { // Base case if (root === null) return root;  // Hvis nøkkelen som skal slettes er mindre enn rotens nøkkel, ligger den i det venstre undertreet hvis (nøkkel< 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økkel);  // Hvis nøkkelen er den samme som rotnøkkelen, så er dette noden som skal slettes else { // Node med bare ett barn eller ingen underordnet hvis (root.left === null) returnerer root.right;  else if (root.right === null) returner root.left;  // Node med to barn: Hent etterfølgeren i rekkefølgen (minst i høyre undertre) root.key = this.minValue(root.right);  // Slett inorder-etterfølgeren root.right = this.deleteNode(root.right, root.key);  } returner rot;  } minVerdi(node) { la minv = node.nøkkel;  while (node.left !== null) { minv = node.left.key;  node = node.venstre;  } returner minv;  } } // Driver Code let tree = new BinaryTree(); /* La oss lage følgende BST 50 /  30 70 /  /  20 40 60 80 */ tree.root = tree.insert(tree.root, 50); tree.insert(tre.root, 30); tree.insert(tre.root, 20); tree.insert(tre.root, 40); tree.insert(tre.root, 70); tree.insert(tre.root, 60); tree.insert(tre.root, 80); console.log('Original BST:'); tree.inorder(tre.rot); console.log('

Slett en bladnode: 20'); tree.root = tree.deleteNode(tree.root, 20); console.log('Modifisert BST-tre etter sletting av Leaf Node:'); tree.inorder(tre.rot); console.log('

Slett node med enkelt barn: 70'); tree.root = tree.deleteNode(tre.rot, 70); console.log('Endret BST-tre etter sletting av enkeltbarnsnode:'); tree.inorder(tre.rot); console.log('

Slett node med begge barn: 50'); tree.root = tree.deleteNode(tre.rot, 50); console.log('Endret BST-tre etter sletting av begge underordnede Node:'); tree.inorder(tre.rot);>
Produksjon 
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øyden til BST.
Hjelpeplass: På).

Relaterte linker: