平衡二叉樹（Balanced Binary Tree）

来源:https://www.cnblogs.com/dupengpeng/archive/2023/09/12/17694991.html
-Advertisement-
Play Games

平衡二叉樹（Balanced Binary Tree） 平衡二叉樹是一種特殊的二叉搜索樹，它具有以下特點： 每個節點的左子樹和右子樹的高度差不超過1。 所有的子樹也都是平衡二叉樹。 通過保持平衡性，平衡二叉樹可以在最壞情況下仍然具有較好的性能，保證查找、插入和刪除操作的時間複雜度為O(log n)。 ...


平衡二叉樹（Balanced Binary Tree）

平衡二叉樹是一種特殊的二叉搜索樹，它具有以下特點：

  • 每個節點的左子樹和右子樹的高度差不超過1。
  • 所有的子樹也都是平衡二叉樹。

通過保持平衡性，平衡二叉樹可以在最壞情況下仍然具有較好的性能，保證查找、插入和刪除操作的時間複雜度為O(log n)。

平衡二叉樹的常用實現方法有紅黑樹、AVL、替罪羊樹、Treap、伸展樹等

為什麼需要平衡二叉樹

在普通的二叉搜索樹中，如果插入或刪除操作不經過特殊處理，很容易出現樹的不平衡，使得樹的高度變得很大，導致查找操作的效率下降。

平衡二叉樹通過在每次插入或刪除後調整樹的結構，保持樹的平衡性。這樣可以確保樹的高度儘可能地低，使得查找操作仍然可以在較短的時間內完成。

如下圖：左子樹全部為空，從形式上看，更像一個單鏈表

怎麼平衡樹高的呢？

當二叉樹的左右分支樹高差不為 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. 更新相關節點的高度信息。

代碼實現

    // 左旋轉操作
    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. 更新相關節點的高度信息。

代碼實現

    // 右旋轉操作
    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時，需要進行左旋-右旋操作，先對左子節點進行左旋，然後再對當前節點進行右旋，如下圖


完整代碼在下麵

右左旋（先右旋後左旋）

當某個節點的右子樹的左子樹過深，平衡因數大於1時，需要進行右旋-左旋操作，先對右子節點進行右旋，然後再對當前節點進行左旋。和上面類似

完整代碼示例

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
    }
}

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • php使用jwt作登錄驗證
    JWT官網 https://jwt.io/ 選擇第一個 composer require firebase/php-jwt use Firebase\JWT\ExpiredException;use Firebase\JWT\JWT;use Firebase\JWT\Key;use Firebase ...
  • Go學習筆記5
    在今天的移動互聯網時代，手機已經成為了人們不可或缺的重要工具，而手機的聯網狀態也是我們經常需要關註的一個問題。我們需要保證手機網路處於正常的連接狀態，但是有時候，由於種種原因，手機的網路可能會斷開，這時我們需要及時發現，併進行相應的處理措施。而利用Api介面實現手機網路連接斷開的監聽，便是一種較為高 ...
  • 什麼是方法重載？返回值算重載嗎？
    遞歸函數和其他拓展 課前練習 請實現一個裝飾器，把'函數的返回值'+100然後'返回' def ount(fun): def werrod(*ardes,**warrrts): res=fun(*ardes,**warrrts) return res+100 return werrod @ount ...
  • ArrayList/MySQL數據批量寫入Excel表格
    ArrayList/MySQL數據集合寫入Excel 1.文章概述： 寫入 Excel 文件通常需要使用一些庫或工具，而"EasyExcel"通常是指的阿裡巴巴開源的EasyExcel庫。這個庫可以讓我們在Java中簡便地進行Excel文件的讀寫操作。 2.導入配置： <dependency> <g ...
  • 試試用Markdown來設計表單
    相信很多後端開發。對於前端知識是比較零碎的，所以很多時候寫表單這樣的工作，一般就是複製黏貼，然後改改欄位。對於HTML格式，一直覺得比較雜亂，不夠簡潔。 最近TJ發現了一個有趣的小工具：Create HTML Form。 看看上面它的Slogan，是不是很有意思？居然可以通過Markdown來編寫H ...
  • python採集數據保存csv, 文件內容亂碼了怎麼解決?
    如果你的 Python 程式採集到的數據在保存成 CSV 格式的文件時出現了亂碼，那麼可嘗試以下解決方法： 1. 在打開 CSV 文件時指定編碼方式 你可以使用 Python 中的 open() 函數打開 CSV 文件，併在 open() 函數中指定文件編碼方式為 CSV 文件原始編碼方式。如果 C ...
  • 2.14 PE結構：地址之間的轉換
    在可執行文件PE文件結構中，通常我們需要用到地址轉換相關知識，PE文件針對地址的規範有三種，其中就包括了`VA`，`RVA`，`FOA`三種，這三種該地址之間的靈活轉換也是非常有用的，本節將介紹這些地址範圍如何通過編程的方式實現轉換。VA（Virtual Address，虛擬地址）：它是在進程的虛擬... ...
  • 註意避坑！Java 內部類持有外部類會導致記憶體泄露。。。
    簡介 說明 本文介紹 Java 內部類持有外部類導致記憶體泄露的原因以及其解決方案。 為什麼內部類持有外部類會導致記憶體泄露 非靜態內部類會持有外部類，如果有地方引用了這個非靜態內部類，會導致外部類也被引用，垃圾回收時無法回收這個外部類（即使外部類已經沒有其他地方在使用了）。 解決方案 不要讓其他的地方 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類