平衡二叉树及其应用详解

平衡二叉树

定义与性质

平衡二叉树（Balanced Binary Tree）是计算机科学中的一种数据结构，它是二叉排序树的一种特殊情况。

平衡二叉树满足以下性质：

左子树和右子树的高度差不超过 1。也就是说，对于任意节点，其左子树和右子树的高度差不超过 1。
左子树和右子树也都是平衡二叉树。

平衡二叉树的定义可以通过递归的方式来定义。一棵高度为 h 的平衡二叉树，必须满足以下两个条件之一：

该树为空，此时高度为 0。
该树的左子树和右子树都是高度为 h-1 的平衡二叉树。

平衡二叉树的定义保证了树中的每个节点的左右子树的高度差不超过 1，从而使得树的高度比较平衡，便于实现各种操作。
在这里插入图片描述

平衡二叉树的应用非常广泛，例如在搜索算法、排序算法、数据结构等领域中都有广泛的应用。由于平衡二叉树的高度比较平衡，因此它具有较好的时间复杂度，特别是对于查找操作，其时间复杂度为 O(logn)，其中 n 是树中的节点数。

查找遍历

平衡二叉树的查找遍历有三种基本的方法：前序遍历、中序遍历和后序遍历。

前序遍历（Preorder Traversal）：先访问根节点，然后按照先左后右的顺序递归遍历左子树和右子树。

中序遍历（Inorder Traversal）：先按照先左后右的顺序递归遍历左子树，然后访问根节点，最后按照先左后右的顺序递归遍历右子树。

后序遍历（Postorder Traversal）：先按照先左后右的顺序递归遍历左子树，然后按照先左后右的顺序递归遍历右子树，最后访问根节点。

除了这三种基本的遍历方法，平衡二叉树还有其他的遍历方法，例如层序遍历（Level Order Traversal）、反向遍历（Reverse Traversal）等。不同的遍历方法可以用于不同的应用场景，例如树的打印、树的统计等。

前序遍历

首先，我们需要定义一个平衡二叉树的节点类，包含左右子节点和节点值。然后，实现前序遍历的方法。

以下是平衡二叉树的前序遍历Java代码实现：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class BinaryTreePreorderTraversal {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);

            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }

        return result;
    }
}

这段代码首先定义了一个TreeNode类，用于表示平衡二叉树的节点。然后定义了一个BinaryTreePreorderTraversal类，其中包含一个preorderTraversal方法，用于实现前序遍历。在这个方法中，我们使用了一个栈来辅助遍历，确保遍历的顺序是前序遍历的顺序。

中序遍历

平衡二叉树的中序遍历可以使用递归或迭代的方式实现。以下是使用递归方式实现的代码：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class BinaryTreeInorderTraversal {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;

        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            result.add(curr.val);
            curr = curr.right;
        }

        return result;
    }
}

这段代码中，我们首先判断根节点是否为空，如果为空则直接返回一个空的结果列表。然后创建一个栈，并将根节点入栈。接下来进入循环，每次从栈中弹出一个节点，将其值加入结果列表中，并将其右子节点（如果存在）入栈。最后返回结果列表即可。

后序遍历

平衡二叉树的后序遍历可以使用递归或迭代的方式实现。以下是使用递归方式实现的代码：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class BinaryTreePostorderTraversal {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);

            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }

        return result;
    }
}

这段代码中，我们首先判断根节点是否为空，如果为空则直接返回一个空的结果列表。然后创建一个栈，并将根节点入栈。接下来进入循环，每次从栈中弹出一个节点，将其值加入结果列表中，并将其左右子节点（如果存在）入栈。最后返回结果列表即可。

插入与删除

平衡二叉树的插入与删除是二叉查找树的重要操作，普通二叉搜索树的操作类似，但是需要通过旋转来保持树的平衡。具体来说，插入或删除一个节点后，需要根据该节点的位置和平衡因子来判断是否需要进行旋转。如果需要进行旋转，则可以分为四种类型：L-L型旋转、L-R型旋转、R-L型旋转和R-R型旋转。这些类型的旋转都有相应的Java代码实现 。

下面是平衡二叉树插入和删除的Java实现：

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

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

    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 newNode(int key) {
        Node node = new Node(key);
        node.left = null;
        node.right = null;
        node.height = 1;
        return node;
    }

    // 右旋转
    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 (newNode(key));

        if (key < node.key)
            node.left = insert(node.left, key);
        else if (key > node.key)
            node.right = insert(node.right, key);
        else // 相等的键不允许在BST中
            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 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.right) <= 0)
            return leftRotate(root);

        // 左右型旋转
        if (balance > 1 && getBalance(root.left) < 0) {
            root.left = leftRotate(root.left);
            return rightRotate(root);
        }

        // 右左型旋转
        if (balance < -1 && getBalance(root.right) > 0) {
            root.right = rightRotate(root.right);
            return leftRotate(root);
        }

        return root;
    }

    // 获取最小值节点
    Node minValueNode(Node node) {
        Node current = node;
        while (current.left != null)
            current = current.left;
        return current;
    }
}

复杂度分析

时间复杂度

平衡二叉树的时间复杂度主要取决于插入、删除和查找操作的实现。下面将详细分析这三种操作的时间复杂度。

插入操作：

平衡二叉树的插入操作的时间复杂度为 O(logn)，其中 n 是树的节点数量。这是因为插入操作需要在树中找到适当的位置，以保证树的平衡。具体来说，插入操作需要执行以下步骤：

  1. 将节点插入到树的根节点。
  2. 如果插入的节点的值比根节点的值小，则将节点插入到根节点的左子树。
  3. 如果插入的节点的值比根节点的值大，则将节点插入到根节点的右子树。
  4. 在左子树或右子树中，重复执行步骤 2 和步骤 3，直到找到适当的位置。

在执行插入操作的过程中，最坏情况下需要执行 O(logn)次比较操作，才能找到适当的位置。因此，插入操作的时间复杂度为 O(logn)。

删除操作：

平衡二叉树的删除操作的时间复杂度为 O(logn)，其中 n 是树的节点数量。这是因为删除操作需要找到要删除的节点，并在树中进行调整，以保持树的平衡。具体来说，删除操作需要执行以下步骤：

  1. 找到要删除的节点。
  2. 如果要删除的节点只有一个孩子节点，则直接将该节点删除，并将该节点的孩子节点替换该节点。
  3. 如果要删除的节点有两个孩子节点，则需要找到该节点的后继节点，并将该节点的值替换为后继节点的值，然后删除该节点的后继节点。
  4. 在执行删除操作的过程中，需要对树进行调整，以保持树的平衡。

在执行删除操作的过程中，最坏情况下需要执行 O(logn)次比较操作，才能找到要删除的节点并进行调整。因此，删除操作的时间复杂度为 O(logn)。

查找操作：

平衡二叉树的查找操作的时间复杂度为 O(logn)，其中 n 是树的节点数量

空间复杂度

平衡二叉树的空间复杂度主要取决于树的实现方式。下面将详细分析平衡二叉树的空间复杂度。

如果使用数组实现平衡二叉树，则空间复杂度为 O(n)，其中 n 是树的节点数量。这是因为数组需要存储树的所有节点，每个节点需要占用一个存储空间。因此，空间复杂度为 O(n)。

如果使用链表实现平衡二叉树，则空间复杂度为 O(n)，其中 n 是树的节点数量。这是因为链表需要存储树的所有节点，每个节点需要占用一个存储空间。因此，空间复杂度为 O(n)。

如果使用递归实现平衡二叉树，则空间复杂度为 O(logn)，其中 n 是树的节点数量。这是因为递归实现需要使用栈来存储递归调用的上下文，每次递归调用需要占用一个栈帧，因此空间复杂度为 O(logn)。

总的来说，平衡二叉树的空间复杂度取决于树的实现方式。如果使用数组或链表实现平衡二叉树，则空间复杂度为 O(n)，其中 n 是树的节点数量。如果使用递归实现平衡二叉树，则空间复杂度为 O(logn)，其中 n 是树的节点数量。

应用场景

平衡二叉树的应用场景如下：

  1. 排序：平衡二叉树可以作为一种排序算法，例如堆排序和快速排序。通过维护一个平衡二叉树，可以快速地对数据进行排序。
  2. 查找：平衡二叉树可以作为一种查找算法，例如二叉查找树。通过维护一个平衡二叉树，可以快速地在树中查找特定的节点。
  3. 数据结构：平衡二叉树可以作为一种数据结构，例如红黑树。红黑树是一种特殊的平衡二叉树，它具有以下特点：
    • 每个节点要么是红色，要么是黑色。
    • 根节点是黑色。
    • 每个叶子节点（NIL 节点，空节点）是黑色。
    • 每个红色节点的两个子节点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色节点）

红黑树在实际应用中非常广泛，例如在操作系统、数据库、图形学等领域中都有广泛的应用。（下一篇将对红黑树做出详细介绍）

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/93912.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

echarts 甘特图一组显示多组数据

echarts 甘特图一组显示多组数据

<template><el-button type"primary" click"addlin">添加线</el-button><el-button type"success" click"addArea">添加区域</el-button><div ref"echart" id"echart" class&qu…
阅读更多...
18-使用钩子函数判断用户登录权限-登录前缀

18-使用钩子函数判断用户登录权限-登录前缀

钩子函数的两种应用: (1). 应用在app上 before_first_request before_request after_request teardown_request (2). 应用在蓝图上 before_app_first_request #只会在第一次请求执行,往后就不执行, (待定,此属性没调试通过) before_app_request # 每次请求都会执行一次(重点…
阅读更多...
计网-All

计网-All

路由器的功能与路由表的查看_路由器路由表_傻傻小猪哈哈的博客-CSDN博客路由基础-直连路由、静态路由与动态路由的概念_MikeVane-bb的博客-CSDN博客路由器的功能与路由表的查看_路由器路由表_傻傻小猪哈哈的博客-CSDN博客 直连路由就是路由器直接连了一个网段&#xff0c;他就…
阅读更多...
【C++ 学习 ⑱】- 多态（上）

【C++ 学习 ⑱】- 多态（上）

目录 一、多态的概念和虚函数 1.1 - 用基类指针指向派生类对象 1.2 - 虚函数和虚函数的重写 1.3 - 多态构成的条件 1.4 - 多态的应用场景 二、协变和如何析构派生类对象 2.1 - 协变 2.2 - 如何析构派生类对象 三、C11 的 override 和 final 关键字 一、多态的概念和虚…
阅读更多...
微信扫码跳转微信小程序

微信扫码跳转微信小程序

一:首先声明为什么需要这样做 项目中需要在后台管理页面进行扫码支付,其他人弄了微信小程序支付,所以就需要挑战小程序进行支付,在跳转的时候需要参数例如订单编号等 二:跳转小程序的方法有多种 接口调用凭证 | 微信开放文档 具体可以参考微信开放文档 1.获取scheme码 按照文…
阅读更多...
【项目实战典型案例】05.前后端分离的好处(发送调查问卷)

【项目实战典型案例】05.前后端分离的好处(发送调查问卷)

目录 一、背景二、思路三、过程1、主要的业务逻辑2、解决问题的思路 四、总结五、面向对象的好处 一、背景 以下流程图是给用户发送调查问的整体流程&#xff0c;将不必要的业务逻辑放到前端进行处理。这样导致逻辑混乱难以维护。前后端分离的其中一个目的是将功能的样式放在了…
阅读更多...
基础论文学习（5）——MAE

基础论文学习（5）——MAE

MAE&#xff1a;Masked Autoencoders Are Scalable Vision Learners Self-Supervised Learning step1&#xff1a;先用无标签数据集&#xff0c;把参数从一张白纸训练到初步预训练模型&#xff0c;可以得到数据的 Visual Representationstep2&#xff1a;再从初步成型&#x…
阅读更多...
clickhouse ssb-dbgen数据构造 及 clickhouse-benchmark简单压测

clickhouse ssb-dbgen数据构造 及 clickhouse-benchmark简单压测

一、 测试数据构造 1. 数据样例 官方文档有给出一批数据样例。优点是比较真实&#xff0c;缺点是太大了&#xff0c;动辄上百G不适合简单小测试 Anonymized Yandex.Metrica DatasetStar Schema BenchmarkWikiStatTerabyte of Click Logs from CriteoAMPLab Big Data Benchma…
阅读更多...
浅析Linux 物理内存外碎片化

浅析Linux 物理内存外碎片化

本文出现的内核代码来自Linux4.19&#xff0c;如果有兴趣&#xff0c;读者可以配合代码阅读本文。 一、Linux物理内存外碎片化概述 什么是Linux物理内存碎片化&#xff1f;Linux物理内存碎片化包括两种&#xff1a; 1.物理内存内碎片&#xff1a;指分配给用户的内存空间中未…
阅读更多...
【产品规划】优先级规划

【产品规划】优先级规划

文章目录 1、功能优先级保障了产品在最短时间接受验证2、隐藏在优先级背后的是产品的目标和价值3、敏捷方法论中的功能优先级制定方法4、优先级制定时常见问题和应对方法5、敏捷方法论中的开发计划制定 1、功能优先级保障了产品在最短时间接受验证 2、隐藏在优先级背后的是产品…
阅读更多...
C++ list模拟实现

C++ list模拟实现

list模拟实现代码&#xff1a; namespace djx {template<class T>struct list_node{T _data;list_node<T>* _prev;list_node<T>* _next;list_node(const T& x T()):_data(x),_prev(nullptr),_next(nullptr){}};template<class T,class Ref,class Pt…
阅读更多...
ctfshow-红包题第二弹

ctfshow-红包题第二弹

0x00 前言 CTF 加解密合集CTF Web合集 0x01 题目 0x02 Write Up 同样&#xff0c;先看一下有没有注释的内容&#xff0c;可以看到有一个cmd的入参 执行之后可以看到文件代码&#xff0c;可以看到也是eval&#xff0c;但是中间对大部分的字符串都进行了过滤&#xff0c;留下了…
阅读更多...
纸贵科技连续三年蝉联IDC中国 FinTech 50榜单

纸贵科技连续三年蝉联IDC中国 FinTech 50榜单

近日&#xff0c;国际权威市场研究机构IDC公布了“2023 IDC中国FinTech 50榜单”。作为领先的区块链技术和解决方案服务商&#xff0c;纸贵科技凭借过硬的区块链技术和丰富的金融科技创新成果&#xff0c;连续第三年荣登IDC中国FinTech 50榜单。 IDC中国FinTech 50榜单是金融科…
阅读更多...
【leetcode 力扣刷题】双指针///原地扩充线性表

【leetcode 力扣刷题】双指针///原地扩充线性表

双指针///原地扩充线性表 剑指 Offer 05. 替换空格定义一个新字符串扩充字符串&#xff0c;原地替换思考 剑指 Offer 05. 替换空格 题目链接&#xff1a;剑指 Offer 05. 替换空格 题目内容&#xff1a; 这是一道简单题&#xff0c;理解题意&#xff0c;就是将字符串s中的空格…
阅读更多...
很干的 Nginx

很干的 Nginx

&#x1f3a8; 前言 本篇文章有些概念性的东西&#xff0c;是结合自己的理解表达出来的&#xff0c;可能有些理解不到位的地方。希望多多指教&#xff0c;谢谢大家。 红包献上 &#x1f9e7;&#x1f9e7;&#x1f9e7;&#x1f9e7;&#x1f9e7;&#x1f9e7;&#x1f9e7;…
阅读更多...
【c语言】文件操作 万字详解

【c语言】文件操作 万字详解

目录 一&#xff0c;为什么使用文件 二&#xff0c;什么是文件 1&#xff0c;程序文件 2&#xff0c;数据文件 3&#xff0c;文件名 三&#xff0c;文件的打开和关闭 1&#xff0c;文件指针 2&#xff0c;文件的打开和关闭 四&#xff0c; 文件的顺序读写 1&#xff0c;顺序…
阅读更多...
ethers.js2：provider提供商

ethers.js2：provider提供商

1、Provider类 Provider类是对以太坊网络连接的抽象&#xff0c;为标准以太坊节点功能提供简洁、一致的接口。在ethers中&#xff0c;Provider不接触用户私钥&#xff0c;只能读取链上信息&#xff0c;不能写入&#xff0c;这一点比web3.js要安全。 除了之前介绍的默认提供者d…
阅读更多...
如何编译打包OpenSSH 9.4并实现批量升级

如何编译打包OpenSSH 9.4并实现批量升级

1 介绍 openssh 9.4版本已于8月10号发布&#xff0c;安全团队又催着要赶紧升级环境里的ssh版本&#xff0c;本文主要介绍Centos5、Centos6、Centos7下openssh 9.4源码编译rpm包以及批量升级服务器openssh版本的方法。关注公众号后台回复ssh可获取本文相关源码文件。 https://w…
阅读更多...
使用Tampermonkey（篡改猴）向页面注入js脚本

使用Tampermonkey（篡改猴）向页面注入js脚本

一、Tampermonkey 简单介绍 Tampermonkey是一款浏览器插件&#xff0c;适用于Chrome、Microsoft Edge、Safari、Opera Next 和 Firefox。他允许我们自定义javascript给指定网页添加功能&#xff0c;或修改现有功能。也可以用来辅助调试&#xff0c;或去除网页广告等。 官网地…
阅读更多...
深度学习-4-二维目标检测-YOLOv3理论模型

深度学习-4-二维目标检测-YOLOv3理论模型

单阶段目标检测模型YOLOv3 R-CNN系列算法需要先产生候选区域&#xff0c;再对候选区域做分类和位置坐标的预测&#xff0c;这类算法被称为两阶段目标检测算法。近几年&#xff0c;很多研究人员相继提出一系列单阶段的检测算法&#xff0c;只需要一个网络即可同时产生候选区域并…
阅读更多...
最新文章

Copyright @ 2022~2023