Cây AVL *

Trong phần "Cây tìm kiếm nhị phân" (Binary Search Tree), chúng ta đã đề cập rằng sau nhiều thao tác chèn và xóa, cây tìm kiếm nhị phân có thể bị suy biến thành một danh sách liên kết. Trong trường hợp này, độ phức tạp thời gian của tất cả các thao tác sẽ giảm từ \(O(\log n)\) xuống \(O(n)\).

Như được minh họa trong hình dưới đây, sau hai thao tác xóa nút, cây tìm kiếm nhị phân này sẽ suy biến thành một danh sách liên kết.

Ví dụ, trong cây nhị phân hoàn hảo (perfect binary tree) được minh họa ở hình dưới đây, sau khi chèn hai nút, cây sẽ bị lệch nhiều sang bên trái, và độ phức tạp thời gian của thao tác tìm kiếm cũng sẽ bị suy biến.

Vào năm 1962, G. M. Adelson-Velsky và E. M. Landis đã đề xuất cây AVL (AVL tree) trong bài báo khoa học "An algorithm for the organization of information". Bài báo mô tả một loạt các thao tác giúp ngăn chặn cây AVL bị suy biến khi các nút được chèn và xóa, từ đó duy trì độ phức tạp thời gian của các thao tác khác nhau ở mức \(O(\log n)\). Nói cách khác, trong các tình huống yêu cầu thực hiện thường xuyên các thao tác chèn, xóa, tìm kiếm và cập nhật, cây AVL có thể duy trì hiệu suất hiệu quả một cách nhất quán và do đó có giá trị thực tiễn rất cao.

Thuật ngữ thường gặp trong cây AVL

Cây AVL vừa là cây tìm kiếm nhị phân vừa là cây nhị phân cân bằng, đồng thời thỏa mãn tất cả các thuộc tính của hai loại cây nhị phân này, do đó nó là một cây tìm kiếm nhị phân cân bằng (balanced binary search tree).

Chiều cao nút

Vì các thao tác liên quan đến cây AVL yêu cầu lấy chiều cao của nút, chúng ta cần thêm một biến height vào lớp (class) nút:

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

class TreeNode:
    """Nút cây AVL"""
    def __init__(self, val: int):
        self.val: int = val                 # Giá trị nút
        self.height: int = 0                # Chiều cao nút
        self.left: TreeNode | None = None   # Tham chiếu con bên trái
        self.right: TreeNode | None = None  # Tham chiếu con bên phải

/* Nút cây AVL */
struct TreeNode {
    int val{};          // Giá trị nút
    int height = 0;     // Chiều cao nút
    TreeNode *left{};   // Con bên trái
    TreeNode *right{};  // Con bên phải
    TreeNode() = default;
    explicit TreeNode(int x) : val(x){}
};

/* Nút cây AVL */
class TreeNode {
    public int val;        // Giá trị nút
    public int height;     // Chiều cao nút
    public TreeNode left;  // Con bên trái
    public TreeNode right; // Con bên phải
    public TreeNode(int x) { val = x; }
}

/* Nút cây AVL */
class TreeNode(int? x) {
    public int? val = x;    // Giá trị nút
    public int height;      // Chiều cao nút
    public TreeNode? left;  // Tham chiếu con bên trái
    public TreeNode? right; // Tham chiếu con bên phải
}

/* Nút cây AVL */
type TreeNode struct {
    Val    int       // Giá trị nút
    Height int       // Chiều cao nút
    Left   *TreeNode // Tham chiếu con bên trái
    Right  *TreeNode // Tham chiếu con bên phải
}

/* Nút cây AVL */
class TreeNode {
    var val: Int // Giá trị nút
    var height: Int // Chiều cao nút
    var left: TreeNode? // Con bên trái
    var right: TreeNode? // Con bên phải

    init(x: Int) {
        val = x
        height = 0
    }
}

/* Nút cây AVL */
class TreeNode {
    val; // Giá trị nút
    height; // Chiều cao nút
    left; // Con trỏ con bên trái
    right; // Con trỏ con bên phải
    constructor(val, left, right, height) {
        this.val = val === undefined ? 0 : val;
        this.height = height === undefined ? 0 : height;
        this.left = left === undefined ? null : left;
        this.right = right === undefined ? null : right;
    }
}

/* Nút cây AVL */
class TreeNode {
    val: number;            // Giá trị nút
    height: number;         // Chiều cao nút
    left: TreeNode | null;  // Con trỏ con bên trái
    right: TreeNode | null; // Con trỏ con bên phải
    constructor(val?: number, height?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val === undefined ? 0 : val;
        this.height = height === undefined ? 0 : height; 
        this.left = left === undefined ? null : left; 
        this.right = right === undefined ? null : right; 
    }
}

/* Nút cây AVL */
class TreeNode {
  int val;         // Giá trị nút
  int height;      // Chiều cao nút
  TreeNode? left;  // Con bên trái
  TreeNode? right; // Con bên phải
  TreeNode(this.val, [this.height = 0, this.left, this.right]);
}

use std::rc::Rc;
use std::cell::RefCell;

/* Nút cây AVL */
struct TreeNode {
    val: i32,                               // Giá trị nút
    height: i32,                            // Chiều cao nút
    left: Option<Rc<RefCell<TreeNode>>>,    // Con bên trái
    right: Option<Rc<RefCell<TreeNode>>>,   // Con bên phải
}

impl TreeNode {
    /* Hàm khởi tạo */
    fn new(val: i32) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(Self {
            val,
            height: 0,
            left: None,
            right: None
        }))
    }
}

/* Nút cây AVL */
typedef struct TreeNode {
    int val;
    int height;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

/* Hàm khởi tạo */
TreeNode *newTreeNode(int val) {
    TreeNode *node;

    node = (TreeNode *)malloc(sizeof(TreeNode));
    node->val = val;
    node->height = 0;
    node->left = NULL;
    node->right = NULL;
    return node;
}

/* Nút cây AVL */
class TreeNode(val _val: Int) {  // Giá trị nút
    val height: Int = 0          // Chiều cao nút
    val left: TreeNode? = null   // Con bên trái
    val right: TreeNode? = null  // Con bên phải
}

### Lớp nút cây AVL ###
class TreeNode
  attr_accessor :val    # Giá trị nút
  attr_accessor :height # Chiều cao nút
  attr_accessor :left   # Tham chiếu con bên trái
  attr_accessor :right  # Tham chiếu con bên phải

  def initialize(val)
    @val = val
    @height = 0
  end
end

"Chiều cao nút" (node height) là khoảng cách từ nút đó đến nút lá xa nhất của nó, tức là số lượng cạnh trên đường đi. Cần lưu ý rằng chiều cao của một nút lá là \(0\), và chiều cao của một nút rỗng (null node) là \(-1\). Chúng ta sẽ tạo hai hàm tiện ích để lấy và cập nhật chiều cao của một nút:

[file]{avl_tree}-[class]{avl_tree}-[func]{update_height}

Hệ số cân bằng nút

Hệ số cân bằng (balance factor) của một nút được định nghĩa là chiều cao của cây con bên trái của nút đó trừ đi chiều cao của cây con bên phải của nó, và hệ số cân bằng của một nút rỗng được định nghĩa là \(0\). Chúng ta cũng đóng gói hàm để lấy hệ số cân bằng của nút nhằm thuận tiện cho việc sử dụng sau này:

[file]{avl_tree}-[class]{avl_tree}-[func]{balance_factor}

Tip

Giả sử hệ số cân bằng là \(f\), khi đó hệ số cân bằng của bất kỳ nút nào trong cây AVL đều thỏa mãn \(-1 \le f \le 1\).

Phép xoay trong cây AVL

Đặc trưng của cây AVL nằm ở phép "xoay" (rotation), nó có thể khôi phục lại trạng thái cân bằng cho các nút mất cân bằng mà không làm ảnh hưởng đến thứ tự duyệt trung thứ tự (inorder traversal) của cây nhị phân. Nói cách khác, các phép xoay vừa có thể duy trì thuộc tính của một "cây tìm kiếm nhị phân", vừa giúp cây trở lại thành một "cây nhị phân cân bằng".

Chúng ta gọi những nút có giá trị tuyệt đối của hệ số cân bằng \(> 1\) là "các nút mất cân bằng" (unbalanced nodes). Tùy thuộc vào trạng thái mất cân bằng, các phép xoay được chia làm bốn loại: xoay phải (right rotation), xoay trái (left rotation), xoay phải rồi xoay trái (right-left rotation), và xoay trái rồi xoay phải (left-right rotation). Dưới đây chúng ta sẽ mô tả chi tiết các phép xoay này.

Phép xoay phải

Như được minh họa trong hình dưới đây, giá trị nằm dưới nút là hệ số cân bằng. Từ dưới lên trên, nút mất cân bằng đầu tiên trong cây nhị phân là "nút 3". Chúng ta tập trung vào cây con có gốc là nút mất cân bằng này, ký hiệu nút đó là node và nút con bên trái của nó là child, rồi thực hiện thao tác "xoay phải". Sau khi xoay phải hoàn tất, cây con sẽ lấy lại thăng bằng và vẫn duy trì được các thuộc tính của một cây tìm kiếm nhị phân.

<1><2><3><4>

Như được minh họa trong hình dưới đây, khi nút child có một con bên phải (ký hiệu là grand_child), một bước cần được thêm vào trong phép xoay phải: đặt grand_child làm con bên trái của node.

"Xoay phải" chỉ là một thuật ngữ mang tính hình tượng; trên thực tế, nó được thực hiện bằng cách sửa đổi các con trỏ hoặc tham chiếu của nút, như được thể hiện trong mã nguồn dưới đây:

[file]{avl_tree}-[class]{avl_tree}-[func]{right_rotate}

Phép xoay trái

Tương tự như vậy, nếu chúng ta xét trường hợp "đối xứng" (mirror) của cây nhị phân mất cân bằng ở trên, ta cần thực hiện thao tác "xoay trái" như minh họa trong hình dưới đây.

Tương tự, như được minh họa trong hình dưới đây, khi nút child có một con bên trái (ký hiệu là grand_child), một bước cần được thêm vào trong phép xoay trái: đặt grand_child làm con bên phải của node.

Có thể thấy rằng các thao tác xoay phải và xoay trái có tính chất đối xứng gương về mặt logic, và hai trường hợp mất cân bằng mà chúng giải quyết cũng đối xứng nhau. Dựa trên tính đối xứng này, chúng ta chỉ cần thay thế tất cả left trong mã nguồn triển khai xoay phải bằng right, và tất cả right bằng left để thu được mã nguồn triển khai cho xoay trái:

[file]{avl_tree}-[class]{avl_tree}-[func]{left_rotate}

Phép xoay trái rồi xoay phải

Đối với nút mất cân bằng 3 trong hình dưới đây, nếu chỉ sử dụng riêng lẻ phép xoay trái hoặc xoay phải thì không thể khôi phục lại trạng thái cân bằng cho cây con. Trong trường hợp này, trước tiên ta cần thực hiện "xoay trái" đối với nút child, sau đó thực hiện "xoay phải" đối với nút node.

Phép xoay phải rồi xoay trái

Như được minh họa trong hình dưới đây, đối với trường hợp đối xứng của cây nhị phân mất cân bằng ở trên, trước tiên ta cần thực hiện "xoay phải" đối với nút child, sau đó thực hiện "xoay trái" đối với nút node.

Lựa chọn phép xoay

Bốn loại mất cân bằng được mô tả trong hình dưới đây tương ứng một-đối-một với các trường hợp nêu trên, lần lượt yêu cầu các thao tác xoay phải, xoay trái rồi xoay phải, xoay phải rồi xoay trái, và xoay trái.

Như bảng dưới đây, chúng ta xác định nút mất cân bằng thuộc trường hợp nào bằng cách đánh giá dấu của hệ số cân bằng của chính nút đó và hệ số cân bằng của nút con ở phía cao hơn của nó.

Bảng   Điều kiện lựa chọn giữa bốn trường hợp xoay

Hệ số cân bằng của nút mất cân bằng	Hệ số cân bằng của nút con	Phương pháp xoay cần áp dụng
\(> 1\) (cây lệch trái)	\(\geq 0\)	Xoay phải
\(> 1\) (cây lệch trái)	\(<0\)	Xoay trái rồi xoay phải
\(< -1\) (cây lệch phải)	\(\leq 0\)	Xoay trái
\(< -1\) (cây lệch phải)	\(>0\)	Xoay phải rồi xoay trái

Để thuận tiện cho việc sử dụng, chúng ta đóng gói các thao tác xoay vào một hàm. Với hàm này, chúng ta có thể thực hiện xoay cho các tình huống mất cân bằng khác nhau, khôi phục lại trạng thái cân bằng cho các nút mất cân bằng. Mã nguồn như sau:

[file]{avl_tree}-[class]{avl_tree}-[func]{rotate}

Các thao tác thường gặp trên cây AVL

Chèn nút

Thao tác chèn nút trong cây AVL về mặt nguyên lý tương tự như trong cây tìm kiếm nhị phân. Điểm khác biệt duy nhất là sau khi chèn một nút vào cây AVL, một loạt các nút mất cân bằng có thể xuất hiện trên đường đi từ nút đó đến gốc. Do đó, chúng ta cần bắt đầu từ nút này và thực hiện các phép xoay từ dưới lên trên để khôi phục trạng thái cân bằng cho tất cả các nút bị mất cân bằng. Mã nguồn như sau:

[file]{avl_tree}-[class]{avl_tree}-[func]{insert_helper}

Xóa nút

Tương tự, trên cơ sở của phương pháp xóa nút trong cây tìm kiếm nhị phân, các phép xoay cần được thực hiện từ dưới lên trên để khôi phục lại trạng thái cân bằng cho tất cả các nút mất cân bằng. Mã nguồn như sau:

[file]{avl_tree}-[class]{avl_tree}-[func]{remove_helper}

Tìm kiếm nút

Thao tác tìm kiếm nút trong cây AVL hoàn toàn thống nhất với thao tác này trong cây tìm kiếm nhị phân, và sẽ không được trình bày chi tiết ở đây.

Ứng dụng điển hình của cây AVL

• Tổ chức và lưu trữ dữ liệu quy mô lớn, thích hợp cho các tình huống có tần suất tìm kiếm cao và tần suất chèn/xóa thấp.
• Được sử dụng để xây dựng hệ thống chỉ mục (index system) trong các cơ sở dữ liệu.
• Cây đỏ-đen (red-black tree) cũng là một loại cây tìm kiếm nhị phân cân bằng phổ biến. So với cây AVL, cây đỏ-đen có điều kiện cân bằng lỏng lẻo hơn, yêu cầu ít thao tác xoay hơn khi chèn và xóa nút, và có hiệu suất trung bình cao hơn đối với các thao tác thêm và xóa nút.