Làm cách nào để hợp nhất hai BST hiệu quả?

Question

Làm cách nào để hợp nhất hai cây tìm kiếm nhị phân duy trì thuộc tính của BST?

Nếu chúng tôi quyết định lấy mỗi phần tử từ một cây và chèn nó vào người kia, sự phức tạp của phương pháp này sẽ O(n1 * log(n2)), nơi n1 là số nút của cây (nói T1), mà chúng tôi đã tách ra và n2 là số nút của cây khác (ví dụ T2). Sau thao tác này chỉ có một BST có các nút n1 + n2.

Câu hỏi của tôi là: chúng tôi có thể làm tốt hơn O (n1 * log (n2)) không?

Answer 1

Còn làm phẳng cả hai cây thành danh sách được sắp xếp, hợp nhất các danh sách và sau đó tạo một cây mới?

Answer 2

• Làm phẳng cây thành danh sách được sắp xếp.
• Hợp nhất danh sách được sắp xếp.
• Tạo cây ra khỏi danh sách được hợp nhất.

IIRC, đó là O (n1 + n2).

Answer 3

Naaff của câu trả lời với nhiều hơn một chút chi tiết:

• cầu dẹt một BST vào một danh sách được sắp xếp là O (N)
  • Nó chỉ là "trong trật tự" lặp đi lặp lại trên toàn bộ cây.
  • Làm nó cho cả hai là O (n1 + n2)
• sáp nhập hai danh sách được sắp xếp là vào một danh sách được sắp xếp là O (n1 + n2).
  • Giữ con trỏ đến đầu của cả hai danh sách
  • Đón đầu nhỏ hơn và thăng tiến con trỏ của nó
  • Đây là cách kết hợp của merge-sort làm việc
• Tạo một BST cân một cách hoàn hảo từ một danh sách được sắp xếp là O (N)
  • Giá trị ở giữa sẽ là gốc và recurse.
  • Trong trường hợp của chúng tôi, danh sách được sắp xếp có kích thước n1 + n2. nên O (n1 + n2)
  • Cây kết quả sẽ là BST khái niệm nhị phân tìm kiếm danh sách

Ba bước của O (n1 + n2) cho kết quả trong thời gian O (n1 + n2)

Đối với n1 và n2 của cùng một thứ tự của tầm quan trọng, đó là tốt hơn so với O (n1 * log (n2))

Answer 4

Jonathan,

Sau khi phân loại, chúng tôi có một danh sách dài n1 + n2. Xây dựng một cây nhị phân ra khỏi nó sẽ mất thời gian đăng nhập (n1 + n2). Điều này giống như sắp xếp hợp nhất, chỉ ở mỗi bước đệ quy, chúng ta sẽ không có thuật ngữ O (n1 + n2) như chúng ta có trong thuật toán sắp xếp hợp nhất.Vì vậy, độ phức tạp của thời gian là nhật ký (n1 + n2).

Bây giờ, độ phức tạp của toàn bộ vấn đề là O (n1 + n2).

Ngoài ra tôi sẽ nói phương pháp này là tốt nếu hai danh sách có kích thước tương đương. Nếu các kích thước không thể so sánh thì tốt nhất nên chèn tất cả các nút của cây nhỏ vào một cái cây lớn. Điều này sẽ mất thời gian O (n1 * log (n2)). Ví dụ: nếu chúng ta có hai cây có kích thước 10 và kích thước khác là 1024. Tại đây n1 + n2 = 1034 trong đó n1log (n2) = 10 * 10 = 100. Cách tiếp cận phải phụ thuộc vào kích thước của hai cây.

Answer 5

O (n1 * log (n2)) là trường hợp trung bình ngay cả khi chúng tôi có 2 hợp nhất bất kỳ danh sách chưa được phân loại nào vào BST. Chúng tôi không sử dụng thực tế là danh sách được sắp xếp danh sách hoặc BST.

Theo tôi Giả sử BST có phần tử n1 và phần tử khác có phần tử n2. Bây giờ chuyển đổi một BST thành một danh sách mảng sắp xếp L1 trong O (n1).

Merged BST (BST, Array)

if (Array.size == 0) return BST if (Array.size == 1) chèn phần tử trong BST. trả về BST;

Tìm chỉ mục trong mảng có phần tử bên trái < BST.rootnode và phần tử bên phải> = BST.rootnode nói chỉ mục. if (BST.rootNode.leftNode == null) // tức là Không có nút trái { chèn tất cả các mảng từ chỉ số 0 vào bên trái của BST và } khác { Merged BST (BST.leftNode, Array { 0 đến Index}) }

if (BST.rootNode.rightNode == null) // tức là Không có nút ngay { chèn tất cả các mảng từ Index để Array.size vào bên phải của BST } khác { BST được hợp nhất (BST.rightNode, Array {Index to Array.size}) }

trả lại BST.

Thuật toán này sẽ mất < < thời gian hơn O (n1 * log (n2)) như mỗi lần chúng tôi phân vùng mảng và BST để xử lý các vấn đề con.

---

Answer 6

Ý tưởng là sử dụng tính năng truyền tải theo thứ tự lặp lại. Chúng tôi sử dụng hai ngăn xếp phụ trợ cho hai BST. Vì chúng ta cần in các phần tử theo dạng được sắp xếp, bất cứ khi nào chúng ta lấy một phần tử nhỏ hơn từ bất kỳ cây nào, chúng ta sẽ in nó. Nếu phần tử lớn hơn, sau đó chúng ta đẩy nó trở lại để ngăn xếp cho lần lặp tiếp theo.