Chứng minh số lượng tối đa quay cho hai cây để trở thành bình đẳng

Question

Trong cuốn sách Giới thiệu về thuật toán - Cách tiếp cận sáng tạo, Câu hỏi 4,24:

Hãy T1 và T2 là hai cây tùy ý, mỗi n có nút . Chứng minh rằng nó đủ để áp dụng tối đa 2n vòng quay đến T1, sao cho nó trở thành bằng T2.

Đối với cây tìm kiếm nhị phân, tôi đã tìm ra một thuật toán:

1. Tìm các yếu tố tương đương với gốc T2 của, chúng ta hãy gọi nó là nhắm mục tiêu-root.

2. Sử dụng chiến lược xoay vòng AVL, xoay mục tiêu gốc để biến nó thành gốc mới của T1.
   Trong quá trình này, nhiều phép quay có thể được thực hiện.

3. Đối với cây con bên trái của T1 và T2, xử lý chúng như trên đệ quy.
   Đối với cây con phải của T1 và T2, xử lý chúng như trên đệ quy.

Thuật toán này, trong trường hợp xấu nhất, chạy trong O (N^2).

Tôi không hiểu cụm từ "cây bất kỳ" và tôi không thể tìm ra cách để T1 bằng T2.

Có ai có thể giúp về câu hỏi này không?

Answer 1

Từ bất cứ điều gì tôi đã nhận tôi có thể đề xuất một thuật toán có thể giải quyết vấn đề này trong thời gian O (N) quay nhưng không thể có được sự chính xác trên ràng buộc nhưng nghĩ rằng bạn có thể xây dựng về vấn đề này: -

Đây là mã giả cho thuật toán: -

//Method to make T1 equivalent to T2 

    alignTree(T1,T2) { 

    if(length(T1)==1) 
     return 

    else { 

     Node k = FindRoot(T1,T2) 
     rotateAbout(k) 
     align(T1.left,T2.left) 
     align(T1.right,T2.right) 
    } 


    } 

Giả sử FindRoot tìm thấy nút của T1 được coi là gốc của cây mới là cây tương đương. Giả sử rotateAbout(K) làm cho vòng quay thích hợp thành gốc để có các nút tương đương trên các nhánh trái và phải của cây mới. Sau đó, chúng tôi có thể giải quyết đệ quy cho các vấn đề phụ nhỏ hơn trên các subtrees nhỏ hơn.

Số Xoay: Như bạn thấy trong mã giả những không quay tương đương với pre-order traversal của cây đó là O(N)

Lưu ý: Bạn luôn có thể mở rộng mã giả trên cho cây chung và vẫn nhận được sự phức tạp tương tự.