Ghép/Kết hợp/Nối hai cây AVL

Question

Giả sử rằng tôi có hai cây AVL và mỗi phần tử từ cây đầu tiên nhỏ hơn thì bất kỳ phần tử nào từ cây thứ hai. Cách hiệu quả nhất để ghép chúng vào một cây AVL đơn lẻ là gì? Tôi đã tìm kiếm ở khắp mọi nơi nhưng không tìm thấy bất cứ điều gì hữu ích.

Answer 1

Giả sử bạn có thể phá hủy các cây đầu vào:

1. loại bỏ các yếu tố ngoài cùng bên phải cho cây trái, và sử dụng nó để xây dựng một nút gốc mới, có con bên trái là cây trái, và có con bên phải là cây phải: O (log n)
2. xác định và đặt hệ số cân bằng của nút đó: O (log n). Trong (tạm thời) vi phạm bất biến, yếu tố cân bằng có thể bên ngoài phạm vi {-1, 0, 1}
3. xoay để có được những yếu tố cân bằng trở lại vào khoảng: O (log n) phép quay: O (log n)

Do đó, toàn bộ thao tác có thể được thực hiện trong O (log n).

Chỉnh sửa: Theo ý nghĩ thứ hai, sẽ dễ dàng hơn để giải thích về các phép quay trong thuật toán sau. Nó cũng khá có khả năng nhanh hơn:

1. Xác định chiều cao của cả hai cây: O (log n).
   Giả sử rằng cây phải cao hơn (trường hợp khác là đối xứng):
2. xóa phần tử ngoài cùng bên phải khỏi cây left (xoay và điều chỉnh chiều cao được tính nếu cần). Hãy để n là yếu tố đó. O (log n)
3. Trong cây bên phải, điều hướng sang trái cho đến khi bạn đạt đến nút có số lượng con nhiều nhất là 1 cao hơn left. Hãy để r là nút đó. O (log n)

4. thay thế nút đó bằng nút mới có giá trị n và các subtrees left và r. O (1)
   Bằng cách xây dựng, nút mới được cân bằng AVL và nút con của nó cao hơn r.

5. tăng số dư của phụ huynh cho phù hợp. O (1)

6. và cân bằng lại như sau khi chèn. O (log n)

Answer 2

Tôi nghi ngờ rằng bạn sẽ chỉ phải đi bộ một cây (hy vọng nhỏ hơn) và cá nhân thêm từng phần tử của nó vào cây khác. Các hoạt động chèn/xóa AVL không được thiết kế để xử lý việc thêm toàn bộ cây con tại một thời điểm.

Answer 3

Một giải pháp cực kỳ đơn giản (mà làm việc mà không cần bất kỳ giả định trong quan hệ giữa cây) là thế này:

1. Làm một loại kết hợp của cả hai cây vào một mảng sáp nhập (đồng thời lặp lại cả hai cây).
2. Tạo một cây AVL từ mảng - lấy phần tử ở giữa làm gốc và áp dụng đệ quy cho nửa trái và phải.

Cả hai bước này là O (n). Vấn đề chính với nó là phải mất không gian thêm O (n).

Answer 4

Giải pháp tốt nhất tôi đọc cho sự cố này có thể được tìm thấy here. Rất gần với câu trả lời của meriton nếu bạn khắc phục sự cố này:

Điều hướng thứ ba của thuật toán điều hướng sang trái cho đến khi nút có cây phụ có cùng chiều cao với cây bên trái. Điều này không phải lúc nào cũng có thể, (xem hình ảnh phản diện). Đúng cách để thực hiện bước này là hai tìm cho một cây con với chiều cao h hoặc h+1 nơi h là chiều cao của cây trái