【数据结构】二叉搜索树(BST)

定义

1、一棵二叉树:

  • 或者为空;
  • 或者包含三部分——一个值、一个左分支和一个右分支,并且这两个分支也都是二叉树。

2、一颗二叉搜索树是满足下面条件的二叉树:

  • 所有左分支的值都小于本节点的值;
  • 本节点的值小于所有右分支的值。

3、二叉搜索树的定义要求它的值必须能比较大小。为了强调这种区别,特称二叉搜索树的值为键,把节点存储的其他数据信息称为值。

数据组织

二叉搜索树的节点:

function Node(data, left, right) {
    //属性
    this.data = data;
    this.left = left;
    this.right = right;
    //方法
    this.show = show;
}
function show(){
    return this.data;
}

插入

算法描述:
用下述算法向一棵二叉搜索树中插入一个键k,

  • 如果树为空,创建一个叶子结点,令该节点的 key = k ;
  • 如果 k 小于根节点的 key ,将它插入到左子树中;
  • 如果 k 大于根节点的 key ,将它插入到右子树中。

算法描述函数:
insert(T,k)=node(ϕ,k,ϕ),node(insert(Tl,k),k,Tr),node(Tl,k,insert(Tr,k)),T=ϕk<k
其中,当T不为空时, Tl,Trk 分别是它的左右子树和key。函数node以给定的左子树、key和右子树为参数创建一个新节点。

实现:

function BST() { //初始化二叉搜索找树
    //属性
    this.root = null;
    //方法
    this.insert = insert;  //插入函数
    this.inOrder = inOrder; //中序遍历函数
}

function insert(data) {
    var n = new Node(data, null, null);
    if (this.root == null) {
        this.root = n;
    } else {
        var current = this.root;
        var parent;
        while (true) {
            parent = current;
            if (data < current.data) {
                current = current.left;
                if (current == null) {
                    parent.left = n;
                    break;
                }
            } else {
                current = current.right;
                if (current == null) {
                    parent.right = n;
                    break;
                }
            }
        }
    }
}

遍历

1、有三种遍历 BST 的方式: 中序遍历、 前序遍历和后序遍历。
2、中序遍历的算法描述:

  • 如果树为空,则返回;
  • 否则,先中序遍历左子树,然后访问根节点,最后再中序遍历右子树。

算法描述函数:
如果二叉树非空,令 TlTrk 分别代表左右子树和key,可以定义下面的抽象map函数:
map(f,T)={ϕ,node(Tl,h,Tr),T=ϕ
其中, Tl=map(f,Tl)Tr=map(f,Tr)k=f(k)
实现:

//中序遍历
function inOrder(node){
    if(node != null){
        inOrder(node.left);
        console.log(node.show());
        inOrder(node.right);
    }
}

//前序遍历
function perOrder(node){
    if(node != null){
        console.log(node.show());
        perOrder(node.left);
        perOrder(node.right);
    }
}

//后续遍历
function postOrder(node){
    if(node != null){
        postOrder(node.left);
        postOrder(node.right);
        console.log(node.show());
    }
}

4、通过中序遍历得到一个排序方法:
先把一个无序列表转化为一棵二叉搜索树,然后再用中序遍历把树转换回列表。

var array = [23,45,16,37,3,99,22];
var nums = new BST();
for(var i in array){
    nums.insert(array[i]);
}
console.log("Inorder traversal: ");
inOrder(nums.root); 

// Inorder traversal: 3 16 22 23 37 45 99

搜索

BST 通常有下列三种类型的查找:

  • 查找给定元素(lookup)
  • 查找最大或最小元素
  • 查找给定元素的上一个(predecessor)或下一个元素(successor)

lookup

算法描述:
我们可以按照下面描述的方法在树中查找一个key:

  • 如果树为空,查找失败
  • 如果根节点的key等于待查找的值,查找成功,返回根节点作为结果;
  • 如果待查找的值小于根节点的key,继续在左子树中递归查找;
  • 如果待查找的值大于根节点的key,继续在右子树中递归查找。

算法描述函数:
lookup(T,x)=ϕ,T,lookup(Tl,x),lookup(Tr,x),T=ϕk=xx<k

算法时间复杂度:
如果二叉树很平衡,绝大多数节点都有非空的左右分支,对于n个元素的二叉树,搜素算法的性能为 O(lgn) 。如果二叉树很不平衡,最坏情况下,查找的时间会退化到 O(n) 。若记树的高度为 h ,则算法的性能可以统一成 O(h) 的形式。

实现:

/* * findup:在BST中查找一个元素 * 如果找到给定值, 该方法返回保存该值的节点; 如果没找到, 该方法返回 null。 */
 function findup(data){ //递归实现
    var current = this.root;
     while(current!=null){
         console.log(current)
         if(current.data == data){
             return current;
         } else if(data<current.data){
             current = current.left;
         } else if(data > current.data){
             current = current.right;
         }
     }
     return null;
 }

function findup(data){ //迭代实现
     var current = this.root;
     while(current!=null && current.data!=data){
         if(data < current.data ){
             current = current.left;
         } else {
             current = current.right;
         }
     }
     return current;
 }

最小元素和最大元素

算法描述:
在BST中,较小的元素总是位于左侧分支,而较大的元素总是位于右侧分支。为了获取较小元素,可以不断向左侧前进,知道左侧分支为空。同样的,可以通过向右侧前进来获取最大元素。
算法描述函数:
min(T)={k,min(Tl),Tl=ϕ
max(T)={k,max(Tr),Tr=ϕ
算法时间复杂度:
两个函数的性能都是 O(h) ,其中 h 是树的高度。当二叉树比较平衡时, minmax 的性能都是 O(lgn) ,最坏情况下,性能退化为 O(n)
实现:

/* * getMin():取得BST最小值 */
function getMin() {
    var current = this.root;
    while (current.left != null) {
        current = current.left;
    }
    return current.data;
}

/* - getMax():取得BST最小值 */
 function getMax() {
    var current = this.root;
    while (current.right!= null) {
        current = current.right;
    }
    return current.data;
 }

前驱和后继

后继(Succ):给定元素 x ,它的后继元素 y 是满足 y>x 的最小值。
有两种情况:

  • 如果 x 所在的节点有一个非空的右子树,则右子树中的最小值就是答案。
  • 如果 x 没有非空的右子树,则需要向上回溯,找到最近的一个祖先,使得该祖先的左侧孩子,也为 x 的祖先。

实现:

/* * Succ:后继函数 * param: x——给定元素 * return:返回给顶元素在BST中的后继 */
function Succ(x){
  if(x.right!=null){
        //getMin(node) 获取以node节点为根节点的BST的最小值
        return this.getMin(x.right);
    } else{
        //Node节点有一个parent属性来保存父节点
        var parent = x.parent;
        while(parent!=null&&x ==parent.right){
            x = parent;
            parent = parent.parent;
        }
        return parent;
    }
}
/* * Pred:前驱函数 * param: x——给定元素 * return:返回给顶元素在BST中的前驱 */
function Pred(x){
    if(x.left!=null){
        //getMax(node) 获取以node节点为根节点的BST的最大值
        return this.getMax(x.left);
    } else{
        var parent = x.parent;
        while(parent!=null&&x ==parent.left){
            x = parent;
            parent = parent.parent;
        }
        return parent;
    }
}

删除

算法描述:
从二叉搜索树中删除节点 x 的方法如下:

  • 如果 x 没有子节点,或者只有一个孩子,直接将 x “切下”;
  • 如果 x 有两个孩子,我们用其右子树中的最小值替换 x ,然后将右子树中的这一最小值“切掉”。

因为右子树中的最小值节点不可能有两个非空的孩子,因此将上面第二种情况简化为第一种情况,因而可以直接将最小值节点“切掉”。

算法描述函数:
delete(T,x)=ϕnode(delete(Tl,x),k,Tr)node(Tl,k,delete(Tr,x))TrTlnode(Tl,y,delete(TR,y)):T=ϕ:x<k:x>k:x=kTl=ϕ:x=kTr=ϕ:x=kTl,Tr
其中, TlTrk 分别是当 T 非空时的左右子树和key:
Tl=left(T)Tr=right(T)k=key(T)y=min(Tr)

实现:

/* * removeData:删除数据 * param: * node——要删除数据的节点 * data——要删除的数据 * return: * 已删除data数据的树根节点 */
function removeData(node,data){
  if(node == null){ //空树
        return null;
    }
    if (data == node.data) {
        if (node.left == null && node.right == null) { //没有子节点的节点
            return null;
        }
        if (node.left == null) { //没有左子树的节点
            return node.right;
        }
        if (node.right == null) { //没有右子树的节点
            return node.left;
        }
        //有左右子树的节点
        var tempNode = getMin(node.right);
        node.data = tempNode.data;
        node.right = removeData(node.right,tempNode.data);
        return node;
    }else if(data < node.data){
        node.left = removeData(node.left,data);
        return node;
    }else{
        node.right = removeData(node.right,data);
        return node;
    }

}
/* * remove() 方法:简单地接受待删除数据 */
function remove(data){
   this.root = removeData(this.root,data);
}

//test
var nums = new BST();
var arr = [4,3,8,1,16,2,10,9,14]; for(var i in arr){ nums.insert(arr[i]); } nums.remove(4); console.log(nums.root);
相关文章
相关标签/搜索