Số lượng nút tối thiểu trong Cây AVL với chiều cao đã cho bằng cách sử dụng C ++.

Tuyên bố vấn đề

Với chiều cao của cây AVL, nhiệm vụ là tìm số nút tối thiểu mà cây có thể có.

If height = 0 then AVL tree can have one 1 node
If height = 5 then AVL tree can have minimum 20 nodes

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à sự khác biệt về chiều cao của cây con bên trái và bên phải không được nhiều hơn -1, 0 hoặc 1 cho mỗi nút. Sử dụng thuộc tính này, chúng tôi có thể tạo quan hệ lặp lại bên dưới -

1. If height = 0 then return 1
2. If height = 1 then return 2
3. If height > 1 then return (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;
}

Đầu ra

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