数据结构与算法的JavaScript实现及应用 – 二叉查找树

摘要

在这篇文章里,我将介绍二叉查找树的基本操作和应用。

我们将看到二叉查找树操作的JavaScript的递归实现。由于递归受堆栈深度的限制,我们还将考虑非递归的实现。

最后我们将其与线性表结构进行对比,总结二叉查找树的优劣和应用场景。

关于本系列

文章列表

[php_everywhere]

开放源码

  • 本系列的所有代码均开源,托管在Github
  • 所有Demo均托管在JSFiddle,点击查看

二叉查找树

二叉查找树又称二叉搜索树,其维基百科的定义为:

二叉查找树(Binary Search Tree),也称有序二叉树(ordered binary tree),排序二叉树(sorted binary tree),是指一棵空树或者具有下列性质的二叉树:
  1. 若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  2. 若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
  3. 任意节点的左、右子树也分别为二叉查找树;
  4. 没有键值相等的节点。

根据定义,我们知道二叉查找树中的节点最多只有两个分支,即左子树和右子树。节点需要一个键key来标明其唯一性。 我们可以定义二叉查找树的节点如下:

function BstNode(key, value, parent) {
    //键
    this.key = key;
    //值域
    this.valueList = [value];
    //父节点
    this.parent = parent || null;
    //左节点
    this.left = null;
    //右节点
    this.right = null;
}

以上定义还包含了parent域,用于保存节点的父节点。valueList域为值域,为一个数组,用于保存相同键下的不同值。

在一颗二叉查找树里,我们只要获取了根节点,便可遍历所有节点,故我们定义二叉查找树如下:

function BinarySearchTree() {
    //根
    this.root = null;
}

操作

二叉查找树的操作有很多,其基本操作为查找,插入,删除,遍历等。

由于二叉查找树的左右子树均为二叉查找树,这是一种递归的定义,所以我们可以很容易用递归的思路来操作它。

但是由于递归需要调用堆栈,一旦递归层数超过系统上限,则会堆栈溢出。所以我们也有必要了解其非递归的解法。

查找

顾名思义,二叉查找树的首要目标是查找。

递归解法
  • 递归的终止条件为:当前处理的节点为空或查找成功
  • 递归的缩小问题为:若当前节点比查找值小,则转至当前节点的右子树进行查找;否则转至当前节点的左子树进行查找
BinarySearchTree.prototype._find = function(node, key) {
    if(node == null || node.key == key) {
        return node;
    }
    if(node.key > key) {
        return this._find(node.left, key);
    }
    return this._find(node.right, key);
};
非递归解法

我们可以看到递归形式的查找其实是一种尾递归,尾递归其实就是一种循环展开,所以我们不需要借助栈即可实现非递归版本的查找。

BinarySearchTree.prototype.findNR = function(key) {
    var node = this.root;
    while(node) {
        if(node.key == key) {
            return node;
        }
        if(node.key > key) {
            node = node.left;
        }
        else {
            node = node.right;
        }
    }
    return node;
};
查找最小和最大节点

由于左子树永远小于根,右子树永远大于根,故而找到最小和最大的节点非常直观。

即,最左的节点为最小节点,最右的节点为最大节点。

由于代码相似,以下只列出找到最小节点的代码:

BinarySearchTree.prototype._findMin = function(root) {
    while(root && root.left) {
        root = root.left;
    }
    return root;
};
时间复杂度

设树的高度为h,由于查找每次都会向下下降一层,所以其时间复杂度为O(h)。

最坏的情况就是,所有左子树为空或所有右子树为空。这样,二叉查找树与单链表是一样的,树的高度跟链表长度一样为n,时间复杂度为O(n)。

如果是一颗完全二叉树,则树的高度为log(n),时间复杂度为O(log(n))。

可以证明,如果是随机构建的二叉查找树,树的高度的期望为log(n)。

插入

递归解法

插入跟查找十分类似,因为插入需要寻找到合适的节点后,然后再进行插入,所以其本身就是一种查找插入点的过程。

BinarySearchTree.prototype._add = function(node, key, value) {
    //根节点特殊处理
    if(this.root == null) {
        this.root = new BstNode(key, value);
        return ;
    }
    if(key < node.key) {
        node.left == null ? 
            node.left = new BstNode(key, value, node) :
            this._add(node.left, key, value);
    }
    else if(key > node.key) {
        node.right == null ? 
            node.right = new BstNode(key, value, node) : 
            this._add(node.right, key, value);
    }
    else {
        node.valueList.push(value);
    }
};

当树中已经存在相同key的节点时,我们把值放入该节点的valueList域,以兼容同key不同值。

由于插入与查找类似,所以不列出非递归解法的代码。

时间复杂度

时间复杂度和查找相同,为O(h),h为树的高度。

最坏情况为O(n),最好情况为O(log(n)),随机插入的平均情况为O(log(n))。

删除

删除是一个比较复杂的操作,因为它有三种不同的情况:

  1. 待删除的节点是叶子节点(无左右子树)
  2. 待删除的节点只有左子树或只有右子树
  3. 待删除的节点既有左子树又有右子树

以下是对应的解决方法:

第一种情况最好解决,因为可以直接将其删除,而不影响树的其他部分。

第二种情况也比较好解决,因为它只有一边的子树,删除了它,我们只需要让它的那一边子树代替它原来的位置就行了。

第三种情况是最复杂的,但是解决的方法却很好理解。 解决的方法是:

  1. 选择右子树中key最小的节点,或左子树中key最大的节点,设该节点为P
  2. 可以知道节点P是最接近待删节点的节点,我们将待删节点置换成节点P
  3. 再递归删除节点P

递归解法
BinarySearchTree.prototype._remove = function(key, value, root) {
    if(!root) return null;  

    if(key < root.key) {
        //递归一
        this._remove(key, value, root.left);
    }
    else if(key > root.key) {
        //递归二
        this._remove(key, value, root.right);
    }
    else if(value && root.valueList.length > 1) {
        root.valueList.splice(root.valueList.indexOf(value), 1);
    }
    //第三种情况
    else if(root.left && root.right) {
        var rightMin = this._findMin(root.right);
        root.key = rightMin.key;
        root.valueList = rightMin.valueList;
        //递归三
        this._remove(root.key, null, root.right);
    }
    //第一种和第二种情况合并处理
    else {
        var next = root.left ? root.left : root.right
        if(root == this.root) {
            this.root = next;
            this.root.parent = null;
            return;
        }
        if(root.key >= root.parent.key) {
            root.parent.right = next;
        }
        else if(root.key < root.parent.key) {
            root.parent.left = next;
        }
        if(next) {
            next.parent = root.parent;
        }
    }
    return root;
};
非递归解法

在递归解法中,我们看到有三处递归。

其中前两次递归都是在查找待删除的节点,这与查找的非递归是一样的;而最后一次的递归则出现在第三种情况里,其实我们只需要深入分析一下第三种情况,即可避免递归。

以选取右子树的最小节点为P举例,我们可以肯定P没有左子树,这就退化到了第二种情况。这时候删除P,只需要将P的右子树连接到P的父节点即可。

由于代码大部分类似,以下将不给出非递归代码。

时间复杂度

删除操作分为两部分:

  1. 查找待删除的节点,其时间复杂度就是查找的时间复杂度,为O(h),h为树高度;
  2. 执行删除操作,我们可以通过非递归解法看到三种情况的删除,都只需要常数级别的操作即可完成,故其时间复杂度为O(1)。

所以删除操作的时间复杂度为O(h),h为树的高度,与查找,插入相同。

中序遍历

中序遍历的意思是指按照左子树->根->右子树的顺序对树进行遍历。

由于二叉查找树的特殊结构,对其进行中序遍历,可以获得一个升序的序列。

递归解法

按照中序遍历的描述可以很自然的想到递归解法。

  • 递归的终止条件为:当前节点为空节点
  • 递归的缩小方法为:分别对当前节点的左子树和右子树进行递归
BinarySearchTree.prototype._inOrderTravel = function(root, func) {
    if(root) {
        this._inOrderTravel(root.left, func);
        func(root);
        this._inOrderTravel(root.right, func);
    }
};  
非递归解法

也许非递归解法才是一个真正的挑战,在阅读下文之前,建议读者拿出纸笔,设想如何用非递归解法来对二叉查找树进行中序遍历。

前文中,我们知道递归其实就是一种函数调用,该调用需要用到栈来保存递归进入时当前的变量,称之为调用栈。

其实递归转换为非递归的解法关键就在于:我们自建一个调用栈,来保存进入递归时的当前变量

仔细观察递归的代码。

  • 若当前节点有左子树,则需要对左子树进行递归。此时,调用栈需要把当前节点入栈以备返回时使用;
  • 若当前节点没有左子树,则可以直接遍历当前节点。需要判断当前节点是否有右子树:
    • 若有右子树,则将当前节点设为右节点,继续遍历;
    • 若没有右子树,说明对当前节点的处理工作结束,需要进行递归返回。此时,若调用栈不为空,我们将调用栈出栈,遍历出栈节点,直至其有右子树。
BinarySearchTree.prototype.inOrderTravelNR = function(func) {
    var node = this.root;
    var stack = [];
    while(node) {
        if(node.left) {
            stack.push(node);
            node = node.left;
        }
        else {
            func(node);
            while(! node.right) {
                node = stack.pop();
                if(! node) {
                    return ;
                }
                func(node);
            }
            node = node.right;
        }
    }
};
时间复杂度

我们设具有n个节点的二叉查找树的中序遍历时间复杂度为T(n),设左边有k个节点,则右边有n-k-1个节点。

故而:

可以得出:

所以中序遍历的时间复杂度为O(n)。

应用

二叉查找树的应用十分广泛。

C++里的map和set就是基于二叉查找树的原理实现的。

由于二叉查找树的特殊结构,导致其十分适合于动态查询的数据系统。

因为所有的数据在插入之后便成为有序序列,而且二叉查找树的插入,查找,删除的平均时间复杂度为O(log(n)),这是非常高效的。

设想一个系统,需要频繁插入、删除数据,获取分段有序序列,获取排名等等。如果用数组等实现的话,每一次插入删除后都需要重新排序,才能获取有序序列。而二叉查找树则可以在插入删除时,动态的调整树,使其输出仍为一个有序序列。

然而二叉查找树的最坏情况,将其退化为单链表,从而导致其效率急剧下降。故而二叉查找树需要进行一定的修正才能运用于实际场合。

对比

查找 随机访问 插入 删除 有序访问 需要排序
二叉查找树 O(log(n)) 不支持 O(log(n)) O(log(n)) 支持 不需要
数组 O(n) 支持 O(n) O(n) 支持 需要
单链表 O(n) 不支持 O(1) O(1) 支持 需要
字典 O(1) 支持 O(1) O(1) 不支持 需要

总结

二叉查找树由于其构造的特性,使得其特别适合于需要动态查询的数据结构。

由于二叉查找树中序遍历即为有序序列,也使得其适合需要经常排序的数据结构。

但是二叉查找树存在最坏情况,即左右子树为空和输入为有序序列,这时,二叉查找树退化为单链表,丧失其所有优势。

我们需要对二叉查找树进行平衡化处理,使得其形态与平衡二叉树靠近,从而达到避免最坏情况的出现。

关注微信公众号:timind

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注