java如何实现一个高效的二叉搜索树(BST)?请给出时间复杂度分析。

简介: 这段内容介绍了Java中使用AVL树实现高效二叉搜索树的方法。AVL树是一种自平衡树,节点子树高度差不超过1,确保操作时间复杂度为O(log n)。代码包括了`Node`类和`AVLTree`类,实现了节点、插入、删除、查找和平衡旋转等方法。通过旋转操作,维持树的平衡,保证了搜索效率。

在Java中,我们可以使用AVL树来实现一个高效的二叉搜索树。AVL树是一种自平衡的二叉搜索树,它的每个节点的两个子树的高度最多相差1,因此它的时间复杂度为O(log n)。

以下是一个简单的AVL树实现:

class Node {
   
    int key, height;
    Node left, right;

    Node(int d) {
   
        key = d;
        height = 1;
    }
}

class AVLTree {
   
    Node root;

    int height(Node N) {
   
        if (N == null)
            return 0;
        return N.height;
    }

    int max(int a, int b) {
   
        return (a > b) ? a : b;
    }

    Node rightRotate(Node y) {
   
        Node x = y.left;
        Node T2 = x.right;
        x.right = y;
        y.left = T2;
        y.height = max(height(y.left), height(y.right)) + 1;
        x.height = max(height(x.left), height(x.right)) + 1;
        return x;
    }

    Node leftRotate(Node x) {
   
        Node y = x.right;
        Node T2 = y.left;
        y.left = x;
        x.right = T2;
        x.height = max(height(x.left), height(x.right)) + 1;
        y.height = max(height(y.left), height(y.right)) + 1;
        return y;
    }

    int getBalance(Node N) {
   
        if (N == null)
            return 0;
        return height(N.left) - height(N.right);
    }

    Node insert(Node node, int key) {
   
        if (node == null)
            return (new Node(key));
        if (key < node.key)
            node.left = insert(node.left, key);
        else if (key > node.key)
            node.right = insert(node.right, key);
        else
            return node;
        node.height = 1 + max(height(node.left), height(node.right));
        int balance = getBalance(node);
        if (balance > 1 && key < node.left.key)
            return rightRotate(node);
        if (balance < -1 && key > node.right.key)
            return leftRotate(node);
        if (balance > 1 && key > node.left.key) {
   
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }
        if (balance < -1 && key < node.right.key) {
   
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
        return node;
    }

    Node minValueNode(Node node) {
   
        Node current = node;
        while (current.left != null)
            current = current.left;
        return current;
    }

    Node deleteNode(Node root, int key) {
   
        if (root == null)
            return root;
        if (key < root.key)
            root.left = deleteNode(root.left, key);
        else if (key > root.key)
            root.right = deleteNode(root.right, key);
        else {
   
            if ((root.left == null) || (root.right == null)) {
   
                Node temp = null;
                if (temp == root.left)
                    temp = root.right;
                else
                    temp = root.left;
                if (temp == null) {
   
                    temp = root;
                    root = null;
                } else
                    root = temp;
            } else {
   
                Node temp = minValueNode(root.right);
                root.key = temp.key;
                root.right = deleteNode(root.right, temp.key);
            }
        }
        if (root == null)
            return root;
        root.height = max(height(root.left), height(root.right)) + 1;
        int balance = getBalance(root);
        if (balance > 1 && getBalance(root.left) >= 0)
            return rightRotate(root);
        if (balance > 1 && getBalance(root.left) < 0) {
   
            root.left = leftRotate(root.left);
            return rightRotate(root);
        }
        if (balance < -1 && getBalance(root.right) <= 0)
            return leftRotate(root);
        if (balance < -1 && getBalance(root.right) > 0) {
   
            root.right = rightRotate(root.right);
            return leftRotate(root);
        }
        return root;
    }

    boolean search(Node root, int key) {
   
        if (root == null)
            return false;
        if (root.key == key)
            return true;
        return key < root.key ? search(root.left, key) : search(root.right, key);
    }
}

在这个实现中,我们使用了旋转操作来保持树的平衡。插入、删除和查找操作的时间复杂度都是O(log n)。

目录
相关文章
|
25天前
|
存储 Java
【编程基础知识】 分析学生成绩:用Java二维数组存储与输出
本文介绍如何使用Java二维数组存储和处理多个学生的各科成绩,包括成绩的输入、存储及格式化输出,适合初学者实践Java基础知识。
57 1
|
2月前
|
缓存 JavaScript Java
常见java OOM异常分析排查思路分析
Java虚拟机(JVM)遇到内存不足时会抛出OutOfMemoryError(OOM)异常。常见OOM情况包括:1) **Java堆空间不足**:大量对象未被及时回收或内存泄漏;2) **线程栈空间不足**:递归过深或大量线程创建;3) **方法区溢出**:类信息过多,如CGLib代理类生成过多;4) **本机内存不足**:JNI调用消耗大量内存;5) **GC造成的内存不足**:频繁GC但效果不佳。解决方法包括调整JVM参数(如-Xmx、-Xss)、优化代码及使用高效垃圾回收器。
138 15
常见java OOM异常分析排查思路分析
|
3月前
|
Java 程序员
Java 一个 Scanner.nextInt 造成的奇怪问题及分析解决过程
Java 一个 Scanner.nextInt 造成的奇怪问题及分析解决过程
|
8天前
|
存储 Java 关系型数据库
在Java开发中,数据库连接是应用与数据交互的关键环节。本文通过案例分析,深入探讨Java连接池的原理与最佳实践
在Java开发中,数据库连接是应用与数据交互的关键环节。本文通过案例分析,深入探讨Java连接池的原理与最佳实践,包括连接创建、分配、复用和释放等操作,并通过电商应用实例展示了如何选择合适的连接池库(如HikariCP)和配置参数,实现高效、稳定的数据库连接管理。
21 2
|
9天前
|
Java 关系型数据库 数据库
面向对象设计原则在Java中的实现与案例分析
【10月更文挑战第25天】本文通过Java语言的具体实现和案例分析,详细介绍了面向对象设计的五大核心原则:单一职责原则、开闭原则、里氏替换原则、接口隔离原则和依赖倒置原则。这些原则帮助开发者构建更加灵活、可维护和可扩展的系统,不仅适用于Java,也适用于其他面向对象编程语言。
9 2
|
25天前
|
机器学习/深度学习 算法 搜索推荐
让星星⭐月亮告诉你,Java冒泡排序及其时间复杂度计算
冒泡排序是一种简单的排序算法,通过多次遍历数组,每次比较相邻元素并交换位置,将较小的元素逐步移至数组前端。第一轮结束后,最小值会位于首位;第二轮则将次小值置于第二位,依此类推。经过 (n-1) 轮遍历后,数组完成排序。冒泡排序的时间复杂度为 O(n²),在最优情况下(已排序数组)时间复杂度为 O(n)。示例代码展示了如何实现冒泡排序。
46 1
|
25天前
|
Java
让星星⭐月亮告诉你,Java synchronized(*.class) synchronized 方法 synchronized(this)分析
本文通过Java代码示例,介绍了`synchronized`关键字在类和实例方法上的使用。总结了三种情况:1) 类级别的锁,多个实例对象在同一时刻只能有一个获取锁;2) 实例方法级别的锁,多个实例对象可以同时执行;3) 同一实例对象的多个线程,同一时刻只能有一个线程执行同步方法。
15 1
|
25天前
|
小程序 Oracle Java
JVM知识体系学习一:JVM了解基础、java编译后class文件的类结构详解,class分析工具 javap 和 jclasslib 的使用
这篇文章是关于JVM基础知识的介绍,包括JVM的跨平台和跨语言特性、Class文件格式的详细解析,以及如何使用javap和jclasslib工具来分析Class文件。
34 0
JVM知识体系学习一:JVM了解基础、java编译后class文件的类结构详解,class分析工具 javap 和 jclasslib 的使用
|
27天前
|
Java
如何从Java字节码角度分析问题|8月更文挑战
如何从Java字节码角度分析问题|8月更文挑战
|
1月前
|
安全 网络协议 Java
Java反序列化漏洞与URLDNS利用链分析
Java反序列化漏洞与URLDNS利用链分析
47 3