Trong các phần trước, chúng ta đã thấy rằng 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 bị mất cân bằng. 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ây AVL là một loại cây cân bằng, đượ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à cây con bên phải. Đôi khi k được gọi là balance factor (hệ số cân bằng).
Các tính chất của cây AVL
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.
Số lượng node tối thiểu/tối đa trong cây AVL
Để đơ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à:
N(h) = N(h - 1) + N(h - 1) + 1 = 2N(h - 1) + 1
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.
- "1" biểu thị node hiện tại.
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
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).
Khai báo cây AVL
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 cây AVL
public int Height(AVLTreeNode root){
if(root == null){
return -1;
} else {
return root.getHeight();
}
}Xoay vòng (Rotations)
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 các phép xoay đơn hoặc xoay 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 cây con bên trái(X) và cây con bên phải(X) khác nhau chính xác 2. Xoay vòng 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 xoay 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:
- Chèn vào cây con trái của node trái của X.
- Chèn vào cây con phải của node trái của X.
- Chèn vào cây con bên trái của node phải của X.
- 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 xoay đơ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 xoay kép (cần hai phép xoay đơn).
Phép xoay đơ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ụ, 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 phép xoay trái trái duy nhất ở 9. Kết quả là chúng ta có được 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;
}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 cây AVL.
Ví dụ, 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 xoay phải phải duy nhất ở mức 15. Kết quả là chúng ta có được 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;
}Phép xoay kép
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 xoay.
Ví dụ, chúng ta hãy xem xét cây sau: 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 xoay kép.
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 xoay để 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 xoay kép.
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();
}
}
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é.
Đánh giá
Cây AVL là một giải pháp tối ưu cho việc tìm kiếm dữ liệu. Với việc giới hạn độ cao của cây và áp dụng các phép xoay phù hợp, cây AVL đảm bảo tìm kiếm với độ phức tạp O(logn) trong trường hợp xấu nhất. Điều này giúp tăng hiệu suất và cải thiện trải nghiệm người dùng.
Hãy thử áp dụng cây AVL vào các ứng dụng tìm kiếm của bạn để tận hưởng những lợi ích của việc tối ưu hóa này.