preface
In the front-end work, binary search tree is not very common, although not as fast row, bubble, de-weight, binary, hill and other algorithms common, but its role, in some specific scenarios, is very important.
There are a lot of es6 usage scenarios out there, so WHERE I'm going to use ES6, I'm going to use IT.Copy the codeThe body of the
This is what I found on the Internet, just to show you what a tree looks like.
Here is a brief introduction to the terminology of binary search trees, which will be covered in subsequent discussions. The topmost node of a tree is called the root node. If two nodes are connected below a node, the node is called the parent, and the nodes below it are called the children. A node has at most 0-2 child nodes. A node without any children is called a leaf node.
What is a binary search tree
Binary search tree is a kind of nonlinear data structure that is typically used to store data with hierarchy, for example, we have to do a visual file system, similar to the cloud disk web version, it has to distinguish between different folders, each folder has different contents below, they each folder, there is no any relationship, only relationship, The same level of folders, there is a parent folder.
And the non-linear data structure is the opposite of linear data structure, linear data structure is actually more common at ordinary times, the front end of the commonly used linear data structure is: stack, queue, array.
Why use binary search trees
Binary search trees are chosen over basic data structures because they are very fast to look up in and to add or remove elements to a binary search tree.
Binary search tree search features
- Each node of a binary search tree cannot have more than two children.
- The left node of each node is always smaller than it is, and the right node is always smaller than it is;
The realization of binary search tree
The functions of binary search tree include adding nodes, deleting nodes, querying nodes (maximum value, minimum value, a specified value);
The traversal methods of binary search tree include middle-order traversal, pre-order traversal and post-order traversal.
Create a binary search tree node and its operation class
Create a node
When creating a node, remember that binary search tree nodes are not allowed to have more than two children:
class Node {
constructor({data = null, left = null, right = null{})this._data = data
this._left = left
this._right = right
}
show(){
return this._data
}
}
Copy the codeCreate a node, null by default, with left and right nodes. Add a show method to display the current node’s data.
Create a class that operates on a node
Now that we have a node and know what properties it has, we create a class that operates on these nodes:
class BinarySearchTree {
constructor() {this._root = null}}Copy the codeHere we create a root node, which is the root at the bottom of the binary search tree. Next, we add a method to add nodes.
Add a node
class BinarySearchTree {
constructor() {
this._root = null
}
insert(data) {
let node = new Node({
data: data
})
if (this._root == null) {
this._root = node
}
else {
let current, parent
current = this._root
while (true) {
parent = current
if (data < current.data) {
current = current.left
if (current == null) {
parent.left = node
break}}else {
current = current.right
if (current == null) {
parent.right = node
break
}
}
}
}
}
}
Copy the codeHere, we add an insert method that adds nodes;
Check whether the root node is null. If the root node is null, the root node is used as the root node.
If there is a root node, then the value of the comparison target, initialize the root node as the comparison target, check whether the root node is larger than the root node, or smaller than the root node;
If it is smaller than the left node of the root node, then the left node of the root node is used for comparison next time. Of course, if the left node is empty, it is ok to use the left node of the current node to add as the left node.
If greater than, and less than and vice versa;
Then we now start adding values and testing some methods:
let bst = new BinarySearchTree()
bst.insert(2)
bst.insert(1)
bst.insert(3)
Copy the codeWe add a root node, which is 2, and then we add two leaves of nodes 1 and 3, 1 to the left of root 2 and 3 to the right of root 2, and then we add a method to remove the node.
Remove nodes
class BinarySearchTree {
constructor() {
this._root = null
}
remove(data) {
this._root = this._removeNode(this._root, data)
}
_removeNode(node, data) {
if (node == null) {
return null
}
if (data == node._data) {
if (node._left == null && node._right == null) {
return null
}
if (node._left == null) {
return node._right
}
if (node._right == null) {
return node._left
}
var tempNode = this._getSmallest(node._right)
node._data = tempNode._data
node._right = this._removeNode(node._right, tempNode._data)
return node
} else if (data < node._data) {
node._left = this._removeNode(node._left, data)
return node
} else {
node._right = this._removeNode(node._right, data)
return node
}
}
_getSmallest(node) {
if (node._left == null) {
return node
} else {
return this._getSmallest(node._left)
}
}
}
Copy the codeThis is the method used to delete a node.
This method returns a new node. If node is null the first time it is called, the binary search tree is empty.
If the value to be deleted is the value of the current node, then check whether there are values on the left and right nodes of the node. If there are no values, directly return null, because the current node does not need to do child node processing, directly delete the current node.
If the left node is null, the current node is replaced directly by the right node of the current node.
If the right node is null, the current node is replaced by the left node of the current node.
If, the current node to be deleted, left and right nodes exist, then go through the node to the right of the node to be deleted, if the right node does not exist its left node, then directly return to the right node, if there is, keep recursion, find the lowest left node returns the result;
Here is a brief summary, is to find the deleted node right node tree in the minimum value, to replace the current deleted node positionCopy the codeIf the current value to be deleted is smaller than the value of the current node, the recursive call is made until the current value is found and deleted.
If the current value to be deleted is greater than the value of the current node, and vice versa;
Next, we add a lookup method:
Find the current node
class BinarySearchTree {
constructor() {
this._root = null
}
find(data) {
let current = this._root
while(current ! =null) {
if (current._data == data) {
return true
} else if (data < current._data) {
current = current._left
} else {
current = current._right
}
}
return false}}Copy the codeThis method is used to find a value, if the current query value is less than the value of the current node, the current node to the left to look;
Otherwise, if greater than, go directly to the right side of the query;
If the value is never queried, return false, otherwise true.
Find the minimum
class BinarySearchTree {
constructor() {
this._root = null
}
getMin() {
let current = this._root
while(current._left ! =null) {
current = current._left
}
return current._data
}
}
Copy the codeThis is a method to query the minimum value. Due to the particularity of binary search tree data structure, the value on the left side is always the smallest. Therefore, it is necessary to query to the lowest point and find the lowest left node to return.
Querying the maximum value
class BinarySearchTree {
constructor() {
this._root = null
}
getMax() {
let current = this._root
while(current._right ! =null) {
current = current._right
}
return current._data
}
}
Copy the codeThe opposite of the query minimum.
Now that we have all the ways to manipulate nodes in the binary search tree, it’s time to traverse the binary search tree.
Traverse the binary search tree
The binary search tree data traversal, in order, order, order traversal, the amount of code is relatively small, the code is not pseudo code is my own test, the results do not take a screenshot, the flow chart of the execution order, the results are interested in their own run:
In the sequence traversal
class BinarySearchTree {
constructor() {
this._root = null
}
inOrder(node) {
if(node ! =null) {
this.inOrder(node._left)
console.log(node.show())
this.inOrder(node._right)
}
}
}
Copy the codeFirst the left node is traversed, then the root node is traversed, and finally the right node is traversed as follows:
The first sequence traversal
class BinarySearchTree {
constructor() {
this._root = null
}
preOrder(node) {
if(node ! =null) {
console.log(node.show())
this.inOrder(node._left)
this.inOrder(node._right)
}
}
}
Copy the codeThis is sequential traversal, first traversing the root node, then traversing the left node, and finally traversing the right node, as follows:
After the sequence traversal
class BinarySearchTree {
constructor() {
this._root = null
}
postOrder(node) {
if(node ! =null) {
this.inOrder(node._left)
this.inOrder(node._right)
console.log(node.show())
}
}
}
Copy the codeThis is a back-order traversal, first traversing the leaf node, from left to right, and finally traversing the root node, as follows:
conclusion
Here, binary search tree explanation is almost enough, you have questions about where, feel free to comment.
This chapter was supposed to be the final chapter on vUE source parsing (before instantiation), but it covers a lot of stuff, and I want to summarize the previous chapters for the last chapter.
So this chapter will first write a chapter on algorithms, thank you for supporting 🙏