看图说话之二叉排序树

2018-04-12 本文已影响0人涂印

一丶二叉排序树基本介绍

二叉树是一种常见的树结构，二叉排序树是二叉树的一种特殊情况，其在二叉树的基础上施加了一种“顺序性”的约束，BST在排序和查找中具有广泛的运用下图就是一个常见的BST(Binary sort tree,二叉排序树 )。

图1 二叉排序树

二叉树是一种常见的树结构，二叉排序树是二叉树的一种特殊情况，其在二叉树对照图1所示的二叉排序树，可以给出BST的如下主要特点：

结构上，BST是二叉树
排序性上,对于BST的任意一个节点，节点值大于左子树上的所有节点值，小于右子树上的所有节点值。
从上述BST两条主要的特点可以看出BST是递归定义的，其左子树和右子树均是BST树。了解了BST的基本特点之后，接下来总结BST的插入，删除，建树的基本操作原理。

二丶BST的插入操作

假设待插入数组为： int [] A =new int []{1, 17}，将该数组一次插入到图1所示的二叉排序树中(这次做一个特殊的说明，在插入数据中不存在重复的数据)。

插入元素1，首先和根节点比较，发现1比根节点8小，接着和节点8的左节点比较，发现1还是小于7，接着继续和7的左节点6比较，1小于6，同时节点6左节点为null，不存在比较的可能了，此时节点1充当节点6的左节点，比较的过程和结果如下图所示。

图2元素1的插入过程
在上图2的基础上继续插入元素17，重复和步骤1相同的过程。首先17和根节点9比较，17大于9，所以和节点9的右节点比较，17>15,继续和15的右节点比较发现，17<18,所以17和18的左节点比较，但是发现18的左节点为null，于是17找到了正确的位置，为了18的左节点。比较的过程和结果如下图所示

图3元素17的插入过程

依据上述的两个例子可以清晰的看到BST的插入过的基本实现，下面总结下BST插入过程的特点。

插入过程是一个递归的过程，用递归的过程可以这样描述，如果元素小于根元素，则将元素插入左子树，如果元素大于根元素，则将元素插入右子树，如果子树为null，那么插入元素就是新的子树。利用伪代码可以如下实现。

public Node insert(element t,Node root){
                 if(root==null) new Node(t);
                 if(t<root.element){
                 root.left= insert(t,root.left);
                }else if(t>root.element){
                         root.right =insert(t,root.right);
                }else {
                       //在BST中找到了相等的节点，不做处理直接返回
                        return ;
                }
          }

BST树的插入过程的时间效率取决于查找过程中元素的比较次数，被查找元素的深度越深时间消耗越大，最坏的情况就是插入序列是排序的情况，这样树的深度是N，插入的时间消耗也是O(N)，如果BST的树形是完全二叉树，那么其最大深度就是Log(N)，那么插入序列的时间消耗就是Log(N)。最坏情况和最优情况图下图所示:

图4 最优BST树形结构和最差BST树形

三丶BST树的删除操作

BST树的删除操作相比较于BST树的插入操作，过程很相似，只是稍稍复杂一些，主要是分如下三种情况进行讨论。

被删除元素不存在左儿子和右儿子，其过程如下图所示

图5定位被删除节点
图6 删除节点

在该种情况下被删除元素不存在儿子节点，直接用null代替被删除元素
被删除元素只存在一个儿子，其过程如下图所示
图7定位被删除节点
图8删除节点
在该种情况下，被删除节点只有一个儿子，直接由其儿子节点替代删除节点。
被删除节点有两个儿子，其主要过程如下所示三步完成。
图9 定位被删除节点
图10删除第二步
如图9中所示，定位被删除节点后，如果该节点左右儿子都存在，那么找到该节点右子树中的最小节点，用该最小节点替代被删除节点
图11 删除节点右子树最小节点。
经过图8，图9，图10所表示的不步骤后，元素6被删除了且BST的顺序性并未改变。上述三个步骤的汇总如下图所示
图12 被删除节点具有左儿子和右儿子的删除操作

小小的讨论，当被删除节点没有儿子或者只存在一个儿子时的删除操作不会存在任何疑问，但是当被删除节点存在两个儿子时的删除操作存在一个问题：为了必须用右子树的最小节点来替代，不能用左子树的最大节点来替代吗？答案是可以的，这两种删除的方式随便选择一个。对于一个棵很大BST而言，如果采用右子树的删除操作，经过多次删除操作后，BST的树形可能偏向左，同理相反。
二叉树删除操作是递归的实现，用java可以这样实现。

public Node delete(int element,Node root){
       //未定位到删除元素
       if(root==null) return null;
       intdelta = element-root.element;
       if(delta<0){
           root.left = delete(element,root.left);
       }elseif(delta>0){
           root.right =delete(element,root.right);
       }else{
           if(root.left!=null&&root.right!=null){
              Node node = findMin(root.right);
              root.element =node.element;
              root.right = delete(node.element,root.right);
           }else{
              root = root.left!=null?root.left:root.right;
           }
       }
       returnroot;
    }

四丶二叉树的建树操作。

二叉树的建树操作很容易理解，建立一个N个节点BST操作，就是对元素执行N次的插入操作，每次插入操作的时间复杂度若为理想得Log(N)，那么建树操作的时间复杂度就是Nlog(N)。

五丶BST的应用

BST如其名字可以用来进行排序，利用待排序数组建立一个BST树，假设建立结果如下。中序遍历该数组元素输出就是对数组排序的结果

图13 BST

中序遍历结果： 6->7->8->9->10->12->15->18,建树的时间复杂度是Nlog(N),中序遍历额时间复杂度是N，综合起来该种排序方法时间复杂度是Nlog(N)。
BST树可以用来查找，BST的查找操作就是删除操作中定位操作，时间复杂度是log(N),这里要特别注意，上述的log(N)的时间复杂度是建立在BST具有如图5所示的良好树形结构的前提下。

六丶BST树的java代码实现

 public class BinarySortTree {
    publicNode root = null;
    publicstatic void main(String []args){
       int[] elements = new int[]{5,4,9,3,2};
       BinarySortTree bst = new BinarySortTree();
       /****测试插入，建树和中序遍历操作***/
       bst.buildTree(elements);
       bst.midTrace();
       System.out.println();
       /****测数删除操作之无儿子***************/
    //  bst.delete(9);
    //  bst.midTrace();
       /****测数删除操作之只有一个儿子***************/
    //  bst.delete(4);
    //  bst.midTrace();
       /****测数删除操作只有两个儿子***************/
       bst.delete(5);
       bst.midTrace();
    }
    //节点类型定义
    publicstatic class Node{
       publicint element;
       publicNode left;
       publicNode right;
       publicNode(int element){
           this.element = element;
           left = null;
           right = null;
       }
    }
    //外部使用的插入方法
    publicvoid insert(int element){
       root=insert(element,root);
    }
    //内部使用的插入方法
    private  Node insert(int element,Node root){
       if(root==null)
           return new Node(element);
       intdelta = element-root.element;
       if(delta<0){
           root.left = insert(element,root.left);
       }elseif(delta>0){
           root.right = insert(element,root.right);
       }else{
           //不做处理
       }
       returnroot;
    }
    //外部使用的建树方法
    publicvoid buildTree(int [] elements){
       if(root==null){
           for(int i=0;i<elements.length;i++){
              insert(elements[i]);
           }
       }else{
           //若树以存在，则不能建
       }
    }
    publicvoid delete(int element){
       delete(element,root);
    }
    publicNode delete(int element,Node root){
       //未定位到删除元素
       if(root==null) return null;
       intdelta = element-root.element;
       if(delta<0){
           root.left = delete(element,root.left);
       }elseif(delta>0){
           root.right =delete(element,root.right);
       }else{
           if(root.left!=null&&root.right!=null){
              Node node = findMin(root.right);
              root.element =node.element;
              root.right = delete(node.element,root.right);
           }else{
              root = root.left!=null?root.left:root.right;
           }
       }
       returnroot;
    }
    //中序遍历二叉树
    publicvoid midTrace(){
       if(root!=null){
           print(root);
       }
    }
    privatevoid print(Node node){
       if(node!=null){
           print(node.left);
           System.out.print(node.element+" ");
           print(node.right);
       }
    }
    //找到该节点下子树的最小节点。
    publicNode findMin(Node node){
       if(node.left==null)
           return node;
       else
           return findMin(node.left);
    }
}

Reference:
[1] 数据结构与算法 jaba语言描述版
[2] 原文博客链接