2020-05-03 09:05:12 +02:00
|
|
|
/* Binary Search Tree!!
|
2017-08-05 23:53:36 +05:30
|
|
|
*
|
|
|
|
|
* Nodes that will go on the Binary Tree.
|
|
|
|
|
* They consist of the data in them, the node to the left, the node
|
|
|
|
|
* to the right, and the parent from which they came from.
|
|
|
|
|
*
|
|
|
|
|
* A binary tree is a data structure in which an element
|
|
|
|
|
* has two successors(children). The left child is usually
|
|
|
|
|
* smaller than the parent, and the right child is usually
|
|
|
|
|
* bigger.
|
|
|
|
|
*/
|
|
|
|
|
|
2018-03-30 21:15:05 +02:00
|
|
|
// class Node
|
2021-09-27 11:02:10 +05:30
|
|
|
const Node = (function Node () {
|
2018-03-30 21:15:05 +02:00
|
|
|
// Node in the tree
|
2020-05-03 09:05:12 +02:00
|
|
|
function Node (val) {
|
|
|
|
|
this.value = val
|
|
|
|
|
this.left = null
|
|
|
|
|
this.right = null
|
2017-08-05 23:53:36 +05:30
|
|
|
}
|
|
|
|
|
|
2018-03-30 21:15:05 +02:00
|
|
|
// Search the tree for a value
|
|
|
|
|
Node.prototype.search = function (val) {
|
2020-05-03 21:26:52 -03:00
|
|
|
if (this.value === val) {
|
2020-05-03 09:05:12 +02:00
|
|
|
return this
|
2021-09-27 11:02:10 +05:30
|
|
|
} else if (val < this.value && this.left !== null) {
|
2020-05-03 09:05:12 +02:00
|
|
|
return this.left.search(val)
|
2021-09-27 11:02:10 +05:30
|
|
|
} else if (val > this.value && this.right !== null) {
|
2020-05-03 09:05:12 +02:00
|
|
|
return this.right.search(val)
|
2018-03-30 21:15:05 +02:00
|
|
|
}
|
2020-05-03 09:05:12 +02:00
|
|
|
return null
|
|
|
|
|
}
|
2017-08-05 23:53:36 +05:30
|
|
|
|
2018-03-30 21:15:05 +02:00
|
|
|
// Visit a node
|
2021-10-10 16:11:06 +02:00
|
|
|
Node.prototype.visit = function (output = value => console.log(value)) {
|
2018-03-30 21:15:05 +02:00
|
|
|
// Recursively go left
|
2021-09-27 11:02:10 +05:30
|
|
|
if (this.left !== null) {
|
2020-05-03 09:05:12 +02:00
|
|
|
this.left.visit()
|
2017-08-05 23:53:36 +05:30
|
|
|
}
|
2018-03-30 21:15:05 +02:00
|
|
|
// Print out value
|
2021-10-10 16:11:06 +02:00
|
|
|
output(this.value)
|
2018-03-30 21:15:05 +02:00
|
|
|
// Recursively go right
|
2021-09-27 11:02:10 +05:30
|
|
|
if (this.right !== null) {
|
2020-05-03 09:05:12 +02:00
|
|
|
this.right.visit()
|
2017-08-05 23:53:36 +05:30
|
|
|
}
|
2020-05-03 09:05:12 +02:00
|
|
|
}
|
2017-08-05 23:53:36 +05:30
|
|
|
|
2018-03-30 21:15:05 +02:00
|
|
|
// Add a node
|
|
|
|
|
Node.prototype.addNode = function (n) {
|
|
|
|
|
if (n.value < this.value) {
|
2021-09-27 11:02:10 +05:30
|
|
|
if (this.left === null) {
|
2020-05-03 09:05:12 +02:00
|
|
|
this.left = n
|
2018-03-30 21:15:05 +02:00
|
|
|
} else {
|
|
|
|
|
this.left.addNode(n)
|
|
|
|
|
}
|
|
|
|
|
} else if (n.value > this.value) {
|
2021-09-27 11:02:10 +05:30
|
|
|
if (this.right === null) {
|
2020-05-03 09:05:12 +02:00
|
|
|
this.right = n
|
2018-03-30 21:15:05 +02:00
|
|
|
} else {
|
2020-05-03 09:05:12 +02:00
|
|
|
this.right.addNode(n)
|
2018-03-30 21:15:05 +02:00
|
|
|
}
|
|
|
|
|
}
|
2020-05-03 09:05:12 +02:00
|
|
|
}
|
2017-08-05 23:53:36 +05:30
|
|
|
|
2021-09-27 11:02:10 +05:30
|
|
|
// remove a node
|
|
|
|
|
Node.prototype.removeNode = function (val) {
|
|
|
|
|
if (val === this.value) {
|
|
|
|
|
if (!this.left && !this.right) {
|
|
|
|
|
return null
|
|
|
|
|
} else {
|
|
|
|
|
if (this.left) {
|
|
|
|
|
const leftMax = maxVal(this.left)
|
|
|
|
|
this.value = leftMax
|
|
|
|
|
this.left = this.left.removeNode(leftMax)
|
|
|
|
|
} else {
|
|
|
|
|
const rightMin = minVal(this.right)
|
|
|
|
|
this.value = rightMin
|
|
|
|
|
this.right = this.right.removeNode(rightMin)
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
} else if (val < this.value) {
|
|
|
|
|
this.left = this.left && this.left.removeNode(val)
|
|
|
|
|
} else if (val > this.value) {
|
|
|
|
|
this.right = this.right && this.right.removeNode(val)
|
|
|
|
|
}
|
|
|
|
|
return this
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// find maximum value in the tree
|
|
|
|
|
const maxVal = function (node) {
|
|
|
|
|
if (!node.right) {
|
|
|
|
|
return node.value
|
|
|
|
|
}
|
|
|
|
|
return maxVal(node.right)
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// find minimum value in the tree
|
|
|
|
|
const minVal = function (node) {
|
|
|
|
|
if (!node.left) {
|
|
|
|
|
return node.value
|
|
|
|
|
}
|
|
|
|
|
return minVal(node.left)
|
|
|
|
|
}
|
2018-03-30 21:15:05 +02:00
|
|
|
// returns the constructor
|
2020-05-03 09:05:12 +02:00
|
|
|
return Node
|
|
|
|
|
}())
|
2017-08-05 23:53:36 +05:30
|
|
|
|
2018-03-30 21:15:05 +02:00
|
|
|
// class Tree
|
2021-05-21 11:16:11 +05:30
|
|
|
const Tree = (function () {
|
2020-05-03 09:05:12 +02:00
|
|
|
function Tree () {
|
2018-03-30 21:15:05 +02:00
|
|
|
// Just store the root
|
2020-05-03 09:05:12 +02:00
|
|
|
this.root = null
|
2018-03-30 21:15:05 +02:00
|
|
|
};
|
|
|
|
|
|
|
|
|
|
// Inorder traversal
|
|
|
|
|
Tree.prototype.traverse = function () {
|
2021-09-27 11:02:10 +05:30
|
|
|
if (!this.root) {
|
2021-10-10 16:11:06 +02:00
|
|
|
// No nodes are there in the tree till now
|
2021-09-27 11:02:10 +05:30
|
|
|
return
|
|
|
|
|
}
|
2020-05-03 09:05:12 +02:00
|
|
|
this.root.visit()
|
|
|
|
|
}
|
2018-03-30 21:15:05 +02:00
|
|
|
|
|
|
|
|
// Start by searching the root
|
|
|
|
|
Tree.prototype.search = function (val) {
|
2020-05-03 09:05:12 +02:00
|
|
|
const found = this.root.search(val)
|
2021-10-10 16:11:06 +02:00
|
|
|
if (found !== null) {
|
|
|
|
|
return found.value
|
2018-03-30 21:15:05 +02:00
|
|
|
}
|
2021-10-10 16:11:06 +02:00
|
|
|
// not found
|
|
|
|
|
return null
|
2020-05-03 09:05:12 +02:00
|
|
|
}
|
2018-03-30 21:15:05 +02:00
|
|
|
|
|
|
|
|
// Add a new value to the tree
|
|
|
|
|
Tree.prototype.addValue = function (val) {
|
2020-05-03 09:05:12 +02:00
|
|
|
const n = new Node(val)
|
2021-09-27 11:02:10 +05:30
|
|
|
if (this.root === null) {
|
2020-05-03 09:05:12 +02:00
|
|
|
this.root = n
|
2018-03-30 21:15:05 +02:00
|
|
|
} else {
|
2020-05-03 09:05:12 +02:00
|
|
|
this.root.addNode(n)
|
2018-03-30 21:15:05 +02:00
|
|
|
}
|
2020-05-03 09:05:12 +02:00
|
|
|
}
|
2018-03-30 21:15:05 +02:00
|
|
|
|
2021-09-27 11:02:10 +05:30
|
|
|
// remove a value from the tree
|
|
|
|
|
Tree.prototype.removeValue = function (val) {
|
|
|
|
|
// remove something if root exists
|
|
|
|
|
this.root = this.root && this.root.removeNode(val)
|
|
|
|
|
}
|
|
|
|
|
|
2018-03-30 21:15:05 +02:00
|
|
|
// returns the constructor
|
2020-05-03 09:05:12 +02:00
|
|
|
return Tree
|
|
|
|
|
}())
|
2017-08-05 23:53:36 +05:30
|
|
|
|
2021-10-10 16:11:06 +02:00
|
|
|
export { Tree }
|
