Giữ một cây nhị phân cân bằng khi yếu tố này được chèn vào để

Question

tôi đã tự hỏi nếu có một thuật toán phù hợp để duy trì sự cân bằng của một cây nhị phân, khi nó được biết rằng yếu tố này là luôn chèn theo thứ tự.

Một tùy chọn cho việc này là sử dụng phương pháp chuẩn để tạo cây cân bằng từ mảng được sắp xếp hoặc danh sách được liên kết, như được thảo luận trong câu hỏi this và cũng là this câu hỏi khác. Tuy nhiên, tôi muốn một phương thức mà một vài phần tử có thể được chèn vào cây, tra cứu sau đó thực hiện trên nó, và các phần tử khác sau đó được thêm vào sau, mà không cần phải phân hủy cây thành danh sách và tạo lại toàn bộ.

Một tùy chọn khác sẽ là sử dụng một trong nhiều triển khai tự cân bằng cây, AVL, AA, Đỏ-Đen, v.v. Tuy nhiên, tất cả những điều này áp đặt một số chi phí trong quá trình chèn, và tôi đã tự hỏi nếu có thể có một cách để tránh điều này cho ràng buộc các yếu tố là luôn luôn chèn vào theo thứ tự tăng dần. Vì vậy, để rõ ràng, tôi muốn biết nếu có một phương pháp mà tôi có thể duy trì một cây nhị phân cân bằng, để tôi có thể chèn một phần tử mới tùy ý vào nó bất kỳ lúc nào và giữ thăng bằng của cây, cung cấp rằng phần tử mới lớn hơn trong thứ tự của cây hơn tất cả các yếu tố đã có trong cây.

Như một ví dụ, giả sử tôi có cây sau:

 4 
    /\ 
    / \ 
    2  6 
/\ /\ 
    1 3 5 7 

Có một cách đơn giản để duy trì cân bằng khi chèn một yếu tố mới, nếu tôi biết rằng nguyên tố này sẽ lớn hơn 7?

Answer 1

Nếu bạn thực sự quan tâm đến việc nó sử dụng một BST (mà tôi nghĩ không phải là lựa chọn tốt nhất, như bạn có thể đọc trong câu trả lời khác của tôi), bạn có thể làm điều đó như thế này:

Có BST bình thường . Điều đó có nghĩa là tra cứu là O (log N), nếu chúng ta quản lý để giữ độ sâu trong khi chèn.

Khi thực hiện chèn (giả sử chúng tôi có phần tử lớn hơn tất cả các phần trước đó), bạn đi bộ từ gốc sang phần tử ngoài cùng bên phải.Khi bạn gặp phải một nút có subtree là một cây nhị phân hoàn hảo (tất cả các nút bên trong có 2 con và tất cả các lá ở cùng độ sâu), bạn chèn nút mới làm nút cha của nút này.

Nếu bạn đạt đến nút ngoài cùng bên phải trên cây và bạn không áp dụng quy tắc trước đó, điều đó có nghĩa là nó có con trái, nhưng nó không có đúng. Vì vậy, nút mới trở thành con phải của nút hiện tại.

Ví dụ, trong cây đầu tiên bên dưới, cây con của 4 không hoàn hảo, nhưng cây con của 5 là (một cây chỉ với một nút là hoàn hảo theo định nghĩa). Vì vậy, chúng ta thêm 6 là cha mẹ của 5, có nghĩa là 4 là cha mẹ của 6 bây giờ và 5 là con trái của 6.

Nếu chúng ta cố gắng thêm một nút khác, thì cây con của 4 vẫn không hoàn hảo, và không phải là một trong 6. Và 6 là nút phải nhất, vì vậy chúng tôi thêm 7 là con phải của 6.

 4    4    4 
    /\   /\   /\ 
/ \  / \  / \ 
    2  5 --> 2  6 --> 2  6 
/\   /\ / /\ /\ 
1 3   1 3 5  1 3 5 7 

Nếu chúng ta sử dụng thuật toán này, con của con trái của thư mục gốc sẽ luôn luôn được hoàn hảo và subtree của con phải sẽ không bao giờ có chiều cao lớn hơn so với một trong những trái. Do đó, chiều cao của toàn bộ cây sẽ luôn là O (log N), và do đó sẽ là thời gian tra cứu. Việc chèn cũng sẽ mất thời gian O (log N).

Khi so sánh với BST tự cân bằng, độ phức tạp thời gian giống nhau. Nhưng thuật toán này sẽ dễ thực hiện hơn và có thể thực sự nhanh hơn chúng.

Khi so sánh với giải pháp dựa trên mảng từ câu trả lời khác của tôi, độ phức tạp của tra cứu là như nhau, nhưng BST này có thời gian chèn kém hơn.

Answer 2

Tôi giả sử rằng bạn biết một ưu tiên mà các yếu tố đến theo thứ tự tăng dần. Hơn nữa, tôi cho rằng bạn muốn có một cây để tìm kiếm nhanh một yếu tố cụ thể.

Tôi không chắc liệu cây nhị phân có phù hợp nhất để chèn nhanh như bạn mô tả hay không. Nhưng có thể có các cấu trúc dữ liệu khác xử lý tốt với trường hợp sử dụng mà bạn mô tả: Mặc dù tôi chưa bao giờ sử dụng nó, một số skip-list xuất hiện trong đầu tôi. Vì bạn luôn chèn các phần tử lớn hơn tất cả các phần tử đã có trong bộ sưu tập, nên khá dễ dàng để cập nhật các con trỏ.

Answer 3

Đối với yêu cầu bạn mô tả, bạn không cần một cây nào cả. Một sắp xếp dynamic array là tất cả những gì bạn cần.

Khi chèn, luôn chèn vào cuối (O (1) được khấu hao).

Khi tìm kiếm, sử dụng bình thường binary search (O (log N)).

Điều này giả định bạn không cần bất kỳ hoạt động nào khác hoặc bạn không nhớ chúng sẽ là O (N).