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

目录
  • 1.搜索树的概念
  • 2.二叉搜索树的简单实现
    • 2.1查找
    • 2.2插入
    • 2.3删除
    • 2.4修改
  • 3.二叉搜索树的性能

1.搜索树的概念

二叉搜索树是一种特殊的二叉树,又称二叉查找树,二叉排序树,它有几个特点:

  • 如果左子树存在,则左子树每个结点的值均小于根结点的值。
  • 如果右子树存在,则右子树每个结点的值均大于根结点的值。
  • 中序遍历二叉搜索树,得到的序列是依次递增的。
  • 二叉搜索树的左右子树均为二叉搜索树。
  • 二叉搜索树的结点的值不能发生重复。

2.二叉搜索树的简单实现

我们来简单实现以下搜索树,就不使用泛型了,二叉搜索树基本结构:

public class BinarySearchTree {

    static class Node {
        public int val;
        public Node left;
        public Node right;
        public Node(int val) {
            this.val = val;
        }
    }

    public Node root;
    //其他方法
}

2.1查找

二叉搜索树最擅长的就是查找,根据二叉搜索树的定义,左子树的元素比根小,右子树的元素比根大,所以我们只需要根据根结点的值与目标元素的值比较,就能实现查找功能。

  • 根与目标元素相等,表示找到了。
  • 根比目标元素大,去左子树找。
  • 根比目标元素小,去右子树找。
  • 左右子树找不到,那就找不到了。

参考实现代码:

    public Node search(int key) {
        Node cur = this.root;
        while (cur != null) {
            //根与目标元素相等,表示找到了。
            if (cur.val == key) return cur;
            //根比目标元素大,去左子树找。
            else if (cur.val > key) cur = cur.left;
            //根比目标元素小,去右子树找。
            else cur = cur.right;
        }
        //此时cur = null, 左右子树找不到,那就找不到了。
        return cur;
    }

2.2插入

需要在二叉搜索树中插入一个元素,首先得找到一个合适的插入位置,如何找呢?其实就是利用搜索树查找的方式,找到一个空位,如何将目标结点插入到这个位置。

  • 根与插入元素相等,插入元素不能与搜索树中的元素相等,插入失败。
  • 根比插入元素大,去左子树找。
  • 根比插入元素小,去右子树找。
  • 找到的结点为空,那这个位置就是我们要找的空位。

由于你找到空位时,无法获取该空位的前一个位置,所以每次查找的时候都需要保存上一次查找的位置。

找到位置后,将目标结点插入到该位置。

参考实现代码:

    public boolean insert(int val) {
        //结点为空,直接插
        if(root == null) {
            root = new Node(val);
            return true;
        }
        Node cur = this.root;   //当前查找位置
        Node parent = null;     //查找的上一个位置
        while (cur != null) {
            parent = cur;
            if (val > cur.val) cur = cur.right;
            else if (val < cur.val) cur = cur.left;
            else return false;
        }
        //开始插入,找到空位前一个位置,比插入元素小,空位在右边,插入右边
        if (val > parent.val) {
            parent.right = new Node(val);
        } else {
            //比插入元素大,空位在左边,插入左边
            parent.left = new Node(val);
        }
        return true;
    }

2.3删除

删除是搜索树基本操作中最麻烦的一个操作,需要考虑多种情况。

不妨设需要删除的结点为curcur的父结点为parent,搜索树的根结点为root。首先需要删除结点,那就得找到结点,所以第一步是找结点,思路与查找的思路一模一样。

第二步那就是删除了,删除结点大概有下面几种情况:

情况1:cur.left == null

  • cur == root,让root = cur.right;
  • cur != root且parent.left == cur,让parent.left = cur.right;
  • cur != root且parent.right == cur,让parent.right = cur.right。

情况2:cur.right == null

  • cur == null,让root = cur.left;
  • cur != root且parent.left == cur,让parent.left = cur.left;
  • cur != root且parent.right == cur,让parent.right = cur.left。

情况3:cur.left != null && cur.right != null

方案1:找到cur右子树中最小的元素target,然后将该元素的值覆盖到cur处(可以理解为交换),此时等价于删除target处的结点,即该结点的父结点为preTarget

因为targetcur右子树最小的一个结点,所以target.left == null,此时preTarget.left == target,所以删除时按照上面的情况1去进行删除。

但是还有一种特殊情况,那就是cur.right就是最小结点,此时preTarget==cur,即preTarget.right == target,这时删除时要将 preTarget.right = target.right。

方案2:找到cur左子树中最大的元素target,然后将该元素的值覆盖到cur处(可以理解为交换),此时等价于删除target处的结点,即该结点的父结点为preTarget

因为targetcur左子树最大的一个结点,所以target.right == null,此时preTarget.right == target,所以删除时按照上面的情况2去进行删除。

但是还有一种特殊情况,那就是cur.left就是左子树最大结点,此时preTarget==cur,即preTarget.left == target,这时删除时要将 preTarget.left = target.left。

参考实现代码:

    public void remove(int key) {
        Node cur = root;
        Node parent = null;
        while (cur != null) {
            if(cur.val == key) {
                //这里开始删除
                removeNode(cur,parent);
                break;
            }else if(cur.val < key) {
                parent = cur;
                cur = cur.right;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
    }

removeNode方法(方案1):

    public void removeNode(Node cur,Node parent) {
        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 preTarget  = cur ;
            Node target  = cur.right;
            while (target.left != null) {
                preTarget = target;
                target = target.left;
            }
            cur.val = target.val;
            if (target == preTarget.left) {
                preTarget.left = target.right;
            } else {
                preTarget.right = target.right;
            }
        }
    }

removeNode方法(方案2):

    public void removeNode(Node cur,Node parent) {
        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 preTarget  = cur ;
            Node target  = cur.left;
            while (target.right != null) {
                preTarget = target;
                target = target.right;
            }
            cur.val = target.val;
            if (target == preTarget.left) {
                preTarget.left = target.left;
            } else {
                preTarget.right = target.left;
            }
        }
    }

2.4修改

搜索树的修改可以基于删除和插入,先删除目标元素,然后再插入修改元素。

参考实现代码:

    public void set(int key, int val) {
        remove(key);
        insert(val);
    }

3.二叉搜索树的性能

在平衡二叉树的情况下(左右子树高度差不超过1),假设有n个结点,此时时间复杂度为二叉树的高度,即 O ( l o g 2 n ) O(log_2n) O(log2​n),但是这只是例行情况,最不理想的情况就是二叉树化为单分支树,时间复杂为 O ( n ) O(n) O(n)。

为了解决这个问题,后面引申出AVL树,红黑树,其中TreeMap与TreeSet的底层就是红黑树。具体红黑树是什么,这里就不多说了。

本文到底了,你学会了吗?

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

(0)

相关推荐

  • 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实现二叉搜索树

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

  • java基础二叉搜索树图文详解

    目录 概念 直接实践 准备工作:定义一个树节点的类,和二叉搜索树的类. 搜索二叉树的查找功能 搜索二叉树的插入操作 搜索二叉树删除节点的操作-难点 性能分析 总程序-模拟实现二叉搜索树 和java类集的关系 总结 概念 二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:1.若它的左子树不为空,则左子树上所有节点的值都小于根结点的值.2.若它的右子树不为空,则右子树上所有节点的值都大于根结点的值.3.它的左右子树也分别为二叉搜索树 直接实践 准备工作:定义一个树节点的类,和二

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

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

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

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

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

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

  • Java 求解如何把二叉搜索树转换为累加树

    一.题目 给出二叉搜索树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和. 提醒一下,二叉搜索树满足下列约束条件: 节点的左子树仅包含键 小于 节点键的节点. 节点的右子树仅包含键 大于 节点键的节点. 左右子树也必须是二叉搜索树. 二.题解 观察示例图发现,树的遍历顺序为右,中,左的顺序,每个节点的值,是按照这个顺序累加的状态 由于是需要累加,所以需要pre指针记录当前遍历节点

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

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

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

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

  • 剑指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++简单实现与分析二叉搜索树流程

    目录 二叉搜索树 二叉搜索树的重要操作 二叉搜索树实现(key模型) 二叉搜索树的应用 二叉搜索树的实现(key/value模型) 二叉搜索树 二叉搜索树又被称为二叉排序树.它可以是一个空树,如果不是空树则满足下列性质: 1.如果它的左子树不为空,那么左子树上的所有节点都小于根. 2.如果它的右子树不为空,那么右子树上的所有节点都大于根 3.它的左子树.右子树也是二叉搜索树. 二叉搜索树的重要操作 二叉搜索树的插入 1.如果树为空,则直接插入 2.如果树不为空,则找到对应的位置插入. 查找办法:

  • C++ 超详细快速掌握二叉搜索树

    目录 二叉搜索树概念与操作 二叉搜索树的概念 二叉搜索树的操作 查找 插入 删除 二叉搜索树的应用 二叉树的性能分析 二叉搜索树概念与操作 二叉搜索树的概念 二叉搜索树又称二叉排序树,若它的左子树不为空,则左子树上所有节点的值都小于根节点的值:若它的右子树不为空,则右子树上所有节点的值都大于根节点的值,它的左右子树也分别未二叉搜索树.也可以是一颗空树. int a[] = { 5, 3, 4, 1, 7, 8, 2, 6, 0, 9 }; 二叉搜索树的操作 查找 迭代: Node* Find(c

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

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

  • C++数据结构二叉搜索树的实现应用与分析

    目录 概念 二叉搜索树的实现

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

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

  • Java 栈与队列超详细分析讲解

    目录 一.栈(Stack) 1.什么是栈? 2.栈的常见方法 3.自己实现一个栈(底层用一个数组实现) 二.队列(Queue) 1.什么是队列? 2.队列的常见方法 3.队列的实现(单链表实现) 4.循环队列 一.栈(Stack) 1.什么是栈? 栈其实就是一种数据结构 - 先进后出(先入栈的数据后出来,最先入栈的数据会被压入栈底) 什么是java虚拟机栈? java虚拟机栈只是JVM当中的一块内存,该内存一般用来存放 例如:局部变量当调用函数时,我们会为函数开辟一块内存,叫做 栈帧,在 jav

随机推荐