Java深入了解数据结构之二叉搜索树增 插 删 创详解

目录
  • ①概念
  • ②操作-查找
  • ③操作-插入
  • ④操作-删除
    • 1. cur.left == null
    • 2. cur.right == null
    • 3. cur.left != null && cur.right != null
  • ⑤性能分析
  • ⑥完整代码

①概念

二叉搜索树又称二叉排序树,它或者是一棵空树**,或者是具有以下性质的二叉树:

若它的左子树不为空,则左子树上所有节点的值都小于根节点的值

若它的右子树不为空,则右子树上所有节点的值都大于根节点的值

它的左右子树也分别为二叉搜索树

②操作-查找

二叉搜索树的查找类似于二分法查找

public Node search(int key) {
        Node cur = root;
        while (cur != null) {
            if(cur.val == key) {
                return cur;
            }else if(cur.val < key) {
                cur = cur.right;
            }else {
                cur = cur.left;
            }
        }
        return null;
    }

③操作-插入

  public boolean insert(int key) {
        Node node = new Node(key);
        if(root == null) {
            root = node;
            return true;
        }

        Node cur = root;
        Node parent = null;

        while(cur != null) {
            if(cur.val == key) {
                return false;
            }else if(cur.val < key) {
                parent = cur;
                cur = cur.right;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
        //parent
        if(parent.val > key) {
            parent.left = node;
        }else {
            parent.right = node;
        }

        return true;
    }

④操作-删除

删除操作较为复杂,但理解了其原理还是比较容易

设待删除结点为 cur, 待删除结点的双亲结点为 parent

1. cur.left == null

1. cur 是 root,则 root = cur.right

2. cur 不是 root,cur 是 parent.left,则 parent.left = cur.right

3. cur 不是 root,cur 是 parent.right,则 parent.right = cur.right

2. cur.right == null

1. cur 是 root,则 root = cur.left

2. cur 不是 root,cur 是 parent.left,则 parent.left = cur.left

3. cur 不是 root,cur 是 parent.right,则 parent.right = cur.left

第二种情况和第一种情况相同,只是方向相反,这里不再画图

3. cur.left != null && cur.right != null

需要使用替换法进行删除,即在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删除节点中,再来处理该结点的删除问题

当我们在左右子树都不为空的情况下进行删除,删除该节点会破坏树的结构,因此用替罪羊的方法来解决,实际删除的过程还是上面的两种情况,这里还是用到了搜索二叉树的性质

public void remove(Node parent,Node cur) {
        if(cur.left == null) {
            if(cur == root) {
                root = cur.right;
            }else if(cur == parent.left) {
                parent.left = cur.right;
            }else {
                parent.right = cur.right;
            }
        }else if(cur.right == null) {
            if(cur == root) {
                root = cur.left;
            }else if(cur == parent.left) {
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }
        }else {
            Node targetParent =  cur;
            Node target = cur.right;
            while (target.left != null) {
                targetParent = target;
                target = target.left;
            }
            cur.val = target.val;
            if(target == targetParent.left) {
                targetParent.left = target.right;
            }else {
                targetParent.right = target.right;
            }
        }
    }

  public void removeKey(int key) {
        if(root == null) {
            return;
        }
        Node cur = root;
        Node parent = null;
        while (cur != null) {
            if(cur.val == key) {
                remove(parent,cur);
                return;
            }else if(cur.val < key){
                parent = cur;
                cur = cur.right;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
    }

⑤性能分析

插入和删除操作都必须先查找,查找效率代表了二叉搜索树中各个操作的性能。

对有n个结点的二叉搜索树,若每个元素查找的概率相等,则二叉搜索树平均查找长度是结点在二叉搜索树的深度 的函数,即结点越深,则比较次数越多。

但对于同一个关键码集合,如果各关键码插入的次序不同,可能得到不同结构的二叉搜索树:

最优情况下,二叉搜索树为完全二叉树,其平均比较次数为:

最差情况下,二叉搜索树退化为单支树,其平均比较次数为:

⑥完整代码

public class TextDemo {

    public static class Node {
        public int val;
        public Node left;
        public Node right;

        public Node (int val) {
            this.val = val;
        }
    }

    public Node root;

    /**
     * 查找
     * @param key
     */
    public Node search(int key) {
        Node cur = root;
        while (cur != null) {
            if(cur.val == key) {
                return cur;
            }else if(cur.val < key) {
                cur = cur.right;
            }else {
                cur = cur.left;
            }
        }
        return null;
    }

    /**
     *
     * @param key
     * @return
     */
    public boolean insert(int key) {
        Node node = new Node(key);
        if(root == null) {
            root = node;
            return true;
        }

        Node cur = root;
        Node parent = null;

        while(cur != null) {
            if(cur.val == key) {
                return false;
            }else if(cur.val < key) {
                parent = cur;
                cur = cur.right;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
        //parent
        if(parent.val > key) {
            parent.left = node;
        }else {
            parent.right = node;
        }

        return true;
    }

    public void remove(Node parent,Node cur) {
        if(cur.left == null) {
            if(cur == root) {
                root = cur.right;
            }else if(cur == parent.left) {
                parent.left = cur.right;
            }else {
                parent.right = cur.right;
            }
        }else if(cur.right == null) {
            if(cur == root) {
                root = cur.left;
            }else if(cur == parent.left) {
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }
        }else {
            Node targetParent =  cur;
            Node target = cur.right;
            while (target.left != null) {
                targetParent = target;
                target = target.left;
            }
            cur.val = target.val;
            if(target == targetParent.left) {
                targetParent.left = target.right;
            }else {
                targetParent.right = target.right;
            }
        }
    }

    public void removeKey(int key) {
        if(root == null) {
            return;
        }
        Node cur = root;
        Node parent = null;
        while (cur != null) {
            if(cur.val == key) {
                remove(parent,cur);
                return;
            }else if(cur.val < key){
                parent = cur;
                cur = cur.right;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
    }

}

到此这篇关于Java深入了解数据结构之二叉搜索树增 插 删 创详解的文章就介绍到这了,更多相关Java 二叉搜索树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • java实现 二叉搜索树功能

    一.概念 二叉搜索树也成二叉排序树,它有这么一个特点,某个节点,若其有两个子节点,则一定满足,左子节点值一定小于该节点值,右子节点值一定大于该节点值,对于非基本类型的比较,可以实现Comparator接口,在本文中为了方便,采用了int类型数据进行操作. 要想实现一颗二叉树,肯定得从它的增加说起,只有把树构建出来了,才能使用其他操作. 二.二叉搜索树构建 谈起二叉树的增加,肯定先得构建一个表示节点的类,该节点的类,有这么几个属性,节点的值,节点的父节点.左节点.右节点这四个属性,代码如下 sta

  • 利用java实现二叉搜索树

    二叉搜索树的定义 它是一颗二叉树 任一节点的左子树上的所有节点的值一定小于该节点的值 任一节点的右子树上的所有节点的值一定大于该节点的值 特点: 二叉搜索树的中序遍历结果是有序的(升序)! 实现一颗二叉搜索树 实现二叉搜索树,将实现插入,删除,查找三个方面 二叉搜索树的节点是不可以进行修改的,如果修改,则可能会导致搜索树的错误 二叉搜索树的定义类 二叉搜索树的节点类 -- class Node 二叉搜索树的属性:要找到一颗二叉搜索树只需要知道这颗树的根节点. public class BST {

  • Java基础之二叉搜索树的基本操作

    一.二叉搜索树插入元素 /** * user:ypc: * date:2021-05-18; * time: 15:09; */ class Node { int val; Node left; Node right; Node(int val) { this.val = val; } } public void insert(int key) { Node node = new Node(key); if (this.root == null) { root = node; } Node cu

  • Java二叉搜索树基础原理与实现方法详解

    本文实例讲述了Java二叉搜索树基础原理与实现方法.分享给大家供大家参考,具体如下: 前言:本文通过先通过了解一些二叉树基础知识,然后在转向学习二分搜索树. 1 树 1.1 树的定义 树(Tree)是n(n>=0)个节点的有限集.n=0时称为空树.在任意一颗非空树中: (1)有且仅有一个特定的称为根(Root)的节点: (2)当n>1时,其余节点可分为m(m>0)个互不相交的有限集T1.T2........Tn,其中每一个集合本身又是一棵树,并且称为根的子树. 此外,树的定义还需要强调以

  • Java底层基于二叉搜索树实现集合和映射/集合Set功能详解

    本文实例讲述了Java底层基于二叉搜索树实现集合和映射功能.分享给大家供大家参考,具体如下: 前言:在第5章的系列学习中,已经实现了关于二叉搜索树的相关操作,详情查看第5章即可.在本节中着重学习使用底层是我们已经封装好的二叉搜索树相关操作来实现一个基本的集合(set)这种数据结构. 集合set的特性: 集合Set存储的元素是无序的.不可重复的.为了能达到这种特性就需要寻找可以作为支撑的底层数据结构. 这里选用之前自己实现的二叉搜索树,这是由于该二叉树是不能盛放重复元素的.因此我们可以使用二叉搜索

  • Java二叉搜索树遍历操作详解【前序、中序、后序、层次、广度优先遍历】

    本文实例讲述了Java二叉搜索树遍历操作.分享给大家供大家参考,具体如下: 前言:在上一节Java二叉搜索树基础中,我们对树及其相关知识做了了解,对二叉搜索树做了基本的实现,下面我们继续完善我们的二叉搜索树. 对于二叉树,有深度遍历和广度遍历,深度遍历有前序.中序以及后序三种遍历方法,广度遍历即我们寻常所说的层次遍历,如图: 因为树的定义本身就是递归定义,所以对于前序.中序以及后序这三种遍历我们使用递归的方法实现,而对于广度优先遍历需要选择其他数据结构实现,本例中我们使用队列来实现广度优先遍历.

  • Java实现二叉搜索树的插入、删除功能

    二叉树的结构 public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() { } TreeNode(int val) { this.val = val; } } 中序遍历 中序遍历:从根节点开始遍历,遍历顺序是:左子树->当前节点->右子树,在中序遍历中,对每个节点来说: 只有当它的左子树都被遍历过了(或者没有左子树),它才会被遍历到.在遍历右子树之前,一定会先遍历当前节点. 中序遍历得到的第一个节点是没

  • Java删除二叉搜索树最大元素和最小元素的方法详解

    本文实例讲述了Java删除二叉搜索树最大元素和最小元素的方法.分享给大家供大家参考,具体如下: 在前面一篇<Java二叉搜索树遍历操作>中完成了树的遍历,这一节中将对如何从二叉搜索树中删除最大元素和最小元素做介绍: 我们要想删除二分搜索树的最小值和最大值,就需要先找到二分搜索树的最小值和最大值,其实也还是很容易的,因为根据二叉搜索树的特点,它的左子树一定比当前节点要小,所以二叉搜索树的最小值一定是左子树一直往下走,一直走到底.同样在二叉搜索树中,右子树节点值,一定比当前节点要大,所以右子树一直

  • Java删除二叉搜索树的任意元素的方法详解

    本文实例讲述了Java删除二叉搜索树的任意元素的方法.分享给大家供大家参考,具体如下: 一.删除思路分析 在删除二叉搜索树的任意元素时,会有三种情况: 1.1 删除只有左孩子的节点 节点删除之后,将左孩子所在的二叉树取代其位置:连在原来节点父亲元素右节点的位置,比如在图中需要删除58这个节点. 删除58这个节点后,如下图所示: 1.2 删除只有右孩子的节点: 节点删除之后,将右孩子所在的二叉树取代其位置:连在原来节点的位置,比如在下图中需要删除58这个节点. 删除58这个节点后,如下图所示: 这

  • Java深入了解数据结构之二叉搜索树增 插 删 创详解

    目录 ①概念 ②操作-查找 ③操作-插入 ④操作-删除 1. cur.left == null 2. cur.right == null 3. cur.left != null && cur.right != null ⑤性能分析 ⑥完整代码 ①概念 二叉搜索树又称二叉排序树,它或者是一棵空树**,或者是具有以下性质的二叉树: 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树 ②操作-查找

  • Java数据结构之二叉搜索树详解

    目录 前言 性质 实现 节点结构 初始化 插入节点 查找节点 删除节点 最后 前言 今天leetcode的每日一题450是关于删除二叉搜索树节点的,题目要求删除指定值的节点,并且需要保证二叉搜索树性质不变,做完之后,我觉得这道题将二叉搜索树特性凸显的很好,首先需要查找指定节点,然后删除节点并且保持二叉搜索树性质不变,就想利用这个题目讲讲二叉搜索树. 二叉搜索树作为一个经典的数据结构,具有链表的快速插入与删除的特点,同时查询效率也很优秀,所以应用十分广泛,例如在文件系统和数据库系统一般会采用这种数

  • 剑指Offer之Java算法习题精讲二叉搜索树与数组查找

    题目一  解法 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; *

  • C++数据结构之二叉搜索树的实现详解

    目录 前言 介绍 实现 节点的实现 二叉搜索树的查找 二叉搜索树的插入 二叉搜索树的删除 总结 前言 今天我们来学一个新的数据结构:二叉搜索树. 介绍 二叉搜索树也称作二叉排序树,它具有以下性质: 非空左子树的所有键值小于其根节点的键值 非空右子树的所有键值大于其根节点的键值 左,右子树都是二叉搜索树 那么我先画一个二叉搜索树给大家看看,是不是真的满足上面的性质. 我们就以根节点6为例子来看,我们会发现比6小的都在6的左边,而比6大的都在6的右边.对于6的左右子树来说,所有的节点都遵循这个规则.

  • Java数据结构实现二维数组与稀疏数组转换详解

    基本介绍 当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组. 稀疏数组的处理方法是: ①记录数组一共有几行几列,有多少个不同的值(0除外). ②把具有不同值的元素的行列及值记录在一个小规模的数组中,从而缩小程序的规模. 二维数组转稀疏数组: ①遍历原始的二维数组,得到有效数据的个数 sum(除0外不同值) ②根据 sum 创建稀疏数组 sparseArr int[sum+1][3] ③将二维数组的有效数据数据存入到稀疏数组 (稀疏数组的第一行,三列分别记录二维数组

  • javascript数据结构之二叉搜索树实现方法

    本文实例讲述了javascript二叉搜索树实现方法.分享给大家供大家参考,具体如下: 二叉搜索树:顾名思义,树上每个节点最多只有二根分叉:而且左分叉节点的值 < 右分叉节点的值 . 特点:插入节点.找最大/最小节点.节点值排序 非常方便 二叉搜索树-javascript实现 <script type="text/javascript"> // <![CDATA[ //打印输出 function println(msg) { document.write(msg

  • 如何利用JavaScript实现二叉搜索树

    计算机科学中最常用和讨论最多的数据结构之一是二叉搜索树.这通常是引入的第一个具有非线性插入算法的数据结构.二叉搜索树类似于双链表,每个节点包含一些数据,以及两个指向其他节点的指针:它们在这些节点彼此相关联的方式上有所不同.二叉搜索树节点的指针通常被称为"左"和"右",用来指示与当前值相关的子树.这种节点的简单 JavaScript 实现如下: var node = { value: 125, left: null, right: null }; 从名称中可以看出,二

  • Java数据结构超详细分析二叉搜索树

    目录 1.搜索树的概念 2.二叉搜索树的简单实现 2.1查找 2.2插入 2.3删除 2.4修改 3.二叉搜索树的性能 1.搜索树的概念 二叉搜索树是一种特殊的二叉树,又称二叉查找树,二叉排序树,它有几个特点: 如果左子树存在,则左子树每个结点的值均小于根结点的值. 如果右子树存在,则右子树每个结点的值均大于根结点的值. 中序遍历二叉搜索树,得到的序列是依次递增的. 二叉搜索树的左右子树均为二叉搜索树. 二叉搜索树的结点的值不能发生重复. 2.二叉搜索树的简单实现 我们来简单实现以下搜索树,就不

随机推荐