One article to understand how to implement a binary search tree in JS

One of the most commonly used and discussed data structures in computer science is thebinary search tree. This is usually the first data structure introduced with a nonlinear insertion algorithm. Binary search trees are similar to doubly linked lists, each node contains some data, and two pointers to other nodes; they differ in the way those nodes are related to each other. The pointers to binary search tree nodes are often called "left" and "right" and are used to indicate the subtree associated with the current value. A simple JavaScript implementation of such a node is as follows:

var node = { value: 125, left: null, right: null };

As you can see from the name, a binary search tree is organized into a hierarchical tree-like structure. The first item becomes the root node and each additional value is added to the tree as an ancestor of that root. However, the values on the nodes of a binary search tree are unique and ordered according to the value they contain: as the values in the left subtree of a node are always smaller than the node's value, the values in the right subtree are always larger than the node's value. In this way, finding values in a binary search tree becomes very simple, as long as the value you are looking for is smaller than the node you are working on then go left, if the value is larger then move right. There cannot be duplicates in a binary search tree because duplication breaks the relationship. The figure below represents a simple binary search tree.

#The above figure represents a binary search tree with a root value of 8. When the value 3 is added, it becomes the left child of the root because 3 is less than 8. When the value 1 is added, it becomes the left child of 3 because 1 is less than 8 (so to the left) and then 1 is less than 3 (again to the left). When the value 10 is added, it becomes the right child of follow because 10 is greater than 8. Continue this process with values 6, 4, 7, 14, and 13. The depth of this binary search tree is 3, meaning that the node furthest from the root is three nodes.

Binary search trees end up in a naturally sorted order and therefore can be used to find data quickly because you can eliminate the possibility of each step immediately. Searches can be made faster by limiting the number of nodes that need to be found. Suppose you want to find the value 6 in the tree above. Starting at the root, we determine that 6 is less than 8, so we go to the left child of the root. Since 6 is greater than 3, you will go to the right node. You can find the correct value. So you only need to visit three nodes instead of nine to find this value.

To implement a binary search tree in JavaScript, the first step is to define the basic interface:

function BinarySearchTree() { this._root = null; } BinarySearchTree.prototype = { //restore constructor constructor: BinarySearchTree, add: function (value){ }, contains: function(value){ }, remove: function(value){ }, size: function(){ }, toArray: function(){ }, toString: function(){ } };

The basic interface is similar to other data structures, with methods for adding and deleting values. I also added some convenience methods,size(),toArray(), andtoString(), which are useful for JavaScript.

To master the method of using binary search trees, it is best to start with thecontains()method. Thecontains()method accepts a value as a parameter and returnstrueif the value exists in the tree, otherwise it returnsfalse. This method follows a basic binary search algorithm to determine whether the value exists:

BinarySearchTree.prototype = { //more code contains: function(value){ var found = false, current = this._root //make sure there's a node to search while(!found && current){ //if the value is less than the current node's, go left if (value < current.value){ current = current.left; //if the value is greater than the current node's, go right } else if (value > current.value){ current = current.right; //values are equal, found it! } else { found = true; } } //only proceed if the node was found return found; }, //more code };

The search starts at the root of the tree. If no data is added, then there is probably no root, so you have to check. Traversing the tree follows the simple algorithm discussed earlier: move left if the value you are looking for is smaller than the current node, and move right if the value is larger. Thecurrentpointer is overwritten each time until the value sought is found (in which casefoundis set totrue) or there are no more in that direction node (in this case, the value is not in the tree).

The methods used incontains()can also be used to insert new values in the tree. The main difference is that you are looking for where to put the new value, rather than looking for the value in the tree:

BinarySearchTree.prototype = { //more code add: function(value){ //create a new item object, place data in var node = { value: value, left: null, right: null }, //used to traverse the structure current; //special case: no items in the tree yet if (this._root === null){ this._root = node; } else { current = this._root; while(true){ //if the new value is less than this node's value, go left if (value < current.value){ //if there's no left, then the new node belongs there if (current.left === null){ current.left = node; break; } else { current = current.left; } //if the new value is greater than this node's value, go right } else if (value > current.value){ //if there's no right, then the new node belongs there if (current.right === null){ current.right = node; break; } else { current = current.right; } //if the new value is equal to the current one, just ignore } else { break; } } } }, //more code };

The special case when adding a value in a binary search tree is when there is no root. In this case, just setting the root to a new value will do the job easily. For other cases, the basic algorithm is exactly the same as that used incontains(): go left if the new value is smaller than the current node, and go right if the value is larger. The main difference is that this is where the new value is when you can't go any further. So if you need to move left but there is no left node, the new value will be the left node (same as the right node). Since there are no duplicates, the operation stops if a node with the same value is found.

在继续讨论size()方法之前，我想深入讨论树遍历。为了计算二叉搜索树的大小，必须要访问树中的每个节点。二叉搜索树通常会有不同类型的遍历方法，最常用的是有序遍历。通过处理左子树，然后是节点本身，然后是右子树，在每个节点上执行有序遍历。由于二叉搜索树以这种方式排序，从左到右，结果是节点以正确的排序顺序处理。对于size()方法，节点遍历的顺序实际上并不重要，但它对toArray()方法很重要。由于两种方法都需要执行遍历，我决定添加一个可以通用的traverse()方法：

BinarySearchTree.prototype = { //more code traverse: function(process){ //helper function function inOrder(node){ if (node){ //traverse the left subtree if (node.left !== null){ inOrder(node.left); } //call the process method on this node process.call(this, node); //traverse the right subtree if (node.right !== null){ inOrder(node.right); } } } //start with the root inOrder(this._root); }, //more code };

此方法接受一个参数process，这是一个应该在树中的每个节点上运行的函数。该方法定义了一个名为inOrder()的辅助函数用于递归遍历树。注意，如果当前节点存在，则递归仅左右移动（以避免多次处理null）。然后traverse()方法从根节点开始按顺序遍历，process()函数处理每个节点。然后可以使用此方法实现size()、toArray()、toString()：

BinarySearchTree.prototype = { //more code size: function(){ var length = 0; this.traverse(function(node){ length++; }); return length; }, toArray: function(){ var result = []; this.traverse(function(node){ result.push(node.value); }); return result; }, toString: function(){ return this.toArray().toString(); }, //more code };

size()和toArray()都调用traverse()方法并传入一个函数来在每个节点上运行。在使用size()的情况下，函数只是递增长度变量，而toArray()使用函数将节点的值添加到数组中。toString()方法在调用toArray()之前把返回的数组转换为字符串，并返回 。

删除节点时，你需要确定它是否为根节点。根节点的处理方式与其他节点类似，但明显的例外是根节点需要在结尾处设置为不同的值。为简单起见，这将被视为 JavaScript 代码中的一个特例。

删除节点的第一步是确定节点是否存在：

BinarySearchTree.prototype = { //more code here remove: function(value){ var found = false, parent = null, current = this._root, childCount, replacement, replacementParent; //make sure there's a node to search while(!found && current){ //if the value is less than the current node's, go left if (value < current.value){ parent = current; current = current.left; //if the value is greater than the current node's, go right } else if (value > current.value){ parent = current; current = current.right; //values are equal, found it! } else { found = true; } } //only proceed if the node was found if (found){ //continue } }, //more code here };

remove()方法的第一部分是用二叉搜索定位要被删除的节点，如果值小于当前节点的话则向左移动，如果值大于当前节点则向右移动。当遍历时还会跟踪parent节点，因为你最终需要从其父节点中删除该节点。当found等于true时，current的值是要删除的节点。

删除节点时需要注意三个条件：

1、叶子节点

2、只有一个孩子的节点

3、有两个孩子的节点

从二叉搜索树中删除除了叶节点之外的内容意味着必须移动值来对树正确的排序。前两个实现起来相对简单，只删除了一个叶子节点，删除了一个带有一个子节点的节点并用其子节点替换。最后一种情况有点复杂，以便稍后访问。

在了解如何删除节点之前，你需要知道节点上究竟存在多少个子节点。一旦知道了，你必须确定节点是否为根节点，留下一个相当简单的决策树：

BinarySearchTree.prototype = { //more code here remove: function(value){ var found = false, parent = null, current = this._root, childCount, replacement, replacementParent; //find the node (removed for space) //only proceed if the node was found if (found){ //figure out how many children childCount = (current.left !== null ? 1 : 0) + (current.right !== null ? 1 : 0); //special case: the value is at the root if (current === this._root){ switch(childCount){ //no children, just erase the root case 0: this._root = null; break; //one child, use one as the root case 1: this._root = (current.right === null ? current.left : current.right); break; //two children, little work to do case 2: //TODO //no default } //non-root values } else { switch (childCount){ //no children, just remove it from the parent case 0: //if the current value is less than its //parent's, null out the left pointer if (current.value < parent.value){ parent.left = null; //if the current value is greater than its //parent's, null out the right pointer } else { parent.right = null; } break; //one child, just reassign to parent case 1: //if the current value is less than its //parent's, reset the left pointer if (current.value < parent.value){ parent.left = (current.left === null ? current.right : current.left); //if the current value is greater than its //parent's, reset the right pointer } else { parent.right = (current.left === null ? current.right : current.left); } break; //two children, a bit more complicated case 2: //TODO //no default } } } }, //more code here };

处理根节点时，这是一个覆盖它的简单过程。对于非根节点，必须根据要删除的节点的值设置parent上的相应指针：如果删除的值小于父节点，则left指针必须重置为null（对于没有子节点的节点）或删除节点的left指针；如果删除的值大于父级，则必须将right指针重置为null或删除的节点的right指针。

如前所述，删除具有两个子节点的节点是最复杂的操作。考虑二元搜索树的以下表示。

根为 8，左子为 3，如果 3 被删除会发生什么？有两种可能性：1（3 左边的孩子，称为有序前身）或4（右子树的最左边的孩子，称为有序继承者）都可以取代 3。

这两个选项中的任何一个都是合适的。要查找有序前驱，即删除值之前的值，请检查要删除的节点的左子树，并选择最右侧的子节点；找到有序后继，在删除值后立即出现的值，反转进程并检查最左侧的右子树。其中每个都需要另一次遍历树来完成操作：

BinarySearchTree.prototype = { //more code here remove: function(value){ var found = false, parent = null, current = this._root, childCount, replacement, replacementParent; //find the node (removed for space) //only proceed if the node was found if (found){ //figure out how many children childCount = (current.left !== null ? 1 : 0) + (current.right !== null ? 1 : 0); //special case: the value is at the root if (current === this._root){ switch(childCount){ //other cases removed to save space //two children, little work to do case 2: //new root will be the old root's left child //...maybe replacement = this._root.left; //find the right-most leaf node to be //the real new root while (replacement.right !== null){ replacementParent = replacement; replacement = replacement.right; } //it's not the first node on the left if (replacementParent !== null){ //remove the new root from it's //previous position replacementParent.right = replacement.left; //give the new root all of the old //root's children replacement.right = this._root.right; replacement.left = this._root.left; } else { //just assign the children replacement.right = this._root.right; } //officially assign new root this._root = replacement; //no default } //non-root values } else { switch (childCount){ //other cases removed to save space //two children, a bit more complicated case 2: //reset pointers for new traversal replacement = current.left; replacementParent = current; //find the right-most node while(replacement.right !== null){ replacementParent = replacement; replacement = replacement.right; } replacementParent.right = replacement.left; //assign children to the replacement replacement.right = current.right; replacement.left = current.left; //place the replacement in the right spot if (current.value < parent.value){ parent.left = replacement; } else { parent.right = replacement; } //no default } } } }, //more code here };

具有两个子节点的根节点和非根节点的代码几乎相同。此实现始终通过查看左子树并查找最右侧子节点来查找有序前驱。遍历是使用while循环中的replacement和replacementParent变量完成的。

replacement中的节点最终成为替换current的节点，因此通过将其父级的right指针设置为替换的left指针，将其从当前位置移除。

For the root node, whenreplacementis a direct child node of the root node,replacementParentwill benull, soreplacement's Therightpointer is just therightpointer set to root.

The final step is to assign the replacement node to the correct location. For root nodes, the replacement is set to the new root; for non-root nodes, the replacement is assigned to the appropriate location on the originalparent.

A note about this implementation: Replacing nodes always with an ordered predecessor can result in an unbalanced tree, where most values will be on one side of the tree. An unbalanced tree means less efficient search and should therefore be of concern in real-life scenarios. In a binary search tree implementation, it is important to determine whether to use an ordered predecessor or an ordered successor to keep the tree properly balanced (often called a self-balancing binary search tree).

The complete source code of this binary search tree implementation can be found in myGitHub. For an alternative implementation, you can also check outIsaac Schlueter'sGitHub fork.

This article is reproduced from: https://segmentfault.com/a/1190000020044659

English original address: https://humanwhocodes.com/blog/2009/06/09/ computer-science-in-javascript-binary-search-tree-part-1/

Author: Nicholas C. Zakas

Recommended tutorial: "JavaScript Video Tutorial》

The above is the detailed content of One article to understand how to implement a binary search tree in JS. For more information, please follow other related articles on the PHP Chinese website!