Advertisement
Alhiris

Tree node deletion - implementation

Oct 22nd, 2019
210
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.62 KB | None | 0 0
  1. class Node{
  2.     public:
  3.         Node* left;
  4.         Node* right;
  5.         Node* parent;
  6.  
  7.         static Node* removeNodes(Node* node,int value){
  8.             removeNodes(node->left,value);
  9.             removeNodes(node->right,value);
  10.             if(node->value==value){
  11.                 Node* aux;
  12.                 //First case, right side of the parent
  13.                 //1.Inserting left continuation of my node to the left side of parrent
  14.                 //2.Right side was my node so just mapping it to the parent's right
  15.                 if(node->parent->right==node){
  16.                     if(node->left != nullptr){
  17.                         aux=node;
  18.                         while(aux->left!=nullptr)
  19.                             aux=aux->left;
  20.                         //last left node mapped to first left child of parent
  21.                         aux->left=node->parent->left;
  22.                         node->parent->left->parent=aux;
  23.                         //first left side node mapped to parent
  24.                         node->left->parent=node->parent;
  25.                         node->parent->left=aux;
  26.                     }
  27.                     //Managing right side of the deletion
  28.                     node->parent->right=node->right;
  29.                     node->right->parent=node->parent;
  30.                 }
  31.                 //Second case, left side of parent(same process)
  32.                 //but left and right are inversed
  33.                 if(node->parent->left==node){
  34.                     if(node->right!=nullptr){
  35.                         aux=node;
  36.                         while(aux->right!=nullptr)
  37.                             aux=aux->right;
  38.                         aux->right=node->parent->right;
  39.                         node->parent->right->parent=aux;
  40.                         node->right->parent=node->parent;
  41.                         node->parent->left=aux;
  42.                     }
  43.                     node->parent->left=node->left;
  44.                     node->left->parent=node->parent;
  45.                 }
  46.                 //Case of it being root
  47.                 //Decided the best is to just take a leaf and
  48.                 //Set it as root
  49.                 else{
  50.                     aux=node;
  51.                     while(aux->right!=nullptr)
  52.                         aux=aux->right;
  53.                     aux->left=node->left;
  54.                     aux->right=node->right;
  55.                     aux->parent=nullptr;
  56.                     node=aux;
  57.                 }
  58.             }
  59.             if(node->parent==nullptr)
  60.                 return node;
  61.             else return nullptr;
  62.         }
  63.  
  64.     private:
  65.         int value;
  66. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement