特点

  1. 左子树的节点 < 根节点 < 右子树节点
  2. 没有重复节点

查找

    search(key, node = this.roots) {
        if (node) {
            if (key < node.key) {
                return this.search(node.left, key);
            } else if (key > node.key) {
                return this.search(node.right, key);
            } else {
                return true;
            }
        } else {
            return false;
        }
    }

插入和删除

插入很简单,就是在树的最底层寻找一个合适的位置。

   insert(key) {
        let newNode = {
            key: key,
            left: null,
            right: null
        };
        if (!this.roots) {
            this.roots = newNode;
        } else {
            this.insertNode(this.roots, newNode);  // 从根节点开始
        }
        return this;  // 链式操作
    };

    insertNode(node, newNode) {
        if (newNode.key < node.key) {
            if (!node.left) {
                node.left = newNode;
            } else {
                this.insertNode(node.left, newNode);
            }
        } else if(newNode.key > node.key){
            if (!node.right) {
                node.right = newNode;
            } else {
                this.insertNode(node.right, newNode);
            }
        }else{
            return false;  //不能有键值相等的节点
        }
    }

删除比较复杂,要根据子节点情况分三类进行操作:
1.如果没有子节点直接删除
2.如果有一个子节点那么将孩子提升到被删除元素的位置
3.如果有两个子节点则需要用被删除节点的右子树中最小节点替换,如下图所示:

屏幕快照 2017-05-11 下午6.06.00.png

    remove(key, node = this.roots) {
        if (node === null) {
            return false;
        }

        if (key < node.key) {
            node.left = this.remove(key, node.left);
            return node;
        } else if (key > node.key) {
            node.right = this.remove(key, node.right);
            return node;
        } else {
            //如果没有子节点直接删除
            //如果有一个子节点那么将孩子提升到被删除元素的位置
            if (node.left === null && node.right === null) {
                node = null;
                return node;
            } else if (node.left === null) {
                node = node.right;
                return node;
            } else if (node.right === null) {
                node = node.left;
                return node;
            } else {
                //如果有两个子节点
                console.log(node)
                let aux = this.findMinNode(node.right);  //在右子树中向左到尽头找到最小节点
                node.key = aux.key;
                node.right = this.remove(aux.key, node.right);
                return node;
            }
        }
    }

    findMinNode(node) {
        while (node && node.left) {
            node = node.left;
        }
        return node;
    }

复杂度

搜索、插入、删除的复杂度等于树高。
同样一棵二叉搜索树,全部由插入生成的和经过插入和删除的两棵树就不一样。树高的期望为 {O(log n)},最坏 {O(n)}

正因为这种随机性,特别是当插入有序的节点时,树就会退化成线性表,所以我们还会对二叉搜索树进行优化,让其拥有最好的最坏复杂度。你听说过的红黑树、AVL树就是解决这一问题而出现的,下篇文章我们会介绍。