Detailed explanation of using JS binary search tree-JS Tutorial-php.cn

This time I will bring you a detailed explanation of the use of JS binary search trees. What are the precautions when using JS binary search trees? The following is a practical case. Get up and take a look.

What is a binary tree

A binary tree means that each node of the tree can only have at most two child nodes

What is a binary search tree

On the basis of the binary tree, the binary search tree has an additional condition, that is, when inserting a value in the binary tree, if the inserted value is smaller than the current node, it will be inserted into the left node, otherwise it will be inserted into the right node; if during the insertion process, the left node or If the right node already exists, then continue to compare according to the above rules until a new node is encountered.

Characteristics of binary search trees

Due to its unique data structure, the binary search tree has a time complexity of O(h) whether it is adding, deleting or searching. h is the height of the binary tree. Therefore, the binary tree should be as short as possible, that is, the left and right nodes should be as balanced as possible.

Construction of binary search tree

To construct a binary search tree, you must first construct the node class of the binary tree. It can be seen from the characteristics of binary trees that each node class has a left node, a right node and the value itself, so the node class is as follows:

class Node {
 constructor(key) {
  this.key = key;
  this.left = null;
  this.right = null;
 }
}

Copy after login

Then construct a binary search tree

class Tree{
 constructor(param = null) {
  if (param) {
   this.root = new Node(param);
  } else {
   this.root = null;
  }
 }
}

Copy after login

Here this.root is the tree of the current object.

Binary search treeNew addition

Due to the characteristics of the binary search tree that the left subtree is smaller than the node and the right subtree is larger than the node, the new algorithm for the binary search tree can be easily written, as follows:

insert(key) {
 if (this.root === null) {
  this.root = new Node(key);
 } else {
  this._insertNode(this.root, key);
 }
}
_insertNode(node, key) {
 if (key < node.key) {
  if (node.left === null) {
   node.left = new Node(key);{1}
  } else {
   this._insertNode(node.left, key);{2}
  }
 } else if (key > node.key) {
  if (node.right === null) {
   node.right = new Node(key);{3}
  } else {
   this._insertNode(node.right, key);{4}
  }
 }
}

Copy after login

The above code first determines the key size of the newly added key and the current node. If it is smaller, it recursively traverses the left child node until it finds a null left child node; if it is larger than the current node, the same principle applies. The reason why the above code {1}{2}{3}{4} can change the value of this.root is because the JavaScript function is passed by value, and when the parameter is a non-basic type, such as here Object, the value of its object is memory, so the content of this.root will be directly changed every time.

Traversal of binary search tree

Binary search trees are divided into three traversal methods: preorder, inorder, and postorder.

inOrderTraverse(callback) {
 this._inOrderTraverse(this.root, callback);
}
_inOrderTraverse(node, callback) {
 if (node) {
  this._inOrderTraverse(node.left, callback);
  callback(node.key);
  this._inOrderTraverse(node.right, callback);
 }
}

Copy after login

The above is an in-order traversal.

The thing to understand here is recursion. You know, the execution of a function can be abstracted into a data structure - a stack. For the execution of the function, a stack is maintained to store the execution of the function. Each time the function recurses, it will push the current execution environment onto the stack and record the execution location. Taking the above code as an example, there is the following data

It will start from 11, execute {1} to the stack, then go to 7, then execute {1} to the stack, then go to 5, execute {1} to the stack, and then go to 3, execute {1} to the stack. At this time, it is found that The left child node of node 3 is null, so it starts to pop off the stack. At this time, the execution environment of node 3 pops up, execute {2}, {3}, and find that the right child node of 3 is also null, and the recursive execution of {3} is completed. , then pop up node 5, execute {2}{3}, then pop up node 7, execute {2}{3} onto the stack, when executing {3}, it is found that node 7 has a right node, so continue executing {1}, to the node 8, execute {1} again, 8 has no left child node, {1} is executed, {2}{3} is executed, and so on.

The difference between preorder and midorder is that the node itself is visited first, that is, the execution order of the code is 2 1 3.

The same applies to the post-order, the execution order is 1 3 2

It is not difficult to find that no matter the order is before, during or after, the left node is always recursed first. When the left node is traversed, the stack is popped and all nodes are traversed. The only difference between them is the timing of accessing the node itself.

Binary search tree search

The search is very simple, just make a loop judgment based on the principle that the left child node is smaller than the node and the right child node is larger than the node.

search(value) {
 if (this.root) {
  if (value === this.root.key) {
   return true;
  } else {
   return this._searchNode(value, this.root);
  }
 }
 throw new Error('this.root 不存在');
}
_searchNode(value, node) {
 if (!node) {
  return false;
 }
 if (value === node.key) {
  return true;
 }
 if (value > node.key) {
  return this._searchNode(value, node.right);
 } else if (value < node.key) {
  return this._searchNode(value, node.left);
 }
}

Copy after login

Binary search treeDelete

Deletion is more complicated and needs to be judged according to different situations

First determine whether the node has a left subtree. If there is no left subtree, directly replace the deleted node with the root node of the right subtree;

If there is, replace the deleted node with the smallest node of the right subtree;

remove(key) {
 this._removeNode(this.root, key);
}
_removeNode(node, value) {
 if (!node) {
  return null;
 }
 if (value > node.key) {
  node.right = this._removeNode(node.right, value);
 } else if (value < node.key) {
  node.left = this._removeNode(node.left, value);
 } else {
  // 如果没有左子树，那么将右子树根节点作为替换节点
  if (!node.left) {
   return node.right;
   // 如果存在左子树，那么取右子树最小节点作为替换节点
  } else if (node.left) {
   return this._minNode(node.right);
  }
 }
}

Copy after login

总结

总的来说，通过这次简单的二叉搜索树的学习，让我重新认识了递归，以前对于递归的理解只是一些简单的理论概念，这次深入实践让我对递归的理解又加深了许多。

这让我想到了数学的学习，数学的理论公式是很容易记住掌握的，如果说对一个知识点的掌握满分是十分，那么直到真正去实践它之前，只看公式的掌握只能是2分，因为公式很简单，就几句话几个原则，但是遇到的问题是千变万化的，只有真正将理论付诸实践，经过各种实践的打磨蹂躏，才能真正理解它其中的奥秘。

相信看了本文案例你已经掌握了方法，更多精彩请关注php中文网其它相关文章！