05:24:00
algorithms, binary search tree, bst, C++, Class, code, Concepts, Remove in BST, Search, search algorithms, searchalgo, Simple Programs
No comments
This is part 3 for Binary Search Tree, previous posts are Part 1 and Part 2. In this post, I'll attach the complete code also explain how Remove function for BST can be implemented.
There are a few situations possible while removing a node from the BST. There node may have no children, both children, etc. Let's have a quick view of them.
Key is element to be deleted.
- BST is empty -- then do nothing.
- Key is not found -- do nothing.
- Key is found at a node which is:
(b) Not a leaf node and has:
(i) One child N -- Previous adapts N, Remove Current
(ii) Two children -- find the Predecessor¹ P of the current node, Swap P and current node, if P is leaf then apply A else apply B(a)
 |
| Figure A |
 |
| Figure B |
¹To find a Predecessor, go to left child and then keep going right till the leaf element is reached. Predecessor is the element which is smaller to the Current node but larger than all it's left side children.
In this figure A, you can see even if replace predecessor with current node i.e. 12 with 9, the order of the tree remains intact. See figure B.
Now let's look at the code.
void remove(const T & key)
{
if (s == 0)
{
cout << "\n Empty! \n";
return;
}
else
{
if (search(key) == false)
{
cout << "\n Key not found! \n";
return;
}
//SEARCHING
Node* curr = root;
Node* prev = nullptr; //parent
while (curr != nullptr && curr->data != key)
{
prev = curr;
if (curr->data > key)
curr = curr->lchild; //key is smaller
else
curr = curr->rchild; //key is greater
}
if (curr->lchild == nullptr && curr->rchild == nullptr) //if leaf
{
delete curr;
if (curr == root)
root = nullptr;
//is it left or right child?
else if (prev->data > key)
prev->lchild = nullptr;
else if (prev->data < key)
prev->rchild = nullptr;
}
else //not leaf
{
//single child
if ((curr->lchild != nullptr && curr->rchild == nullptr) || (curr->lchild == nullptr && curr->rchild != nullptr))
{
if (prev->lchild = curr) //if curr was left child of its parent
{
if (curr->lchild != nullptr) //if curr has left child
{
prev->lchild = curr->lchild; //prev adopts left child
}
else if (curr->rchild != nullptr) //if curr has right child
{
prev->lchild = curr->rchild; //prev adopts right child
}
}
else if (prev->rchild = curr) //if curr was right child of its parent
{
if (curr->lchild != nullptr) //if curr has left child
{
prev->rchild = curr->lchild; //prev adopts left child
}
else if (curr->rchild != nullptr) //if curr has right child
{
prev->rchild = curr->rchild; //prev adopts right child
}
}
delete curr;
}
//if curr has 2 children
else if (curr->lchild != nullptr && curr->rchild != nullptr)
{
//find the predecessor
Node* curr2 = curr->lchild; //go to left of the curr
Node* prev2 = curr;
Node* prev3 = nullptr;
while (curr2 != nullptr)
{
prev3 = prev2;
prev2 = curr2;
curr2 = curr2->rchild;
}
swap(curr->data, prev2->data); //swapped
//if prev2 is a leaf
if (prev2->lchild == nullptr && prev2->rchild == nullptr)
{
if (prev2 == root)
root = nullptr;
else if (prev3->lchild == prev2)
prev3->lchild = nullptr;
else if (prev3->rchild == prev2)
prev3->rchild = nullptr;
delete prev2;
}
//if prev2 has one child
else if ((prev2->lchild != nullptr && prev2->rchild == nullptr) || (prev2->lchild == nullptr && prev2->rchild != nullptr))
{
if (prev3->lchild = prev2) //if prev2 was left child of its parent
{
if (prev2->lchild != nullptr) //if curr has left child
{
prev3->lchild = prev2->lchild; //prev adopts left child
}
else if (prev2->rchild != nullptr) //if curr has right child
{
prev3->lchild = prev2->rchild; //prev adopts right child
}
}
else if (prev3->rchild = prev2) //if prev2 was right child of its parent
{
if (prev2->lchild != nullptr) //if curr has left child
{
prev3->rchild = prev2->lchild; //prev adopts left child
}
else if (prev2->rchild != nullptr) //if prev2 has right child
{
prev3->rchild = prev2->rchild; //prev adopts right child
}
}
delete curr;
}
}
}
s--; //reducing size
}
}
This is all so far about BST.
To download code, Click Here!
In my code, I have other utility functions too as per my requirement which I have not discussed here. Keep them or remove them, your choice! :P
Thanks for reading. If any question, Comment below! :)
0 comments:
Post a Comment