【数据结构】动态查找表 — 二叉排序树的概述和算法分析

发布于：2022-10-15 ⋅ 阅读:(392) ⋅ 点赞:(0)

目录

一、什么是动态表查找？

二、动态查找表的特点

三、二叉排序树

1）概述

2）定义

3）插入：分析

4）插入：算法

5）查找：分析

6）查找：算法

7）删除：分析

8）删除：算法

9）练习

💟 创作不易，不妨点赞💚评论❤️收藏💙一下

一、什么是动态表查找？

动态查找表指在查找过程同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。

动态查找表的表结构本身是在查找过程中动态生成的，即对于给定值key，若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。

动态查找表也即树表的查找，动态查找表的方法是一种以树的形式来组织查找，以实现动态高效效率的查找。

动态查找表的方法有：

  1.  二叉排序树
  2. 平衡二叉树
  3. B树
  4. B+树

二、动态查找表的特点

  • 表结构本身是在查找过程中动态生成的，即对于给定值key，

  • 若表中存在关键字值等于key的记录，则查找成功返回；

  • 否则插入关键字值等于key的记录。

三、二叉排序树

1）概述

  • 二分查找具有最高的查找效率，但是由于二分查找要求表中记录按关键字有序，且不能用链表做存储结构，因此，当表的插入、删除操作非常频繁时，为维护表的有序性，需要移动表中很多记录。这种由移动记录引起的额外时间开销，就会抵消二分查找的优点。

  • 二叉排序树不仅具有二分查找的效率，同时又便于在查找表中进行记录的增加和删除操作。

2）定义

  • 二叉排序树（Binary Sort Tree ）或者是一棵空树，或者是一颗具有下列性质的二叉树：

    1. 若左子树不空，则左子树上所有结点的值均小于根结点的值

    2. 若右子树不空，则右子树上所有结点的值均大于根结点的值

    3. 它的左右子树也都是二叉排序树

相关类：

  • 二叉树结点：

    public class BiTreeNode {
    public Object data;// 结点的数据元素
​
    public BiTreeNode lchild, rchild; // 左右孩子
}

  • 二叉排序树的类结构：

    public class BSTree { //二叉排序树类
​
    public BiTreeNode root;   //根结点
    
    public void inOrderTraverse(BiTreeNode p) { //中根次序遍历以p结点为根的二叉树
        if (p != null) {
            inOrderTraverse(p.lchild);
            // 结点的数据元素存放的是RecordNode
            System.out.print(((RecordNode) p.data).toString() + "");
            inOrderTraverse(p.rchild);
        }
    }
}

3）插入：分析

  • 假设待插入结点的关键字值为key，为了将其插入到表中

  • 先要将它放入二叉排序树中进行查找，

  • 若查找成功，则按二叉排序树定义，待插入结点已存在，不用插入

  • 否则，将新结点插入到表中。因此，新插入的结点一定是作为叶子结点添加到表中去的。

  • 构建一棵二叉排序树是从一棵空树开始逐个插入结点的过程。假设关键字序列为{49, 25, 55, 10, 51, 65}，则构造一棵二叉排序树的过程如下：

4）插入：算法

  • 代码

    //在二叉排序树中插入关键字为Key,数据项为theElement的结点,若插入成功返回true,否则返回false
public boolean insertBST(Comparable key, Object theElement) {
    if (key == null || !(key instanceof Comparable)) {//不能插入空对象或不可比较大小的对象
        return false;
    }
    if (root == null) {
        root = new BiTreeNode(new RecordNode(key, theElement)); //建立根结点
        return true;
    }
    return insertBST(root, key, theElement);
}
​
//将关键字为key,数据项为theElement的结点插入到以p为根的二叉排序树中的递归算法
private boolean insertBST(BiTreeNode p, Comparable key, Object theElement) {
    if (key.compareTo(((RecordNode) p.data).key) == 0) {
        return false;             //不插入关键字重复的结点
    }
    if (key.compareTo(((RecordNode) p.data).key) < 0) {
        if (p.lchild == null) {        //若p的左子树为空
            p.lchild=new BiTreeNode(new RecordNode(key, theElement));  //建立叶子结点作为p的左孩子
            return true;
        } else {                      //若p的左子树非空
            return insertBST(p.lchild, key, theElement);   //插入到p的左子树中
        }
    } else if (p.rchild == null) {    //若p的右子树为空
        p.rchild=new BiTreeNode(new RecordNode(key, theElement));    //建立叶子结点作为p的右孩子
        return true;
    } else {                          //若p的右子树非空
        return insertBST(p.rchild, key, theElement);   //插入到p的右子树中
    }
}
  • 测试
import book.ch07.RecordNode;

public class TestBSTree1_insertBST {
    public static void main(String[] args) {
        int[] k = {49, 12, 65, 8, 35, 88, 5, 10, 15,68};
        BSTree bsTree = new BSTree();
        for (int i = 0; i < k.length; i++) {
            if (bsTree.insertBST(k[i], null)) { //若插入对象成功
                System.out.print("[" + k[i] + "]");
            }
        }
        System.out.println("\n中序遍历二叉排序树：  ");
        bsTree.inOrderTraverse(bsTree.root);
        System.out.println();
​
    }
}

5）查找：分析

  • 若将查找表组织为一棵二叉排序树，则根据二叉排序树的特点，查找过程的主要步骤：

    1. 若查找树为空，则查询失败

    2. 若查找树非空，则：

      1. 若给定值k等于根结点的关键字值，则查找成功，结束查找过程，否则转2

      2. 若给定值k小于根结点的关键字值，则继续在根结点的左子树上进行，否则转3

      3. 若给定值k大于根结点的关键字值，则继续在根结点的右子树上进行。

6）查找：算法

  • 代码

    //查找关键字值为key的结点,若查找成功返回结点值，否则返回null
public Object searchBST(Comparable key) {
    if (key == null || !(key instanceof Comparable)) {
        return null;
    }
    return searchBST(root, key);
}
​
//二叉排序树查找的递归算法
//在二叉排序树中查找关键字为key的结点。若查找成功则返回结点值，否则返回null
private Object searchBST(BiTreeNode p, Comparable key) {
    if (p != null) {
        if (key.compareTo(((RecordNode) p.data).key) == 0) //查找成功
        {
            return p.data;
        }
        //     System.out.print(((RecordNode) p.data).key + "? ");
        if (key.compareTo(((RecordNode) p.data).key) < 0) {
            return searchBST(p.lchild, key);     //在左子树中查找
        } else {
            return searchBST(p.rchild, key);    //在右子树中查找
        }
    }
    return null;
}

  • 测试

    import book.ch07.RecordNode;
​
/**
 * @author 桐叔
 * @email liangtong@itcast.cn
 */
public class TestBSTree2_searchBST {
    public static void main(String[] args) {
        int[] k = {49, 12, 65, 8, 35, 88, 5, 10, 15,68};
        BSTree bsTree = new BSTree();
        for (int i = 0; i < k.length; i++) {
            if (bsTree.insertBST(k[i], null)) { //若插入对象成功
                System.out.print("[" + k[i] + "]");
            }
        }
        System.out.println("\n中序遍历二叉排序树：  ");
        bsTree.inOrderTraverse(bsTree.root);
        System.out.println();
​
        //查找关键字
        RecordNode recordNode1 = (RecordNode) bsTree.searchBST(35);
        System.out.println(recordNode1);
​
        RecordNode recordNode2 = (RecordNode) bsTree.searchBST(36);
        System.out.println(recordNode2);
    }
}
​
//中序遍历二叉排序树：  
//[5,null][8,null][10,null][12,null][15,null][35,null][49,null][65,null][68,null][88,null]
//[35,null]
//null

7）删除：分析

  • 从二叉排序树中删除一个结点，要保证删除后仍然是一棵二叉排序树。根据二叉排序树的结构特征，删除操作可以分4种情况

  • 情况1：若待删除的结点是叶子结点，则直接删除该结点即可。若该结点同时也是根节点，则删除后二叉排序树将变为空树。

  • 情况2：若待删除的结点只有左子树，而无右子树。根据二叉排序树的特点，—《可以直接将其左子树的根结点代替被删除结点的位置—》，即若被删除的结点为其双亲结点的左孩子，则将被删除结点的唯一左孩子收为其双亲结点的左孩子；否则收为其双亲节点的右孩子。

  • 情况3：待删除的结点只有右子树，而无左子树。—《可以直接将其右子树的根结点替代被删除结点的位置—》，即若被删除的结点为其双亲结点的左孩子，则将被删除结点的唯一右孩子收为其双亲结点的左孩子；否则收为其双亲结点的右孩子。

  • 情况4：待删除结点既有左子树又有右子树。根据二叉排序树的特点，可以用被删除结点在中序遍历序列下的前驱结点（或其中序遍历序列下的后继结点）代替被删除结点，同时删除其中序遍历序列下的前驱结点（或其中序遍历序列下的后继结点）。而被删除结点在中序遍历下的前驱无右子树，被删除结点在中序遍历下的后继无左子树，因而问题转换为第2种情况或第3种情况。

     方式1：前驱结点：左子树的最右的结点

     方式2：后继结点：右子树的最左的结点

8）删除：算法

  • 代码

    //二叉排序树中删除结点算法。若删除成功返回删除结点值，否则返回null
public Object removeBST(Comparable key) {
    if (root == null || key == null || !(key instanceof Comparable)) {
        return null;
    }
    //在以root为根的二叉排序树中删除关键字为elemKey的结点
    return removeBST(root, key, null);
}
​
//在以p为根的二叉排序树中删除关键字为elemKey的结点。parent是p的父结点，递归算法
private Object removeBST(BiTreeNode p, Comparable elemKey, BiTreeNode parent) {
    if (p != null) {
        if (elemKey.compareTo(((RecordNode) p.data).key) < 0) { //在左子树中删除
            return removeBST(p.lchild, elemKey, p);    //在左子树中递归搜索
        } else if (elemKey.compareTo(((RecordNode) p.data).key) > 0) { //在右子树中删除
            return removeBST(p.rchild, elemKey, p);    //在右子树中递归搜索
        } else if (p.lchild != null && p.rchild != null) {
            //相等且该结点有左右子树
            BiTreeNode innext = p.rchild;    //寻找p在中根次序下的后继结点innext
            while (innext.lchild != null) { //即寻找右子树中的最左孩子
                innext = innext.lchild;
            }
            p.data=innext.data;              //以后继结点值替换p
            return removeBST(p.rchild, ((RecordNode) p.data).key, p); //递归删除结点p
        } else {//p是1度和叶子结点
            if (parent == null) {  //删除根结点，即p==root
                if (p.lchild != null) {
                    root = p.lchild;
                } else {
                    root = p.rchild;
                }
                return p.data;       //返回删除结点p值
            }
            if (p == parent.lchild) { //p是parent的左孩子
                if (p.lchild != null) {
                    parent.lchild=p.lchild;  //以p的左子树填补
                } else {
                    parent.lchild=p.rchild;
                }
            } else if (p.lchild != null) { //p是parent的右孩子且p的左子树非空
                parent.rchild=p.lchild;
            } else {
                parent.rchild=p.rchild;
            }
            return p.data;
        }
    }
    return null;
}

  • 测试

    import book.ch07.RecordNode;
​
/**
 * @author 桐叔
 * @email liangtong@itcast.cn
 */
public class TestBSTree3_removeBST {
    public static void main(String[] args) {
        int[] k = {49, 12, 65, 8, 35, 88, 5, 10, 15,68};
        BSTree bsTree = new BSTree();
        for (int i = 0; i < k.length; i++) {
            if (bsTree.insertBST(k[i], null)) { //若插入对象成功
                System.out.print("[" + k[i] + "]");
            }
        }
        System.out.println("\n中序遍历二叉排序树：  ");
        bsTree.inOrderTraverse(bsTree.root);
        System.out.println();
​
        RecordNode recordNode = (RecordNode)bsTree.removeBST(12);
        System.out.println(recordNode);
​
        bsTree.inOrderTraverse(bsTree.root);
    }
}
​

9）练习

50、40、60、35、25、45、70、80

要求1：绘制二叉排序树（绘图）

要求2：查询25，书写查询路径

要求3：重新开始，删除结点40后，二叉排序树（绘图）

要求4：重新开始，删除结点35后，二叉排序树（绘图）

要求5：重新开始，删除结点60后，二叉排序树（绘图）

要求2：查询25，书写查询路径：
50 --> 40 --> 35 --> 25

写到最后

四季轮换，已经数不清凋零了多少， 愿我们往后能向心而行，一路招摇胜！

🐋 你的支持认可是我创作的动力

💟 创作不易，不妨点赞💚评论❤️收藏💙一下

😘 感谢大佬们的支持，欢迎各位前来不吝赐教

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布