6.10 Balanced Binary Search Trees

Trong các phần trước, chúng ta đã thấy các cây khác nhau có độ phức tạp trong trường hợp xấu nhất là O(n), trong đó n là số node trong cây. Điều này xảy ra khi cây xiên. Trong phần này, chúng ta sẽ cố gắng giảm độ phức tạp trong trường hợp xấu nhất này xuống O(logn) bằng cách áp đặt các hạn chế về độ cao.

Nói chung, các cây cân bằng chiều cao được biểu diễn bằng HB(k), trong đó k là hiệu giữa chiều cao cây con bên trái và chiều cao cây con bên phải. Đôi khi k được gọi là balance factor(hệ số cân bằng).

Full Balanced Binary Search Trees Trong HB(k), nếu k = 0 (nếu hệ số cân bằng bằng 0) thì ta gọi cây nhị phân tìm kiếm đó là full balanced binary search trees(cây nhị phân tìm kiếm cân bằng đầy đủ.) Điều đó có nghĩa là, trong cây tìm kiếm nhị phân HB(0), chênh lệch giữa chiều cao cây con bên trái và chiều cao cây con bên phải tối đa bằng 0. Điều này đảm bảo rằng cây là một cây nhị phân đầy đủ. Ví dụ,

6.11 AVL (Adelson-Velskii and Landis) Trees

Trong HB(k), nếu k = 1 (nếu hệ số cân bằng là một) thì cây tìm kiếm nhị phân như vậy được gọi là cây AVL. Điều đó có nghĩa là cây AVL là cây tìm kiếm nhị phân với điều kiện cân bằng: sự khác biệt giữa chiều cao cây con bên trái và chiều cao cây con bên phải nhiều nhất là 1.

Các tính chất của AVL Trees

Cây nhị phân được gọi là cây AVL nếu:

• Nó là một cây tìm kiếm nhị phân
• Và đối với bất kỳ node X nào, chiều cao của cây con bên trái của X và chiều cao của cây con bên phải của X khác nhau nhiều nhất là 1.

Ví dụ, trong số các cây tìm kiếm nhị phân sau đây, cây bên trái không phải là cây AVL, trong khi cây tìm kiếm nhị phân bên phải là cây AVL.

Số lượng node tối thiểu/tối đa trong AVL Tree

Để đơn giản, chúng ta hãy giả sử rằng chiều cao của cây AVL là h và N(h) biểu thị số node trong cây AVL có chiều cao h. Để có số node tối thiểu có chiều cao h, chúng ta nên lấp đầy cây bằng số node tối thiểu có thể. Điều đó có nghĩa là nếu chúng ta điền vào cây con bên trái với chiều cao h – 1 thì chúng ta nên điền vào cây con bên phải với chiều cao h – 2. Kết quả là số node tối thiểu có chiều cao h là:

Trong phương trình trên:

• N(h – 1) cho biết số node tối thiểu có chiều cao h – 1.
• N(h – 2) biểu thị số node tối thiểu có chiều cao h – 2.
• Trong biểu thức trên, “1” biểu thị node hiện tại.

Chúng ta có thể cho N(h – 1) cho cây con bên trái hoặc cây con bên phải. Giải quyết sự đệ quy ở trên ta có(Các bạn có thể xem lại cách chứng minh ở đây):

Trong đó n là số node trong cây AVL. Ngoài ra, chiều cao tối đa trong cây AVL là O(logn).

Tương tự, để có số node tối đa, chúng ta cần điền vào cả hai cây con bên trái và bên phải với chiều cao h – 1. Kết quả là, chúng ta có $N(h) = N(h – 1) + N(h – 1) + 1 = 2N(h – 1) + 1$. Biểu thức trên xác định trường hợp cây nhị phân đầy đủ. Giải quyết sự đệ quy ở trên ta có:

Trong cả hai trường hợp, thuộc tính cây AVL đảm bảo rằng chiều cao của cây AVL có n node là O(logn).

AVL Tree Declaration

public class AVLTreeNode { private int data, height; private AVLTreeNode left, right; public int getData() { return data; } public void setData(int data) { this.data = data; } public int getHeight() { return height; } public void setHeight(int height) { this.height = height; } public AVLTreeNode getLeft() { return left; } public void setLeft(AVLTreeNode left) { this.left = left; } public AVLTreeNode getRight() { return right; } public void setRight(AVLTreeNode right) { this.right = right; }
}

Tìm chiều cao của AVL tree

	public int Height(AVLTreeNode root){ if(root == null){ return - 1; } else { return root.getHeight(); } }

Rotations(Xoay vòng)

Khi cấu trúc cây thay đổi (ví dụ: chèn hoặc xóa), chúng ta cần sửa đổi cây để khôi phục thuộc tính cây AVL. Điều này có thể được thực hiện bằng cách sử dụng single rotations(phép quay đơn) hoặc double rotations(phép quay kép). Vì thao tác chèn/xóa liên quan đến việc thêm/xóa một node, nên thao tác này chỉ có thể tăng/giảm chiều cao của cây con đi 1.

Vì vậy, nếu thuộc tính cây AVL bị vi phạm tại node X, điều đó có nghĩa là độ cao của trái(X) và phải(X) khác nhau chính xác 2. Điều này là do, nếu chúng ta cân bằng cây AVL mỗi lần, thì tại bất kỳ thời điểm nào, sự khác biệt về độ cao của trái(X) và phải(X) khác nhau chính xác 2. Rotations là kỹ thuật được sử dụng để khôi phục thuộc tính cây AVL. Điều này có nghĩa là, chúng ta cần áp dụng các phép quay cho node X.

Quan sát: Một quan sát quan trọng là, sau khi chèn, chỉ các node nằm trên đường dẫn từ điểm chèn đến gốc mới có thể bị thay đổi số dư, bởi vì chỉ những node đó mới bị thay đổi cây con của chúng. Để khôi phục thuộc tính cây AVL, chúng ta bắt đầu tại điểm chèn và tiếp tục đi tới gốc của cây.

Trong khi di chuyển đến gốc, chúng ta cần xem xét node đầu tiên không thỏa mãn thuộc tính AVL. Từ node đó trở đi, mọi node trên đường dẫn đến thư mục gốc sẽ gặp sự cố(Không còn thỏa mãn tính chất cây AVL).

Ngoài ra, nếu chúng ta khắc phục sự cố cho node đầu tiên đó, thì tất cả các node khác trên đường dẫn đến gốc sẽ tự động đáp ứng thuộc tính cây AVL. Điều đó có nghĩa là chúng ta luôn cần quan tâm đến node đầu tiên không thỏa mãn thuộc tính AVL trên đường dẫn từ điểm chèn đến gốc và sửa nó.

Các loại vi phạm

Giả sử node phải được cân bằng lại là X. Vì bất kỳ node nào cũng có nhiều nhất hai node con và sự mất cân bằng chiều cao đòi hỏi chiều cao của hai cây con của X phải khác nhau hai, chúng ta có thể dễ dàng quan sát thấy rằng vi phạm có thể xảy ra trong bốn trường hợp:

1. Chèn vào cây con trái của node trái của X.
2. Chèn vào cây con phải của node trái của X.
3. Chèn vào cây con bên trái của node phải của X.
4. Chèn vào cây con bên phải của node phải của X.

Trường hợp 1 và 4 là đối xứng và dễ dàng giải quyết bằng các phép quay đơn. Tương tự, trường hợp 2 và 3 cũng đối xứng và có thể giải bằng phép quay kép (cần hai phép quay đơn).

Single Rotations(Phép quay đơn)

Left Left Rotation (LL Rotation) [Case-1]: Trong trường hợp bên dưới, node X không thỏa mãn thuộc tính cây AVL. Như đã thảo luận trước đó, việc xoay vòng không nhất thiết phải được thực hiện ở gốc của cây. Nói chung, chúng ta bắt đầu tại node được chèn và đi lên cây, cập nhật thông tin số dư tại mọi node trên đường dẫn. Ví dụ, trong hình bên dưới, sau khi chèn 7 vào cây AVL ban đầu ở bên trái, node 9 trở nên mất cân bằng. Vì vậy, chúng ta thực hiện một single left-left rotation duy nhất ở 9. Kết quả là chúng ta có được cái cây bên phải.

	public AVLTreeNode SingleRotateLeft(AVLTreeNode X){ AVLTreeNode W = X.getLeft(); W.setRight(X); X.setHeight(Math.max(Height(X.getLeft()), Height(X.getRight())) + 1); W.setHeight(Math.max(Height(W.getLeft()), X.getHeight()) + 1); return W; }

Time Complexity: O(1). Space Complexity: O(1).

Right Right Rotation (RR Rotation) [Case-4]: Trong trường hợp này, node X không thỏa mãn thuộc tính AVLtree.

Ví dụ, trong hình trên, sau khi chèn 29 vào cây AVL ban đầu ở bên trái, node 15 trở nên mất cân bằng. Vì vậy, chúng ta thực hiện một phép quay single right-right rotation duy nhất ở mức 15. Kết quả là chúng ta có được cái cây ở bên phải.

	public AVLTreeNode SingleRotateRight(AVLTreeNode W){ AVLTreeNode X = W.getRight(); W.setRight(X.getLeft()); X.setLeft(W); W.setHeight(Math.max(Height(W.getRight()), Height(W.getLeft())) + 1); X.setHeight(Math.max(Height(X.getRight()), W.getHeight()) + 1); return X; }

Time Complexity: O(1). Space Complexity: O(1).

Double Rotations(Phép quay đôi)

Left Right Rotation (LR Rotation) [Case-2]: Đối với trường hợp-2 và trường hợp-3, xoay một lần không khắc phục được sự cố. Chúng ta cần thực hiện hai phép quay.

Ví dụ, chúng ta hãy xem xét cây trên: Việc chèn 7 đang tạo ra kịch bản trường hợp-2 và cây bên phải là cây sau khi thực hiện phép quay đôi.

	public AVLTreeNode DoubleRotatewithLeft(AVLTreeNode Z){ Z.setLeft(SingleRotateRight(Z.getLeft())); return SingleRotateLeft(Z); }

Right Left Rotation (RL Rotation) [Case-3]: Tương tự như trường hợp 2, chúng ta cần thực hiện hai phép quay để khắc phục tình huống này.

Ví dụ, chúng ta hãy xem xét cây sau: Việc chèn 6 đang tạo ra kịch bản trường hợp-3 và cây bên phải là cây sau khi thực hiện phép quay đôi.

Thêm phần từ vào cây AVL

Chèn vào cây AVL tương tự như chèn BST. Sau khi chèn phần tử, chúng ta chỉ cần kiểm tra xem có bất kỳ sự mất cân bằng chiều cao nào không. Nếu có sự mất cân bằng, hãy gọi các hàm xoay thích hợp.

	public AVLTreeNode insert(AVLTreeNode root, int data){ if(root == null){ root = new AVLTreeNode(); root.setData(data); root.setHeight(0); root.setLeft(null); root.setRight(null); return root; } else if (data < root.getData()) { root.setLeft(insert(root.getLeft(), data)); if(Height(root.getLeft()) - Height(root.getRight()) == 2){ if (data < root.getLeft().getData()){ root = SingleRotateLeft(root); } else { root = DoubleRotatewithLeft(root); } } } else if (data > root.getData()) { root.setRight(insert(root.getRight(), data)); if (data < root.getRight().getData()) { root = SingleRotateRight(root); } else { root = DoubleRotatewithRight(); } } //Else data is in the tree already. We'll do nothing root.setHeight(Math.max(Height(root.getLeft()), Height(root.getRight())) + 1); return root; }

Đây là code của tác giả, mình thấy thiếu return nếu root bằng null và thừa tham số thứ 2 parent không dùng tới nên mình đã bỏ đi, các bạn xem thấy nếu chưa đúng comment giúp mình nhé.

Time Complexity: O(logn). Space Complexity: O(logn).