個人部落格傳送門

一、須知須會

平衡因子 : 二叉樹的左子樹 - 右子樹 = 高度的內插補點,在平衡樹中可能的值(-1 ,0 ,1)
平衡 : 平衡因子 的絕對值小于 2 (下圖第一張為平衡樹, 第二張為不平衡樹)

平衡樹且平衡因子==0

資料結構(二), AVL平衡二叉樹一、須知須會二、簡介三、基本特征四、算法描述五、完整代碼

非平衡樹且平衡因子==-2

資料結構(二), AVL平衡二叉樹一、須知須會二、簡介三、基本特征四、算法描述五、完整代碼

樹的旋轉 : 參考維基百科樹的旋轉

資料結構(二), AVL平衡二叉樹一、須知須會二、簡介三、基本特征四、算法描述五、完整代碼

資料結構(二), AVL平衡二叉樹一、須知須會二、簡介三、基本特征四、算法描述五、完整代碼

轉軸的移動方向來決定它是左旋還是右旋, 本文中稱轉軸右移為右旋反之則是左旋

右旋 : (Q為樹的根節點, P為轉軸, 轉軸最終被右移) 右旋時,

轉軸的右孩子 = 樹的根節點;
   根節點的左孩子 = 轉軸的右子樹根節點;
   樹的根節點 = 轉軸;

左旋 (P為樹的根節點, Q為轉軸, 轉軸最終被左移) 左旋時,

轉軸的左孩子 = 樹的根節點;
   根節點的右孩子 = 轉軸的左子樹根節點;
   樹的根節點 = 轉軸;

中序不變 旋轉結束後二叉樹的中序始終不變, A<P<B<Q<C

二、簡介

AVL樹（Adelson-Velsky and Landis Tree）得名于它的發明者G. M. Adelson-Velsky和Evgenii Landis，他們在1962年的論文《An algorithm for the organization of information》中公開了這一資料結構。其實AVL就是在BST的基礎上增加了一個平衡(Balance)的屬性, 為的是穩固算法複雜度到 O(logn), BST算法複雜度受到樹結構的影響會遊離于 O(logn)~O(n) 之間, 而加入了平衡屬性之後則會降低到恒定為 O(logn)

三、基本特征

首先是 BST 的一種( BST 有的它都有)
是平衡二叉樹(根節點的平衡因子絕對值不大于1)
左右子樹也是平衡二叉樹

四、算法描述

插入, 删除之後

是否需要平衡

這個樹?

如何平衡

高度

為了判斷一個樹是否平衡? 引入了高度這個概念, 記錄從樹的最後一層到目前層數的距離

資料結構(二), AVL平衡二叉樹一、須知須會二、簡介三、基本特征四、算法描述五、完整代碼

是以我們的節點(Node)結構定義如下

public static class Node {
        private int data;
        private int height;
        private Node left;
        private Node right;
    }

旋轉

為了解決樹的平衡問題引入了樹的旋轉

資料結構(二), AVL平衡二叉樹一、須知須會二、簡介三、基本特征四、算法描述五、完整代碼

A, B, C, D代表

子節點

子樹

或者

null

左左 左節點的左節點/子樹導緻的不平衡, 需要 右旋

private Node rotateRight(Node root) {

        Node t = root.left;
        root.left = t.right;
        t.right = root;

        root.height = Math.max(height(root.left), height(root.right)) + 1;
        t.height = Math.max(height(t.left), height(t.right)) + 1;
        return t;
    }

右右

右節點的右節點/子樹導緻的不平衡, 需要

左旋

private Node rotateLeft(Node root) {

        Node t = root.right;
        root.right = t.left;
        t.left = root;

        root.height = Math.max(height(root.left), height(root.right)) + 1;
        t.height = Math.max(height(t.left), height(t.right)) + 1;
        return t;
    }

左右

左節點的右節點/子樹導緻的不平衡, 需要

左旋

右旋

private Node rotateLeftRight(Node root) {
        root.left = rotateLeft(root.left);
        return rotateRight(root);
    }

右左

右節點的左節點/子樹導緻的不平衡, 需要

右旋

左旋

private Node rotateRightLeft(Node root) {
        root.right = rotateRight(root.right);
        return rotateLeft(root);
    }

查找

和 BST 寫法一緻

先查找根節點,
< 根 , 則找左子樹;
> 根 , 則找右子樹;
= 根 , 則找到傳回;

public Node search(int num) {
        return doSearch(root, num);
    }

    private Node doSearch(Node root, int num) {
        if (root == null) {
            return null;
        }

        if (root.data == num) {
            return root;
        } else if (root.data > num) {
            return doSearch(root.left, num);
        } else if (root.data < num) {
            return doSearch(root.right, num);
        }
        return null;
    }

算法時間複雜度對于 n 個節點的樹

f(n) = 需要查找的次數 = 二叉樹的層數 ~= O(logn)

資料結構(二), AVL平衡二叉樹一、須知須會二、簡介三、基本特征四、算法描述五、完整代碼

插入

比對根節點, 小于就往左節點比對, 大于就往右節點比對
直到需要比對的節點為空, 而這個空就是你需要插入的位置
判斷樹是否平衡, 否, 則需要判斷旋轉類型并進行旋轉變換

public void insert(int num) {
        root = doInsert(root, num);
    }

    private Node doInsert(Node parent, int num) {
        if (parent == null) {
            parent = new Node(num);
        } else if (num > parent.data) {
            parent.right = doInsert(parent.right, num);

            // 判斷樹是否失衡
            if (height(parent.right) - height(parent.left) >= 2) {
                // '右右'
                if (num > parent.right.data) {
                    parent = rotateLeft(parent);
                }
                // '右左'
                else {
                    parent = rotateRightLeft(parent);
                }
            }

        } else if (num < parent.data) {
            parent.left = doInsert(parent.left, num);

            // 判斷樹是否失衡
            if (height(parent.left) - height(parent.right) >= 2) {
                // '左左'
                if (num < parent.left.data) {
                    parent = rotateRight(parent);
                }
                // '左右'
                else {
                    parent = rotateLeftRight(parent);
                }
            }
        }

        // 重新計算旋轉之後的高度
        parent.height = Math.max(height(parent.left), height(parent.right)) + 1;

        return parent;
    }

算法時間複雜度:

f(n) = 查找插入點的比對次數logn + 一次旋轉(單旋或者雙旋) + 判斷是否平衡 ~= O(logn)

旋轉的時間複雜度 O(1) 最多需要單旋或者雙旋, 另外, 判斷是否平衡的時間複雜度也是 O(1) ( 主要得益于 Node 使用了 height 記錄高度, 典型的空間換時間), 這樣總得算法複雜度還是比對的次數

資料結構(二), AVL平衡二叉樹一、須知須會二、簡介三、基本特征四、算法描述五、完整代碼

删除

先查找到目标節點
若: 目标左子樹為空, 則, 用目标右子樹根節點替換目标
若: 目标右子樹為空, 則, 用目标左子樹根節點替換目标
若: 都不為空, 則, 選取 左子樹值最大節點 或者 右子樹最小節點 替換目标, 并, 遞歸删除替換目标的節點
判斷樹是否平衡, 否, 則需要判斷旋轉類型并進行旋轉變換

public void remove(int num) {
        root = doRemove(root, num);
    }

    private Node doRemove(Node parent, int num) {

        if (parent == null) {
            return null;
        }

        if (num > parent.data) {
            parent.right = doRemove(parent.right, num);

            // 判斷樹是否平衡
            if (height(parent.left) - height(parent.right) >= 2) {
                Node t = parent.right;
                // `右左`
                if (t == null || height(t.right) < height(t.left)) {
                    parent = rotateRightLeft(parent);
                }
                // `右右`
                else {
                    parent = rotateLeft(parent);
                }
            }

        } else if (num < parent.data) {
            parent.left = doRemove(parent.left, num);

            // 判斷樹是否平衡
            if (height(parent.right) - height(parent.left) >= 2) {
                Node t = parent.left;
                // `左右`
                if (t == null || height(t.left) < height(t.right)) {
                    parent = rotateLeftRight(parent);
                }
                // `左左`
                else {
                    parent = rotateRight(parent);
                }
            }
        }
        // 找出左子樹最大的值或者右子樹最小的值替換, 這裡選擇前者來實作
        else if (parent.left != null && parent.right != null) {

            // 找到左子樹最大值替換
            parent.data = findMax(parent.left).data;
            // 删除左子樹中用于替換的節點
            parent.left = doRemove(parent.left, parent.data);
        }
        // 左子樹為空, 直接用右子樹根節點替換被删除的節點
        else if (parent.left == null) {
            parent = parent.right;
        }
        // 右子樹為空, 直接用左子樹根節點替換被删除的節點
        else if (parent.right == null) {
            parent = parent.left;
        }

        return parent;
    }

    private Node findMax(Node node) {
        if (node == null) {
            return node;
        }
        while (node.right != null) {
            node = node.right;
        }
        return node;
    }

算法複雜度:

f(n) = 需要比對的次數 = 查找到目标比對次數logn + 旋轉次數logn = O(2logn)

最多需要 logn 次旋轉, 來確定平衡, 是以最終的時間複雜度是 O(2logn)

資料結構(二), AVL平衡二叉樹一、須知須會二、簡介三、基本特征四、算法描述五、完整代碼

五、完整代碼

就一個AVLTree.java檔案搞定, 裡面還附有main()函數測試功能, 可直接運作github傳送門

資料結構(二), AVL平衡二叉樹一、須知須會二、簡介三、基本特征四、算法描述五、完整代碼

一、須知須會

二、簡介

三、基本特征

四、算法描述

高度

旋轉

查找

插入

删除

五、完整代碼

繼續閱讀

Android – ListView 中添加按鈕，動态删除添加ItemView的操作

C++ 第十五周報告1--《冒泡法排序》

Kotlin的ListView與RecyclerView的簡單應用

關于公司的那些坑：Android Studio篇

android SQLite事務和kotlin協程

筆試面試題目：滑動視窗(二)

無法正常編譯錯誤Compilation failed to complete

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

關于Gradle配置的小結

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Android APK檔案反編譯Android APK檔案反編譯

Linux裝置模型（中）之上層容器

hdu7108哈希