Sample code of javascript algorithm binary search tree

This article mainly introduces the example code of the binary search tree of the javascript algorithm. It has certain reference and value for learning JavaScript. Friends who are interested in JavaScript can refer to this article.

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

Based on the binary tree, the binary search tree has one more condition, that is, when inserting a value in the binary tree, if the inserted value is smaller than the current node, it is inserted into the left node, otherwise it is inserted into the right node. ; If during the insertion process, the left node or 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 whether it is adding, deleting or searching. (h), 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;
 }
}

Then construct a binary search tree

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

here this. The root is the tree of the current object.

New addition of binary search tree

The left subtree of the binary search tree is smaller than the node, and the right subtree is larger than the node. Features, you can easily write the algorithm for adding a binary search tree, 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}
  }
 }
}

The above code first determines the size of the new key and the key of the current node. If it is small, it recursively traverses the left child node. , until a left child node that is null is found; the same applies if it is larger than the current node. 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 the object here, the value of the object is memory, so the content of this.root will be directly changed every time.

Traversal of binary search trees

Binary search trees are divided into three traversal methods: pre-order, mid-order, and post-order.

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);
 }
}

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 push into the stack, then enter 7, then execute {1} to push into the stack, and then go to 5, execute {1} to insert stack, and then to 3, execute {1} to push into the stack. At this time, it is found that the left child node of node 3 is null, so it starts to pop up. At this time, the execution environment of node 3 pops up, execute {2}, {3}, and find 3 The right child node of is also null, the recursive execution of {3} is completed, then pop up node 5, execute {2}{3}, then pop up 7, execute {2}{3} and push it onto the stack, when {3} is executed, It is found that node 7 has a right node, so we continue to execute {1}, go to node 8, and then execute {1}. 8 has no left child node. After {1} is executed, {2}{3} is executed, and so on.

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

The same is true for post-order, the execution order is 1 3 2

It is not difficult to find that no matter the front, middle or post-order, the left node is always recursed first, and when the left node When the traversal is completed, pop the stack and traverse the nodes. The only difference between them is the timing of accessing the node itself.

Binary search tree search

The search is very simple. Based on the principle that the left child node is smaller than the node and the right child node is larger than the node, the loop judgment is made. Can.

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);
 }
}

Deletion of binary search tree

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);
  }
 }
}

Summary

In general, through this simple study of binary search trees, I learned about recursion again. My previous understanding of recursion was only a little bit A simple theoretical concept, this in-depth practice has deepened my understanding of recursion a lot.

This reminds me of the study of mathematics. The theoretical formulas of mathematics are easy to remember and master. If the full score for mastering a knowledge point is ten points, then until you actually practice it, Merely looking at the mastery of the formula can only give you 2 points, because the formula is very simple, just a few sentences and a few principles, but the problems encountered are ever-changing. Only by truly putting the theory into practice and polishing it through various practices can we Really understand the mystery of it.

Related recommendations:

Sharing the differences between three JavaScript simulation implementation encapsulation methods and writing methods

Detailed explanation of JavaScript self-executing functions and jQuery extension methods

Explanation of Require calling js examples in JavaScript

The above is the detailed content of Sample code of javascript algorithm binary search tree. For more information, please follow other related articles on the PHP Chinese website!