Định nghĩa :
Một cây nhị phân tìm kiếm cân bằng ( AVL Trees ) bao gồm những yếu tố :

• Chiều cao cây con trái và cây con phải của gốc cây cha  phải chênh lệch nhau không quá 1

• Bản thân cây con trái và cây con phải cũng là cây AVL

Ta kí hiệu chiều cao cây con trái cao hơn là / , chiều cao cây con phải cao hơn là : \ và chiều cao 2 cây con bằng nhau là _ , ta sẽ có vài ví dụ như sau :

 

 Cây AVL với chiều cao h :

Chiều cao lớn nhất của cây nhị phân AVL :

Chiều cao lớn nhất của cây AVL có chính xác là n nút ? Để trả lời câu hỏi này, ta hãy xem xét bên dưới.

Gọi F_h là cây nhị phân AVL có chiều cao là h có số nút ít nhất, F_l, F_r lần lượt là cây con trái và phải tương ứng của cây Fh, khi đó F_l hoặc F_r phải có chiều cao là h-2/

Giả sử cây F_l có chiều cao h-1, và F_r có chiều cao là h-2. Lưu ý F_l là cây AVL có số nút ít nhất trong số các cây AVL có chiều cao h-1, tương tự thì F_r có số nút nhỏ nhất trong số các cây AVL có chiều cao h-2. Như vậy ta có:

| F_h| = | F_{h - 1}| + | F_{h - 2}| + 1

trong đó | F_h|  biểu thị số nút của F_h, cây AVL cực tiểu còn gọi là là cây Fibonacci, | F₀| = 1 và | F₁| =2 . Thêm 1 vào cả 2 bên ta được :

| F_h| + 1 = (| F_{h - 1}| + 1) + (| F_{h - 2}| + 1)

 như cậy | F_h| + 1 là số Fibonacci, sử dụng công thức gần đúng của số Fibonacci ta sẽ có :

| F_h| + 1 

=> h  1.44log| F_n|
=> Với cây AVL có n nút, chiều cao là :     h 1.44log n
=> Chiều cao tệ nhất của cây AVL với n nút là  h 1.44log n

 

[Ðọc chi tiết...]

0 Hướng dẫn tạo ảnh profile Google Plus độc đáo giống Facebook

Nếu bạn đã sử dụng facebook thì cách sắp xếp hình ảnh dạng lát gạch rất quen thuộc phải không nào. Sau đây mình sẽ hướng dẫn bạn tạo một profile Google Plus ấn tượng nhưng cực kì đơn giản.
Yêu cầu: bạn phải có Photoshop.

[Ðọc chi tiết...]

0 10 Lý do nên dùng Google Plus thay cho Facebook

Mới xuất hiện chỉ một tuần trở lại đây nhưng Google Plus đã tạo nên một cơn sốt lan tỏa khắp thế giới. Với khẩu hiệu “Chia sẻ giống như đời thực, tư duy lại cho web” Google Plus hứa hẹn nhiều điều thú vị. Trong bài này, Mình xin đề cập 10 lý do bạn nên sử dụng Google Plus (Google+)

[Ðọc chi tiết...]

1 Cách làm gọn đường link Google Plus Profile

Hiện tại Google Plus cấp cho chúng ta đường link tới Profile (Trang cá nhân trên Google Plus) rất dài và “xấu xí” : https://plus.google.com/113345859580051607251/posts.

[Ðọc chi tiết...]

0 Cách thay đổi kiểu chữ Google Plus

Để thay đổi kiểu chữ cho đoạn text như In đậm, In nghiêng, Gạch chân, Gạch ngang  trong Google+ chúng ta dùng các quy ước như sau:

[Ðọc chi tiết...]

0 Sử dụng phím tắt trong Google Plus ( Đầy đủ nhất)

Xin chia sẻ với các bạn những phím tắt thông dụng khi dùng Google Plus (G+):

[Ðọc chi tiết...]

0 Hướng dẫn các chuyển nhà từ Facebook sang Google Plus

Vậy là sau một thời gian tìm hiểu Google Plus và các thủ thuật cơ bản , nếu có ý định “chuyển nhà” hẳn sang Google Plus (Google+) nhưng bạn vẫn băn khoăn vì còn rất nhiều hình ảnh , bạn bè , dữ liệu … trên Facebook. ThuthuatGoogle sẽ hướng dẫn các bạn “dọn nhà” một cách đầy đủ nhất từ Facebook sang Google Plus.

[Ðọc chi tiết...]