Cách tạo cây AVL bị lệch càng tốt?

Question

Tôi đã thấy điều này trong một số bài báo và một người nào đó cho rằng có thể có nhiều nhất thời gian đăng nhập (n) khi chúng ta xóa một nút của cây AVL. Tôi tin rằng chúng ta có thể đạt được điều này bằng cách tạo ra một cây AVL càng lệch càng tốt. Vấn đề là làm thế nào để làm điều này. Điều này sẽ giúp tôi rất nhiều về việc nghiên cứu điều xoay vòng loại bỏ. Cảm ơn rất nhiều!

Answer 1

Nếu bạn muốn thực hiện một cây AVL tối đa lệch, bạn đang tìm kiếm một Fibonacci tree, được định nghĩa quy nạp như sau:

• Một Fibonacci cây trật tự 0 là trống rỗng.
• Một cây Fibonacci theo thứ tự 1 là một nút duy nhất.
• Một Fibonacci cây trật tự n + 2 là một nút có con trái là một cây Fibonacci trật tự n và có quyền trẻ em là một cây Fibonacci trật tự n + 1.

Ví dụ, đây là một Fibonacci cây trật tự 5:

các cây Fibonacci đại diện cho số tiền tối đa nghiêng rằng một cây AVL có thể có, vì nếu các yếu tố cân bằng là bất kỳ lệch nhiều yếu tố cân bằng của mỗi nút sẽ vượt quá các giới hạn đặt bởi cây AVL.

Bạn có thể sử dụng định nghĩa này đến rất dễ dàng tạo ra cây AVL tối đa lệch:

function FibonacciTree(int order) { 
    if order = 0, return the empty tree. 
    if order = 1, create a single node and return it. 
    otherwise: 
     let left = FibonacciTree(order - 2) 
     let right = FibonacciTree(order - 1) 
     return a tree whose left child is "left" and whose right child is "right." 

Hope this helps!