如何实现一个高效的二叉搜索树(BST)?请给出时间复杂度分析。 要求:设计一个二叉搜索树,支持插入、删除和查找操作。要求在平均情况下,这些操作的时间复杂度为O(log n)。同时,考虑树的平衡性,使得树的高度保持在对数级别。

本文涉及的产品
日志服务 SLS,月写入数据量 50GB 1个月
简介: 如何实现一个高效的二叉搜索树(BST)?请给出时间复杂度分析。要求:设计一个二叉搜索树,支持插入、删除和查找操作。要求在平均情况下,这些操作的时间复杂度为O(log n)。同时,考虑树的平衡性,使得树的高度保持在对数级别。

在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)。

相关实践学习
日志服务之使用Nginx模式采集日志
本文介绍如何通过日志服务控制台创建Nginx模式的Logtail配置快速采集Nginx日志并进行多维度分析。
相关文章
|
14天前
|
缓存 监控 算法
分析慢日志文件来优化 PHP 脚本的性能
分析慢日志文件来优化 PHP 脚本的性能
08-06-06>pe_xscan 精简log分析代码 速度提升一倍
08-06-06>pe_xscan 精简log分析代码 速度提升一倍
|
2月前
|
存储 分布式计算 大数据
【Flume的大数据之旅】探索Flume如何成为大数据分析的得力助手,从日志收集到实时处理一网打尽!
【8月更文挑战第24天】Apache Flume是一款高效可靠的数据收集系统,专为Hadoop环境设计。它能在数据产生端与分析/存储端间搭建桥梁,适用于日志收集、数据集成、实时处理及数据备份等多种场景。通过监控不同来源的日志文件并将数据标准化后传输至Hadoop等平台,Flume支持了性能监控、数据分析等多种需求。此外,它还能与Apache Storm或Flink等实时处理框架集成,实现数据的即时分析。下面展示了一个简单的Flume配置示例,说明如何将日志数据导入HDFS进行存储。总之,Flume凭借其灵活性和强大的集成能力,在大数据处理流程中占据了重要地位。
36 3
|
2月前
|
应用服务中间件 Linux nginx
在Linux中,如何统计ip访问情况?分析 nginx 访问日志?如何找出访问页面数量在前十位的ip?
在Linux中,如何统计ip访问情况?分析 nginx 访问日志?如何找出访问页面数量在前十位的ip?
|
2月前
|
监控 安全 关系型数据库
在Linux中,什么是系统日志和应用程序日志?如何分析它们?
在Linux中,什么是系统日志和应用程序日志?如何分析它们?
|
2月前
|
存储 消息中间件 监控
Java日志详解:日志级别,优先级、配置文件、常见日志管理系统ELK、日志收集分析
Java日志详解:日志级别,优先级、配置文件、常见日志管理系统、日志收集分析。日志级别从小到大的关系(优先级从低到高): ALL < TRACE < DEBUG < INFO < WARN < ERROR < FATAL < OFF 低级别的会输出高级别的信息,高级别的不会输出低级别的信息
|
2月前
|
算法 关系型数据库 程序员
第一周算法设计与分析:A : log2(N)
这篇文章介绍了解决算法问题"输入一个数N,输出log2N(向下取整)"的三种编程思路,包括使用对数函数和幂函数的转换方法,以及避免浮点数精度问题的整数逼近方法。
|
2月前
|
存储 数据可视化 Linux
在Linux中,如何使用ELK进行日志管理和分析?
在Linux中,如何使用ELK进行日志管理和分析?
|
2月前
|
存储 监控 数据可视化
在Linux中,有哪些日志管理和分析工具?
在Linux中,有哪些日志管理和分析工具?
|
2月前
|
应用服务中间件 Shell nginx
shell分析nginx日志的一些指令
shell分析nginx日志的一些指令
下一篇
无影云桌面