Trie so với cây đỏ-đen: tốt hơn trong không gian và thời gian？

Question

Cố gắng và cây đỏ đen rất hiệu quả để lưu trữ chuỗi.

Điều nào có độ phức tạp về thời gian tốt hơn? Làm thế nào về không gian phức tạp?

Answer 1

Điều này phụ thuộc vào nhiều yếu tố, chẳng hạn như chuỗi bạn đang lưu trữ và cách trình bày thông tin.

Trong cây đỏ đen, bạn sẽ cần phải so sánh chuỗi O (log n) trên mỗi thao tác (chèn, xóa, tra cứu, v.v.). Chi phí so sánh là nhỏ nếu bạn so sánh hai chuỗi không có tiền tố chung hoặc nếu bạn so sánh hai chuỗi có chuỗi nhỏ. Trường hợp xấu nhất để so sánh là khi một chuỗi là tiền tố của một chuỗi khác, trong trường hợp đó tất cả các ký tự phải được đọc. Do đó, nếu bạn muốn tìm kiếm một chuỗi chiều dài L trong một chuỗi dây màu đỏ đen, trong trường hợp xấu nhất bạn sẽ làm O (L log n) hoạt động bằng cách so sánh O (log n), mỗi cái nhìn vào tất cả các ký tự từ chuỗi đầu vào. Tuy nhiên, trong trường hợp tốt nhất, điều này sẽ chỉ yêu cầu thời gian O (log n), điều này xảy ra nếu các phép so sánh luôn thất bại ngay lập tức.

Về mặt sử dụng không gian, cây đỏ/đen sẽ cần hai con trỏ trên mỗi nút và một nút trên mỗi chuỗi. (Các bit màu đỏ/đen thường có thể được đóng gói vào các bit thấp của một con trỏ). Do đó tổng không gian là 2n + (tổng chiều dài của tất cả các chuỗi).

Trong một trie, chèn, xóa và tra cứu lấy O (L) trong trường hợp xấu nhất (nếu tất cả các ký tự của đầu vào phải được xem xét) và O (1) trong trường hợp tốt nhất (nếu bạn rơi ra khỏi trie sớm). Điều này nhanh hơn cây đỏ-đen bởi hệ số O (log n), có thể có ý nghĩa quan trọng đối với các bộ sưu tập lớn. Tuy nhiên, các trie có địa phương tồi tệ hơn, vì có rất nhiều con trỏ-đuổi theo tham gia và không có mảng liền kề của các nhân vật để quét.

Về mặt sử dụng bộ nhớ, một trie có bảng chữ cái có kích thước k thường cần tổng số con trỏ kn, trong đó n là số nút. Điều này có thể tồi tệ hơn nhiều so với cây đỏ/đen nếu kích thước bảng chữ cái lớn. Tuy nhiên, chi phí trên không gian có thể được giảm bằng cách nén trie bằng cách sử dụng biểu diễn cây Patricia, sử dụng cấu trúc dữ liệu hiệu quả hơn để lưu trữ con trỏ, hoặc xây dựng một DAWG từ trie.

Hy vọng điều này sẽ hữu ích!