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 the binary 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(), and toString(), which are useful for JavaScript.

To master the method of using binary search trees, it is best to start with the contains() method. The contains() method accepts a value as a parameter and returns true if the value exists in the tree, otherwise it returns false. 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&#39;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. The current pointer is overwritten each time until the value sought is found (in which case found is set to true) or there are no more in that direction node (in this case, the value is not in the tree).

The methods used in contains() 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&#39;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&#39;s value, go right
                } else if (value > current.value){

                    //if there&#39;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 in contains(): 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&#39;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&#39;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&#39;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&#39;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, when replacement is a direct child node of the root node, replacementParent will be null, so replacement's The right pointer is just the right pointer 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 original parent.

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 my GitHub. For an alternative implementation, you can also check out Isaac Schlueter's GitHub 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!