平衡二叉树(Balanced Binary Tree)

这篇具有很好参考价值的文章主要介绍了平衡二叉树(Balanced Binary Tree)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

平衡二叉树(Balanced Binary Tree)

平衡二叉树是一种特殊的二叉搜索树,它具有以下特点:

  • 每个节点的左子树和右子树的高度差不超过1。
  • 所有的子树也都是平衡二叉树。

通过保持平衡性,平衡二叉树可以在最坏情况下仍然具有较好的性能,保证查找、插入和删除操作的时间复杂度为O(log n)。

平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等

为什么需要平衡二叉树

在普通的二叉搜索树中,如果插入或删除操作不经过特殊处理,很容易出现树的不平衡,使得树的高度变得很大,导致查找操作的效率下降。

平衡二叉树通过在每次插入或删除后调整树的结构,保持树的平衡性。这样可以确保树的高度尽可能地低,使得查找操作仍然可以在较短的时间内完成。

如下图:左子树全部为空,从形式上看,更像一个单链表

平衡二叉树(Balanced Binary Tree)

怎么平衡树高的呢?

当二叉树的左右分支树高差不为 1 时,需要进行左旋或者右旋,来调衡树高。这有点像开车的时候,如果车头偏左就往右打方向盘,车头偏右就往左打方向盘是一个道理。

class AVLTree {
    private Node root;

    private class Node {
        int val;
        int height; // 增加一个树高
        Node left;
        Node right;

        public Node(int val) {
            this.val = val;
            this.height = 1;
            this.left = null;
            this.right = null;
        }
    }
}

平衡因子

平衡因子是用来衡量平衡二叉树中某个节点的左子树和右子树高度差的一个指标。它表示了节点的平衡性,可以用来判断是否需要进行旋转操作来恢复树的平衡。
平衡因子的计算方法是,对于一个节点,它的平衡因子等于左子树高度减去右子树高度。具体公式可以表示为:
平衡因子 = 左子树高度 - 右子树高度
根据平衡因子的值,可以判断节点的平衡情况:

  • 平衡因子为0: 左子树和右子树的高度相等,节点处于平衡状态。
  • 平衡因子为正数: 左子树的高度大于右子树的高度,节点处于左重状态。
  • 平衡因子为负数: 右子树的高度大于左子树的高度,节点处于右重状态。
    当平衡因子的绝对值大于1时,表示节点的左右子树高度差过大,树失去平衡,需要进行旋转操作来恢复平衡。
    通过平衡因子的判断,可以及时发现不平衡的节点,并采取相应的调整措施以保持平衡二叉树的平衡性,确保树的高度在可控范围内,从而提高查找、插入和删除操作的效率。

左旋转

左旋是平衡二叉树中的一种旋转操作,用于调整不平衡节点及其子节点之间的关系。左旋的目的是将不平衡节点向左移动,并提升其右子节点作为新的父节点,从而恢复树的平衡性。

左旋的触发条件是当节点A的右子树高度较高(平衡因子大于1),并且节点B的左子树高度不小于节点B的右子树高度时,需要进行左旋操作。

具体情况下,左旋通常在以下情况下使用:

  1. 当在平衡二叉树中插入一个节点后,导致某个节点的平衡因子大于1,即左子树高度比右子树高度多2或更多时,需要进行左旋操作。
  2. 在删除节点后,导致某个节点的平衡因子小于-1,即右子树高度比左子树高度多2或更多时,也需要进行左旋操作。

左旋的目的是使得树保持平衡,确保树的高度差不超过1,从而保证查找、插入和删除等操作的时间复杂度在O(log n)范围内。

如下图:左旋的作用,相当于通过向上迁移树高差大于 1 的右子节点来降低树高的操作

  1. 找到需要进行左旋的节点,即节点值为4的节点。
  2. 将节点值为6的节点提升为新的根节点,并将原来的根节点值为4的节点降级为新根节点的左子节点。
  3. 将原来新根节点值为6的右子节点(值为7)作为原来根节点的右子节点。
  4. 将6原来的左子节点作为4个右子节点
  5. 更新相关节点的高度信息。

平衡二叉树(Balanced Binary Tree)

代码实现

    // 左旋转操作
    private Node rotateLeft(Node x) {
        Node y = x.right;
        Node T2 = y.left;

        // 执行旋转
        y.left = x;
        x.right = T2;

        // 更新节点高度
        x.height = Math.max(height(x.left), height(x.right)) + 1;
        y.height = Math.max(height(y.left), height(y.right)) + 1;

        return y;
    }

右旋转

和左旋转类似,目的是将不平衡节点向右移动,并提升其左子节点作为新的父节点,从而恢复树的平衡性。

  1. 找到需要进行右旋的节点,即节点值为10的节点。
  2. 将节点值为8的节点提升为新的根节点,并将原来的根节点值为10的节点降级为新根节点的右子节点。
  3. 将原来新根节点值为8的左子节点(值为7)作为原来根节点的左子节点。
  4. 更新相关节点的高度信息。

平衡二叉树(Balanced Binary Tree)

代码实现

    // 右旋转操作
    private Node rotateRight(Node y) {
        Node x = y.left;
        Node T2 = x.right;

        // 执行旋转
        x.right = y;
        y.left = T2;

        // 更新节点高度
        y.height = Math.max(height(y.left), height(y.right)) + 1;
        x.height = Math.max(height(x.left), height(x.right)) + 1;

        return x;
    }

左右旋(先左旋后右旋)

当某个节点的左子树的右子树过深,平衡因子小于-1时,需要进行左旋-右旋操作,先对左子节点进行左旋,然后再对当前节点进行右旋,如下图

平衡二叉树(Balanced Binary Tree)
平衡二叉树(Balanced Binary Tree)

完整代码在下面

右左旋(先右旋后左旋)

当某个节点的右子树的左子树过深,平衡因子大于1时,需要进行右旋-左旋操作,先对右子节点进行右旋,然后再对当前节点进行左旋。和上面类似

完整代码示例文章来源地址https://www.toymoban.com/news/detail-707948.html

public class AvlTreeDemo {
    public static void main(String[] args) {
        // 创建平衡二叉树对象
        AVLTree avlTree = new AVLTree();
        // 插入节点
        avlTree.insert(10);
        avlTree.insert(11);
        avlTree.insert(7);
        avlTree.insert(6);
        avlTree.insert(8);
        avlTree.insert(9);
        // 中序遍历并输出节点值
        System.out.print("中序遍历结果:");
        avlTree.inorderTraversal(); // 输出:10 20 25 30 40 50
    }
}

class AVLTree {
    private Node root;

    private class Node {
        int val;
        int height;
        Node left;
        Node right;

        public Node(int val) {
            this.val = val;
            this.height = 1;
            this.left = null;
            this.right = null;
        }
    }

    // 计算节点的高度
    private int height(Node node) {
        if (node == null) {
            return 0;
        }
        return node.height;
    }

    // 计算节点的平衡因子
    private int balanceFactor(Node node) {
        if (node == null) {
            return 0;
        }
        return height(node.left) - height(node.right);
    }

    // 右旋转操作
    private Node rotateRight(Node y) {
        Node x = y.left;
        Node T2 = x.right;

        // 执行旋转
        x.right = y;
        y.left = T2;

        // 更新节点高度
        y.height = Math.max(height(y.left), height(y.right)) + 1;
        x.height = Math.max(height(x.left), height(x.right)) + 1;

        return x;
    }

    // 左旋转操作
    private Node rotateLeft(Node x) {
        Node y = x.right;
        Node T2 = y.left;

        // 执行旋转
        y.left = x;
        x.right = T2;

        // 更新节点高度
        x.height = Math.max(height(x.left), height(x.right)) + 1;
        y.height = Math.max(height(y.left), height(y.right)) + 1;

        return y;
    }

    // 插入节点
    public void insert(int val) {
        root = insertNode(root, val);
    }

    private Node insertNode(Node node, int val) {
        // 执行标准的BST插入
        if (node == null) {
            return new Node(val);
        }

        if (val < node.val) {
            node.left = insertNode(node.left, val);
        } else if (val > node.val) {
            node.right = insertNode(node.right, val);
        } else { // 如果值相等,不允许重复插入
            return node;
        }

        // 更新节点的高度
        node.height = Math.max(height(node.left), height(node.right)) + 1;

        // 计算平衡因子
        int balance = balanceFactor(node);

        // 进行平衡调整
        // 左子树不平衡,右旋转
        if (balance > 1 && val < node.left.val) {
            return rotateRight(node);
        }
        // 右子树不平衡,左旋转
        if (balance < -1 && val > node.right.val) {
            return rotateLeft(node);
        }
        // 左子树不平衡,先左旋转后右旋转
        if (balance > 1 && val > node.left.val) {
            node.left = rotateLeft(node.left);
            return rotateRight(node);
        }
        // 右子树不平衡,先右旋转后左旋转
        if (balance < -1 && val < node.right.val) {
            node.right = rotateRight(node.right);
            return rotateLeft(node);
        }

        return node;
    }

    // 中序遍历
    public void inorderTraversal() {
        inorderHelper(root);
    }

    private void inorderHelper(Node node) {
        if (node == null) {
            return;
        }
        inorderHelper(node.left);
        System.out.print(node.val + " ");
        inorderHelper(node.right);
    }

    public static void main(String[] args) {
        // 创建平衡二叉树对象
        AVLTree avlTree = new AVLTree();

        // 插入节点
        avlTree.insert(10);
        avlTree.insert(20);
        avlTree.insert(30);
        avlTree.insert(40);
        avlTree.insert(50);
        avlTree.insert(25);

        // 中序遍历并输出节点值
        System.out.print("中序遍历结果:");
        avlTree.inorderTraversal(); // 输出:10 20 25 30 40 50
    }
}

到了这里,关于平衡二叉树(Balanced Binary Tree)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Java学数据结构(2)——树Tree & 二叉树binary tree & 二叉查找树 & AVL树 & 树的遍历

    1.树的出现:解决链表线性访问时间太慢,树的时间复杂度O(logN); 2.二叉树的定义,最多两个儿子节点; 3.二叉查找树,左小,右大,中居中;remove方法,两种,只有一个儿子节点,有两个儿子节点; 4.AVL树,在二叉查找树基础上加平衡条件,旋转方法,单旋转,双旋转;

    2024年02月10日
    浏览(49)
  • Leetcode 1367. Linked List in Binary Tree (二叉树好题)

    Linked List in Binary Tree Medium Given a binary tree root and a linked list with head as the first node. Return True if all the elements in the linked list starting from the head correspond to some downward path connected in the binary tree otherwise return False. In this context downward path means a path that starts at some node and goes downwards. Exampl

    2024年01月25日
    浏览(48)
  • 【算法】Distribute Coins in Binary Tree 在二叉树中分配硬币

    给定一个有 N 个结点的二叉树的根结点 root,树中的每个结点上都对应有 node.val 枚硬币,并且总共有 N 枚硬币。 在一次移动中,我们可以选择两个相邻的结点,然后将一枚硬币从其中一个结点移动到另一个结点。(移动可以是从父结点到子结点,或者从子结点移动到父结点。

    2024年02月16日
    浏览(41)
  • 二叉查找树(binary search tree)(难度7)

    C++数据结构与算法实现(目录) 答案在此:二叉查找树(binary search tree)(答案) 写在前面 部分内容参《算法导论》 基本接口实现 1 删除 删除值为value的第一个节点 删除叶子节点1 删除叶子节点1 (3)删除叶子节点1 删除有两个孩子的节点z 分成下面几个步骤进行: 1 找到

    2024年02月10日
    浏览(45)
  • 二叉搜索树(Binary_Search_Tree)

    二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树: 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值。 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值。 它的左右子树也分别为二叉搜索树。 如: a、从根开始

    2024年04月28日
    浏览(40)
  • 【C++】二叉搜索树Binary Search Tree

    二叉搜索树又被称为二叉排序树,顾名思义,当我们使用中序遍历时,会得到一个有序的序列。二叉搜索树有如下的性质: 1.若它的左子树不为空,则左子树上每个节点的值都小于根节点的值。 2.若它的右子树不为空,则右子树上每个节点的值都大于根节点的值。 3.左右子树

    2024年02月07日
    浏览(49)
  • 二叉搜索树(Binary Search Tree,BST)

    二叉搜索树(Binary Search Tree),也称二叉查找树或二叉排序树,是一种特殊的二叉树,它满足以下性质 对于二叉搜索树的每个节点 左子树中的所有节点的值都小于该节点的值 右子树中的所有节点的值都大于(或等于)该节点的值 对于二叉搜索树的任意节点,其左子树和右子

    2024年02月09日
    浏览(46)
  • 数据结构和算法学习记录——平衡二叉树(基本介绍、平衡因子、平衡二叉树的定义、平衡二叉树的高度)

    目录 基本介绍 平衡因子 平衡二叉树  平衡二叉树的高度  什么是平衡二叉树? 以一个例子来解释一下: 搜索树结点按不同的插入次序,将会导致不同的深度和平均查找长度ASL   在二叉搜索树中查找一个元素:  (a)要找到Jan,需要查找一次;要找到Feb,需要查找两次;

    2023年04月26日
    浏览(66)
  • 最优二叉搜索树(Optimal Binary Search Tree)_20230401

    前言 如果有序数组或有序表中的各个元素查找概率相等,那么采用二叉搜索树(BST)进行折半查找,性能最优。如果有序表中各个记录的查找概率不相等,情况又如何呢? 先看一个具体例子。已知有序表keys, 同时给出各个元素的查询频率,注意到各个元素的查询频率不相同。

    2024年02月12日
    浏览(51)
  • 【C++庖丁解牛】二叉搜索树(Binary Search Tree,BST)

    🍁你好,我是 RO-BERRY 📗 致力于C、C++、数据结构、TCP/IP、数据库等等一系列知识 🎄感谢你的陪伴与支持 ,故事既有了开头,就要画上一个完美的句号,让我们一起加油 二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树: 若它的左子树不为空,

    2024年03月28日
    浏览(64)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包