Đề bài
Cho chiều cao của một cây AVL, nhiệm vụ là tìm số nút tối thiểu mà cây có thể có.
Nếu height = 0 thì cây AVL có thể có 1 nút Nếu height = 5 thì cây AVL có thể có tối thiểu 20 nút
Thuật toán
Trong cây AVL, chúng ta phải duy trì thuộc tính cân bằng chiều cao, tức là chênh lệch chiều cao của cây con trái và cây con phải không thể lớn hơn -1, 0 hoặc 1 cho mỗi nút. Sử dụng thuộc tính này, ta có thể tạo ra quan hệ truy hồi sau:
1. Nếu height = 0 thì trả về 1 2. Nếu height = 1 thì trả về 2 3. Nếu height > 1 thì trả về (1 + getMinAVLNodes(h – 1) + getMinAVLNodes(h – 2))
Ví dụ
#include <iostream> using namespace std; int getMinAVLNodes(int h){ if (h < 0) { return 0; } if (h == 0 || h == 1) { return h + 1; } return 1 + getMinAVLNodes(h - 1) + getMinAVLNodes(h -2); } int main(){ int h = 5; cout << "Minimum nodes for " << h << " height = " << getMinAVLNodes(h) << endl; return 0; }
Kết quả
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau:
Minimum nodes for 5 height = 20