澳门新葡亰平台游戏网站数据结构 – 树 – 二叉查找树 – Binary Search Tree

澳门新葡亰平台游戏网站 13

二叉查找树可以递归地定义如下,二叉查找树或者是空二叉树,或者是满足下列性质的二叉树:

1 概念

   
  又称二叉查找树,简称BST。具有以下性质的二叉树:

      (1)
若左子树非空,则左子树上所有结点值均小于根结点的值

      (2)
若右子树非空,则右子树上所有结点值均大于根结点的值

      (3)
左,右子树本身也分别是一棵二叉排序树

   
  也是一个递归的数据结构。下图是一个二叉排序树。

 澳门新葡亰平台游戏网站 1

   
  对其进行中序遍历得到一个递增的有序序列,如上图的中序序列为2,4,5,6,7,8,9,10,11,14。

1. 概念

二叉查找树(Binary Search Tree)也称有序二叉树(Ordered Binary Tree)、排序二叉树(Sorted Binary Tree)。

二叉查找树是java的 TreeSetTreeMap 类实现的基础。

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为O(log
n)。

(1)若它的左子树不为空,则其左子树上任意结点的关键字的值都小于根结点关键字的值。

2 二叉排序树的插入

     
二叉排序树是一种动态的集合,插入结点的过程为,结点值小于根结点值,插入到左子树中,若大于根结点值,则插入到右子树中。插入的新结点一定是某个叶结点

/**
 * 在二叉排序树node中插入一个值为info的结点
 * @param node 二叉排序树
 * @param info 待插入结点值
 * @return
 */
public Node insert(Node node, Integer info){
    if(node == null){
        node = new Node();
        node.data = info;
    }
    if(info < node.data){
        node.lchild = insert(node.lchild, info);
    } else if(info > node.data){
        node.rchild = insert(node.rchild, info);
    } else { }
    return node;
}

2. 特点

  • 若任意结点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;

  • 若任意结点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;

  • 任意结点的左、右子树也分别为二叉查找树。

  • 没有键值相等的结点(no duplicate nodes)。

(2)若它的右子树不为空,则其右子树上任意结点的关键字的值都大于根节点关键字的值。

3 二叉排序树的查找

   
  从根结点开始,若给定值等于根结点值,则查找成功;若小于根结点值,在左子树中查找,否则在右子树中查找。可分为递归和非递归实现。

3. 实现

由于二叉查找树要求所有的节点都可以进行排序.所以编写时代码时需要一个
Comparable 泛型接口。

由于树的递归定义,二叉查找树的代码实现也基本上都是使用递归的函数,

(3)它的左、右子树本身又是一个二叉查找树。

3.1 递归实现

/**
 * 二叉排序树,查找,递归实现
 * @param root
 * @param inte
 * @return -1 不存在 1 存在
 */
public int searchRecur(Node root, Integer inte){
    if(root!= null){
        if(inte == root.data ){
            return 1;
        } else if(inte < root.data){
            return searchRecur(root.lchild, inte);
        } else if(inte > root.data){
            return  searchRecur(root.rchild, inte);
        } 
    }
    return -1;
}

3.1 继承关系

public class BinarySearchTree<T extends Comparable<T>> 

澳门新葡亰平台游戏网站 2

3.2 非递归实现

/**
 * 查找, 非递归实现
 * @return -1 不能存在  1 存在
 */
public int search(Node root, Integer inte){
    while(root != null && inte != root.data){
        if(inte < root.data){
            root = root.lchild;
        } else {
            root = root.rchild;
        }
    }
    return root == null ? -1 : 1;
}

3.2 定义节点

private static class TreeNode<T> {

    T data;

    TreeNode<T> left;

    TreeNode<T> right;

    public TreeNode(T data) {
        this.data = data;
    }
}

从性能上来说如果二叉查找树的所有非叶子结点的左右子树的结点数目均保持差不多(平衡),那么二叉查找树的搜索性能逼近二分查找;但它比连续内存空间的二分查找的优点是,改变二叉查找树结构(插入与删除结点)不需要移动大段的内存数据,甚至通常是常数开销。二叉查找树可以表示按顺序序列排列的数据集合,因此二叉查找树也被称为二叉排序树,并且同一个数据集合可以表示为不同的二叉查找树。二叉查找树的结点的数据结构定义为:

4 二叉排序树的构造

   
  依次输入数据元素,插入到合适的位置上,具体的过程是,每读入一个元素,建立一个新结点,若新结点值小于根结点值,则插入到左子树中,否则插入到右子树中。

public class BST {
    Node root;
    int n=1; // 结点总数
    private class Node{
        Integer data;
        Node lchild, rchild;
    }
    public BST(){
        build(); // 递归构造
        System.out.println("根结点:" + root.data);
        btDepth();
    }
    /**
     * 构造一棵二叉排序树
     */
    public void build(){
//        Integer[] ins = new Integer[] { 8, 4, 9, 2, 7, 5, 6 };
        Integer[] ins = new Integer[] { 8, 4, 2, 7, 5, 6, 16, 10, 9, 14, 15, 11, 12};
        root = new Node();
        root.data = ins[0];
        for (int i = 1; i < ins.length; i++) {
            insert(root, ins[i]);
            n++;
        }
    }
}

3.3 属性

//根节点
private TreeNode<T> root;
struct celltype{

    records data; 

    celltype * lchild, * rchild;

}

typedef celltype * BST;

5 二叉排序树的删除

   
  删除一个结点时,必须保证二叉排序树的性质不会丢失。删除操作的实现过程按3种情况来处理:

      (1)若删除的结点 n
是叶子结点,则直接删除,不会破坏二叉排序树性质;

      (2)若删除的结点 n
只有一棵左子树或者右子树,则使用左或右子女替换;

      (3)若删除的结点 n
左右子树均不空,则令n的直接后继(或直接前驱)替代n,然后删除这个直接后继(或前驱)。

/**
 * 先找到该结点及其双亲结点,然后根据规则删除
 * @param root 根节点
 * @param del 待删除结点值
 * @return -1结点不存在  1删除成功
 */
public int delete(Node root, Integer del){
    Node pre = null; // 待删除结点的双亲结点
    /*
     * 首先找到该结点
     */
    while(root != null && del != root.data){
        pre = root;
        if(del < root.data){
            root = root.lchild;
        } else {
            root = root.rchild;
        }
    }
    if(root == null){ // 若不存在 直接返回
        return -1;
    }
    delete(root, pre);
    return 1;
}
/**
 * 删除结点有三种情况
 * <ul>
 * <li> 若删除的结点 n 是叶子结点,则直接删除;
 * <li> 若删除的结点 n 只有一棵左子树或者右子树,则使用左或右子女替换;
 * <li> 若删除的结点 n 左右子树均不空,则令n的直接后继(或直接前驱)替代n,然后删除这个直接后继(或前驱)
 * <p> 这里的直接前驱和后继是针对中序遍历的顺序而言
 * <ul/>
 * @param node 待删除结点
 * @param pre 其双亲结点
 */
private void delete(Node node, Node pre) {
    Node tmp = null;
    if(node.lchild == null && node.rchild == null){ // 叶子结点
        tmp = null;
    } else if (node.lchild == null) { // 左孩子为空,直接用右孩子替代
        tmp = node.rchild;
    } else if (node.rchild == null) { // 右孩子为空,直接用左孩子替代
        tmp = node.lchild;
    } else { // 左右子树均不为空, 使用中序遍历的直接后继替代
        Node preNode = null// 右子树中序遍历的第一个结点的双亲结点
             ,lnode = node.rchild; // 查找其右子树 中序遍历的第一个结点,其没有左孩子
        while(lnode.lchild != null){
            preNode = lnode;
            lnode = lnode.lchild;
        }
        node.data = lnode.data; // 交换值
        preNode.lchild = lnode.rchild; // 直接删除
        tmp = node;
    }

    if(pre.lchild == node){
        pre.lchild = tmp;
    } else {
        pre.rchild = tmp;
    }
}

3.5 插入 void insert(T data)

public void insert(T data) {
    root = insert(data, root);
}

private TreeNode<T> insert(T data, TreeNode<T> node) {
    if (node == null) {
        return new TreeNode<T>(data);
    }
    int result = node.data.compareTo(data);
    if (result == 0) {
        throw new IllegalArgumentException("has the same data :" + data.toString());
    }
    if (result > 0) {
        node.left = insert(data, node.left);
    } else if (result < 0) {
        node.right = insert(data, node.right);
    }
    return node;
}

澳门新葡亰平台游戏网站 3

在Java中,节点的数据结构定义如下:

6 二叉排序树的查找效率分析

   
  对于高度为H的二叉排序树,其插入和删除的运行时间都是O(H)。但在最坏的情况下,即构造二叉排序树的输入序列是有序的,就会形成一个倾斜的单枝树,此时二叉排序树性能显著变坏,树的高度也增加为元素个数N。

   
  分析之前了解一下平均查找长度的概念。

   
  为确定记录在查找表中的位置,与给定值进行比较的关键字的个数期望值称为查找算法在查找成功时的平均查找长度(ASL)。对于含有n个元素的查找表,查找成功的平均查找长度为:

澳门新葡亰平台游戏网站 4 

   
  其中Pi为查找表中第i个元素的概率,Ci为找到第i个元素已经比较过的次数。

   
  在查找表中找不到待查元素,但是找到待查元素应该在表中存在的位置的平均查找次数称为查找不成功的平均查找长度。

澳门新葡亰平台游戏网站 5

   
  其中元素旁边的数字为查找成功时,比较的次数。

   
  在等概率的情况下,图2(a)的查找成功的平均查找长度为(概率乘以关键字所在层数之和):

ASLa =
(1+2+2+3+3+3+3+4+4+4)/10 = 2.9

而图2(b)的查找成功的平均查找长度

ASLb=(1+2+3+4+5+6+7+8+9+10)/10=5.5

   
  查找失败的平均长度:图a中那些虚线框的元素表示不存在的结点,即是查找失败的点,其查找路径为从根节点到其父节点的结点序列,所以查找失败的平均长度为:

ASLa=(5*3+6*4)/11=3.5

   
  由上可知,二叉排序树查找算法的平均查找长度,主要取决于树的高度,与二叉树的形态有关。若二叉排序树是一个只有右(左)孩子的单枝树(类似于有序单链表),其平均查找长度和单链表相同,为O(n);若左右子树的高度差不超过1,即是平衡二叉树,其平均查找长度为O(log2n)。

   
  二叉排序树与二分查找相似,就平均性能而言,它俩差不多,但二分查找的判定树唯一,而二叉排序树不唯一,不同的输入顺序,可能得到不同的二叉排序树。如上图。

   
  针对维护表的有序性,二叉排序树无需移动结点,只需修改指针完成插入和删除,平均执行时间为O(log2n)。二分查找的对象是有序顺序表,插入和删除代价为O(n)。所以,若是静态查找表,宜用顺序表存储结构,用二分查找;若是动态查找表,则选择二叉排序树作为其逻辑结构。

 

3.6 查找最小值 T min()

public T min() {
    TreeNode<T> node = min(root);
    return node == null ? null : node.data;
}

private TreeNode<T> min(TreeNode<T> node) {
    if (node == null) {
        return null;
    }
    if (node.left == null) {
        return node;
    }
    return min(node.left);
}
package wx.algorithm.search.bst;

/**

 * Created by apple on 16/7/29.

 */

/**

 * @function 二叉搜索树中的节点

 */

public class Node {

    //存放节点数据

    int data;

    //指向左子节点

    Node left;

    //指向右子节点

    Node right;

    /**

     * @function 默认构造函数

     * @param data 节点数据

     */

    public Node(int data) {

        this.data = data;

        left = null;

        right = null;

    }

}

3.7 查找最大值 T max()

public T max() {
    TreeNode<T> node = max(root);
    return node == null ? null : node.data;
}

private TreeNode<T> max(TreeNode<T> node) {
    if (node == null) {
        return null;
    }
    if (node.right == null) {
        return node;
    }
    return max(node.right);
}

查找

而二叉查找树的查找过程为从根结点开始,如果查询的关键字与结点的关键字相等,那么就命中;否则,如果查询关键字比结点关键字小,就进入左儿子;如果比结点关键字大,就进入右儿子;如果左儿子或右儿子的指针为空,则报告找不到相应的关键字。

澳门新葡亰平台游戏网站 6

BST Search(keytype k, BST F){

    //在F所指的二叉查找树中查找关键字为k的记录。若成功,则返回响应结点的指针,否则返回空

    if(F == NULL) //查找失败

        return NULL;

    else if(k == F -> data.key){ //查找成功

        return F;

    }

    else if (k < F -> data.key){ //查找左子树

        return Search(k,F -> lchild);    

    }

    else if (k > F -> data.key){ //查找右子树

        return Search(k,F -> rchild);

    }

}

3.8 是否包含元素 boolean contains(T data)

public boolean contains(T data) {
    return contains(data, root);
}

public boolean contains(T data, TreeNode<T> node) {
    if (node == null) {
        return false;
    }
    int result = node.data.compareTo(data);
    if (result > 0) {
        return contains(data, node.left);
    } else if (result < 0) {
        return contains(data, node.right);
    }
    return true;
}

澳门新葡亰平台游戏网站 7

插入

把一个新的记录R插入到二叉查找树,应该保证在插入之后不破坏二叉查找树的结构性质。因此,为了执行插入操作首先应该查找R所在的位置。查找时,仍然采用上述的递归算法。若查找失败,则把包含R的结点插在具有空子树位置,若查找成功,则不执行插入,操作结束。

澳门新葡亰平台游戏网站 8

void Insert(records R, BST &F){

        //在F所指的二叉查找树中插入一个新纪录R

        if(F == NULL){

             F = new celltype;

             F -> data = R;

             F -> lchild = NULL;

             F -> rchild = NULL;

        }

        else if (R.key < F -> data.key){

             Insert(R,F -> lchild);

            }else if(R.key > F -> data.key){

             Insert(R,F -> rchild);

        }

        //如果 R.key == F -> data.key 则返回

    }

3.9 删除元素 void remove(T data)

在二叉查找树种,删除是最复杂的实现。涉及三种情况:

  • 被删除节点是树叶节点(没有子树):最简单,直接删除,将该节点置为null即可

  • 被删除节点有一个子节点(左子树或右子树):是该节点的父节点指向该节点的子节点(左或右).
    见图1

  • 被删除节点有两个子节点:用其右子树中的最小值代替该节点上的值,删除其右子树上的最小值.
    见图2

public void remove(T data) {
    remove(data, root);
}

public TreeNode<T> remove(T data, TreeNode<T> node) {
    if (data == null) {
        return null;
    }
    int result = node.data.compareTo(data);
    if (result > 0) {
        node.left = remove(data, node.left);
    } else if (result < 0) {
        node.right = remove(data, node.right);
    } else {
        //如果被删除节点有两个儿子
        if (node.left != null && node.right != null) { 
            TreeNode<T> minRight = find(node.right, true);
            node.data = minRight.data; // 当前节点值被其右子树的最小值代替
            node.right = remove(minRight.data, node.right); // 将右子树的最小值删除
        } else if (node.left == null && node.right == null) {
            node = null; // 如果被删除的节点只是一个叶子
        } else if (node.left == null || node.right == null) { // 如果被删除节点只有一个儿子
            node = (node.left != null) ? node.left : node.right;
        }
    }
    return node;
}

澳门新葡亰平台游戏网站 9

删除

删除叶节点

澳门新葡亰平台游戏网站 10

删除只有一个子节点的内部节点

澳门新葡亰平台游戏网站 11

删除有两个子节点的内部节点

如果我们进行简单的替换,那么可能碰到如下情况:

澳门新葡亰平台游戏网站 12

因此我们要在子树中选择一个合适的替换节点,替换节点一般来说会是右子树中的最小的节点:

澳门新葡亰平台游戏网站 13

Java 实现

BinarySearchTree的Java版本代码参考BinarySearchTree:

package wx.algorithm.search.bst;

/**
 * Created by apple on 16/7/29.
 */

/**
 * @function 二叉搜索树的示范代码
 */
public class BinarySearchTree {

    //指向二叉搜索树的根节点
    private Node root;

    //默认构造函数
    public BinarySearchTree() {
        this.root = null;
    }

    /**
     * @param id 待查找的值
     * @return
     * @function 默认搜索函数
     */
    public boolean find(int id) {

        //从根节点开始查询
        Node current = root;

        //当节点不为空
        while (current != null) {

            //是否已经查询到
            if (current.data == id) {
                return true;
            } else if (current.data > id) {
                //查询左子树
                current = current.left;
            } else {
                //查询右子树
                current = current.right;
            }
        }
        return false;
    }

    /**
     * @param id
     * @function 插入某个节点
     */
    public void insert(int id) {

        //创建一个新的节点
        Node newNode = new Node(id);

        //判断根节点是否为空
        if (root == null) {
            root = newNode;
            return;
        }

        //设置current指针指向当前根节点
        Node current = root;

        //设置父节点为空
        Node parent = null;

        //遍历直到找到第一个插入点
        while (true) {

            //先将父节点设置为当前节点
            parent = current;

            //如果小于当前节点的值
            if (id < current.data) {

                //移向左节点
                current = current.left;

                //如果当前节点不为空,则继续向下一层搜索
                if (current == null) {
                    parent.left = newNode;
                    return;
                }
            } else {

                //否则移向右节点
                current = current.right;

                //如果当前节点不为空,则继续向下一层搜索
                if (current == null) {
                    parent.right = newNode;
                    return;
                }
            }
        }
    }

    /**
     * @param id
     * @return
     * @function 删除树中的某个元素
     */
    public boolean delete(int id) {

        Node parent = root;
        Node current = root;

        //记录被找到的节点是父节点的左子节点还是右子节点
        boolean isLeftChild = false;

        //循环直到找到目标节点的位置,否则报错
        while (current.data != id) {
            parent = current;
            if (current.data > id) {
                isLeftChild = true;
                current = current.left;
            } else {
                isLeftChild = false;
                current = current.right;
            }
            if (current == null) {
                return false;
            }
        }

        //如果待删除的节点没有任何子节点
        //直接将该节点的原本指向该节点的指针设置为null
        if (current.left == null && current.right == null) {
            if (current == root) {
                root = null;
            }
            if (isLeftChild == true) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        }

        //如果待删除的节点有一个子节点,且其为左子节点
        else if (current.right == null) {

            //判断当前节点是否为根节点
            if (current == root) {
                root = current.left;
            } else if (isLeftChild) {

                //挂载到父节点的左子树
                parent.left = current.left;
            } else {

                //挂载到父节点的右子树
                parent.right = current.left;
            }
        } else if (current.left == null) {
            if (current == root) {
                root = current.right;
            } else if (isLeftChild) {
                parent.left = current.right;
            } else {
                parent.right = current.right;
            }
        }

        //如果待删除的节点有两个子节点
        else if (current.left != null && current.right != null) {

            //寻找右子树中的最小值
            Node successor = getSuccessor(current);
            if (current == root) {
                root = successor;
            } else if (isLeftChild) {
                parent.left = successor;
            } else {
                parent.right = successor;
            }
            successor.left = current.left;
        }
        return true;
    }

    /**
     * @param deleleNode
     * @return
     * @function 在树种查找最合适的节点
     */
    private Node getSuccessor(Node deleleNode) {
        Node successsor = null;
        Node successsorParent = null;
        Node current = deleleNode.right;
        while (current != null) {
            successsorParent = successsor;
            successsor = current;
            current = current.left;
        }
        if (successsor != deleleNode.right) {
            successsorParent.left = successsor.right;
            successsor.right = deleleNode.right;
        }
        return successsor;
    }

    /**
     * @function 以中根顺序遍历树
     */
    public void display() {
        display(root);
    }

    private void display(Node node) {

        //判断当前节点是否为空
        if (node != null) {

            //首先展示左子树
            display(node.left);

            //然后展示当前根节点的值
            System.out.print(" " + node.data);

            //最后展示右子树的值
            display(node.right);
        }
    }

}

测试函数:

package wx.algorithm.search.bst;

import org.junit.Before;
import org.junit.Test;

/**
 * Created by apple on 16/7/30.
 */
public class BinarySearchTreeTest {

    BinarySearchTree binarySearchTree;

    @Before
    public void setUp() {
        binarySearchTree = new BinarySearchTree();
        binarySearchTree.insert(3);
        binarySearchTree.insert(8);
        binarySearchTree.insert(1);
        binarySearchTree.insert(4);
        binarySearchTree.insert(6);
        binarySearchTree.insert(2);
        binarySearchTree.insert(10);
        binarySearchTree.insert(9);
        binarySearchTree.insert(20);
        binarySearchTree.insert(25);
        binarySearchTree.insert(15);
        binarySearchTree.insert(16);
        System.out.println("原始的树 : ");
        binarySearchTree.display();
        System.out.println("");

    }

    @Test
    public void testFind() {

        System.out.println("判断4是否存在树中 : " + binarySearchTree.find(4));

    }

    @Test
    public void testInsert() {

    }

    @Test
    public void testDelete() {

        System.out.println("删除值为2的节点 : " + binarySearchTree.delete(2));
        binarySearchTree.display();

        System.out.println("n 删除有一个子节点值为4的节点 : " + binarySearchTree.delete(4));
        binarySearchTree.display();

        System.out.println("n 删除有两个子节点的值为10的节点 : " + binarySearchTree.delete(10));
        binarySearchTree.display();

    }

}
You can leave a response, or trackback from your own site.

Leave a Reply

网站地图xml地图