Cây tìm kiếm nhị phân cân bằng hoàn hảo

Question

Tôi có câu hỏi lý thuyết về Balanced BST.

Tôi muốn xây dựng Perfect Balanced Tree có các nút 2^k - 1, từ thông thường unbalanced BST. Giải pháp đơn giản nhất tôi có thể nghĩ là sử dụng một số được sắp xếp Array/Linked list và đệ quy chia mảng thành mảng phụ và xây dựng Perfect Balanced BST từ nó.

Tuy nhiên, trong trường hợp kích thước cây cực lớn, tôi sẽ cần phải tạo một Array/List có cùng kích thước để phương pháp này sẽ tiêu tốn một lượng bộ nhớ lớn.

Một tùy chọn khác là sử dụng chức năng xoay AVL, chèn phần tử theo phần tử và cân bằng cây với phép xoay tùy thuộc vào Hệ số cân bằng cây - ba chiều cao của cây con trái và phải.

Câu hỏi của tôi là, tôi có đúng về các giả định của tôi không? Có cách nào khác để tạo ra một hoàn hảo BST từ không cân bằng BST?

Answer 1

Tôi chưa tìm thấy một tình huống rất tốt để cần một cây tìm kiếm hoàn toàn cân bằng. Nếu trường hợp của bạn thực sự cần nó, tôi muốn nghe về nó. Thông thường, tốt hơn và nhanh hơn để có một cây gần như cân bằng.

Nếu bạn có một cây tìm kiếm lớn, bỏ đi tất cả các cấu trúc hiện có thường là không có ý tưởng tốt. Sử dụng chức năng xoay là một cách tốt để có được một cây cân bằng hơn trong khi vẫn giữ hầu hết cấu trúc hiện có. Nhưng thông thường bạn sử dụng một cấu trúc dữ liệu phù hợp để đảm bảo rằng bạn không bao giờ có một cây hoàn toàn không cân bằng. Vì vậy, được gọi là cây tự cân bằng.

Có ví dụ như cây AVL, cây đỏ-đen hoặc cây splay, sử dụng các biến thể hơi khác nhau để giữ cho cây cân bằng.

Nếu bạn thực sự có cây hoàn toàn không cân bằng, bạn có thể có vấn đề khác. - Trong trường hợp của bạn quay nó theo cách AVL có lẽ là cách tốt nhất để sửa chữa nó.

Answer 2

AVL và các cây tương tự không phải là hoàn toàn được cân bằng vì vậy tôi không chắc chắn cách chúng hữu ích trong ngữ cảnh này.

Bạn có thể tạo danh sách được liên kết gấp đôi ra khỏi các nút cây, sử dụng các con trỏ left và right thay vì các con trỏ forward và backward. Sắp xếp danh sách đó, và xây dựng cây một cách đệ quy từ dưới lên, tiêu thụ danh sách từ trái sang phải.

Xây dựng một cây có kích thước 1 là tầm thường: chỉ cần cắn nút ngoài cùng bên trái khỏi danh sách.

Bây giờ nếu bạn có thể xây dựng một cây kích thước N, bạn cũng có thể xây dựng một cây kích thước 2N+1: xây dựng một cây kích thước N, sau đó cắn đứt một nút duy nhất, sau đó xây dựng một cây kích thước N. Nút đơn sẽ là gốc của cây lớn hơn của bạn, và hai cây nhỏ hơn sẽ là các cây con trái và phải của nó. Vì danh sách được sắp xếp, cây sẽ tự động là cây tìm kiếm hợp lệ.

Điều này cũng dễ dàng sửa đổi đối với các kích thước khác ngoài 2^k-1.

Cập nhật: vì bạn đang bắt đầu từ cây tìm kiếm, bạn có thể tạo danh sách được sắp xếp trực tiếp từ thời gian O(N) và O(log N) không gian (có thể ngay cả trong không gian O(1) với chút khéo léo) và xây dựng cây dưới cùng cũng trong không gian O(N) và O(log N) (hoặc O(1)).

Answer 3

Nếu bạn bị hạn chế về bộ nhớ, bạn có thể sử dụng phép chia và nối có thể thực hiện trên cây AVL trong thời gian O (log n) và tôi tin rằng không gian cố định.

Nếu bạn cũng có thể duy trì thống kê đơn đặt hàng, bạn có thể chia nhỏ trên trung bình, làm cho LHS và RHS hoàn hảo và sau đó tham gia.

Các pseudo-code (cho một phiên bản đệ quy) sẽ

này có thể được thực hiện trong thời gian O (n) thời gian và O (log n) không gian, tôi tin.