Created
September 11, 2017 15:58
-
-
Save scriptonian/3bf1881b26ff1a2ac65d76535aadf4c7 to your computer and use it in GitHub Desktop.
Javascript Binary Search Tree - Remove
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
BinarySearchTree.prototype = { | |
//other code here | |
remove: function(key) { | |
/* | |
First we find out if the node exists. If it doesn't exist, we return null and exit the function | |
*/ | |
if(bst.root === null) { | |
return false; | |
} | |
//find the node in question | |
var currentNode = this.find(bst.root, key); | |
//find nodes parent. | |
var nodeParent = this.findNodeParent(key); | |
//case 1: remove a node that does not have a right child. | |
if(currentNode.right === null) { | |
if(nodeParent === null) { | |
this.root = currentNode.left; | |
} else { | |
//if parent is greater than current value, make teh current left child a child of parent | |
if(currentNode.keyValue < nodeParent.keyValue) { | |
nodeParent.left = currentNode.left; | |
//if parent is less than current value, make the left child a right child of parent. | |
} else if(currentNode.keyValue > nodeParent.keyValue) { | |
nodeParent.right = currentNode.left; | |
} | |
} | |
//case 2. if the node we are removing has a right child which doesnt have a left child | |
} else if (currentNode.right.left === null) { | |
currentNode.right.left = currentNode.left; | |
if(nodeParent === null) { | |
this.root = currentNode.right; | |
} else { | |
//if current value is less than parent, make right child of the left the parent | |
if(currentNode.keyValue < nodeParent.keyValue) { | |
nodeParent.left = currentNode.right; | |
//if current value is greater than parent, make current right child a right child of the parent | |
} else if(currentNode.keyValue > nodeParent.keyValue) { | |
nodeParent.right = currentNode.right; | |
} | |
} | |
//case 3 if the node we are removing has a right child that has a left child. | |
//promote the left child to deleted spot | |
} else { | |
//find the rights left most child | |
var leftmost = currentNode.right.left; | |
var leftmostParent = currentNode.right; | |
while(leftmost.left !== null) { | |
leftmostParent = leftmost; | |
leftmost = leftmost.left; | |
} | |
//parents left subtree becomes the leftmost's right subtree | |
leftmostParent.left = leftmost.right; | |
//assign leftmost's left and right to the current left and right children | |
leftmost.left = currentNode.left; | |
leftmost.right = currentNode.right; | |
if(nodeParent === null) { | |
this.root = leftmost; | |
} else { | |
if(currentNode.keyValue < nodeParent.keyValue) { | |
nodeParent.left = leftmost; | |
} else if(currentNode.keyValue > nodeParent.keyValue) { | |
nodeParent.right = leftmost; | |
} | |
} | |
} | |
//decrease the count | |
this.count--; | |
return true; | |
} | |
//other code here | |
} | |
var bst = new BinarySearchTree(); | |
//Remove Test Cases | |
//case 1 | |
bst.insert(4); | |
bst.insert(2); | |
bst.insert(8); | |
bst.insert(1); | |
bst.insert(3); | |
bst.insert(6); | |
bst.insert(7); | |
bst.insert(5); | |
//case 2 | |
/* | |
bst.insert(4); | |
bst.insert(2); | |
bst.insert(6); | |
bst.insert(1); | |
bst.insert(3); | |
bst.insert(5); | |
bst.insert(7); | |
bst.insert(8); | |
*/ | |
//case 3 | |
/* | |
bst.insert(4); | |
bst.insert(2); | |
bst.insert(6); | |
bst.insert(1); | |
bst.insert(3); | |
bst.insert(5); | |
bst.insert(8); | |
bst.insert(7); | |
*/ |
Thank you, my friend, this website is a treasure! :D
Have a great day too!
Big smile on my face! Enjoy it. And please do share with me any improvements i can make as you explore! I am planning on doing a javascript designs pattern series as well (whenever i can find time). Take care and speak sometime in the future.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Welcome Artem :-) The full blog post is found here
https://www.scriptonitejs.com/javascript-binary-search-trees/
Have a great day.