Tại sao không có chu kỳ trong cây nhị phân bất biến của Eric Lippert?

Question

Tôi chỉ xem xét việc triển khai đơn giản của Eric Lippert là immutable binary tree và tôi có câu hỏi về nó. Sau khi thể hiện việc thực hiện, Eric nói rằng

Lưu ý rằng một tính năng tốt đẹp của cấu trúc dữ liệu bất biến là nó là không thể vô tình (hay cố tình !) Tạo ra một cây mà chứa một chu kỳ.

Dường như tính năng này của việc triển khai của Eric không đến từ tính bất biến, mà còn từ thực tế là cây được xây dựng từ lá. Điều này tự nhiên ngăn chặn một nút từ việc có bất kỳ tổ tiên của nó như là trẻ em. Có vẻ như nếu bạn xây dựng cây theo một hướng khác, bạn sẽ giới thiệu khả năng của chu kỳ.

Tôi có đúng trong suy nghĩ của tôi, hoặc không thể vượt qua các chu kỳ trong trường hợp này đến từ tính bất biến? Xem xét nguồn gốc, tôi tự hỏi liệu tôi có thiếu cái gì không.

EDIT: Sau khi suy nghĩ kỹ hơn một chút, có vẻ như việc xây dựng từ những chiếc lá có thể là cách duy nhất để tạo ra một cây bất biến. Tôi có đúng không?

Answer 1

Nếu bạn đang sử dụng cấu trúc dữ liệu không thay đổi, theo ngôn ngữ nghiêm ngặt (trái ngược với lười), bạn không thể tạo chu trình; vì bạn phải tạo các phần tử theo thứ tự nào đó và khi một phần tử được tạo, bạn không thể biến đổi nó thành một phần tử được tạo sau này. Vì vậy, nếu bạn đã tạo nút n, và sau đó tạo ra nút m mà chỉ vào n (có lẽ gián tiếp), bạn không bao giờ có thể hoàn thành chu trình bằng cách gây n để trỏ vào m như bạn không được phép biến đổi n hoặc bất kỳ nội dung nào mà n đã trỏ đến.

Có, bạn chính xác rằng bạn chỉ có thể tạo ra một cây bất biến bằng cách xây dựng từ lá; nếu bạn bắt đầu từ thư mục gốc, bạn sẽ phải sửa đổi thư mục gốc để trỏ vào con của nó khi bạn tạo chúng. Chỉ bằng cách bắt đầu từ lá, và tạo ra mỗi nút để trỏ đến con của nó, bạn có thể xây dựng một cây từ các nút bất biến.

Answer 2

Bạn không thể xây dựng nó từ gốc, nó đòi hỏi bạn phải đột biến các nút bạn đã thêm.

Answer 3

Khi bạn nói "được xây dựng từ lá", tôi đoán bạn đang bao gồm thực tế là người xây dựng có con nhưng không bao giờ có cha mẹ.

Dường như nếu bạn xây dựng cây theo hướng khác , bạn sẽ giới thiệu khả năng của chu kỳ.

Không, vì sau đó bạn có ràng buộc ngược lại: hàm tạo sẽ phải nhận cha mẹ nhưng không bao giờ là con. Vì vậy bạn không bao giờ có thể tạo ra một hậu duệ cho đến khi tất cả tổ tiên của nó được tạo ra. Do đó không có chu kỳ là có thể.

Sau khi suy nghĩ nó hơn một chút, nó vẻ như xây dựng từ những chiếc lá có thể là cách duy nhất để tạo ra một cây bất biến . Tôi có đúng không?

Không ... xem nhận xét của tôi về Brian và ergosys.

Đối với nhiều ứng dụng, một cây có nút con trỏ đến cha mẹ không phải là rất hữu ích. Tôi cấp điều đó. Nếu bạn cần phải đi qua cây trong một trật tự được xác định bởi hệ thống phân cấp của nó, một cây hướng lên làm cho khó khăn đó.

Tuy nhiên đối với các ứng dụng khác, loại cây đó chính xác là loại chúng tôi muốn. Ví dụ, chúng tôi có một cơ sở dữ liệu các bài báo. Mỗi bài viết có thể có một hoặc nhiều bản dịch. Mỗi bản dịch có thể có bản dịch. Chúng ta tạo cấu trúc dữ liệu này như một bảng cơ sở dữ liệu quan hệ, trong đó mỗi bản ghi có một "khóa ngoại" (con trỏ) cho cha của nó. Không có bản ghi nào trong số những bản ghi này cần phải thay đổi con trỏ của nó thành bản gốc của nó. Khi một bài viết hoặc bản dịch mới được thêm vào, bản ghi sẽ được tạo ra với một con trỏ đến cha mẹ thích hợp.

Trường hợp sử dụng phổ biến là truy vấn bảng dịch, tìm bản dịch cho một bài viết cụ thể hoặc bản dịch bằng một ngôn ngữ cụ thể. Ah, bạn nói, bảng dịch là một cấu trúc dữ liệu có thể thay đổi.

Chắc chắn là vậy. Nhưng nó tách biệt với cái cây. Chúng tôi sử dụng cây (không thay đổi) để ghi lại các mối quan hệ phân cấp và bảng có thể thay đổi để lặp qua các mục. Trong một tình huống không phải là cơ sở dữ liệu, bạn có thể có một bảng băm trỏ đến các nút của cây. Dù bằng cách nào, bản thân cây (tức là các nút) không bao giờ bị sửa đổi.

Here's another example of this data structure, bao gồm cách truy cập các nút một cách hữu ích.

Quan điểm của tôi là câu trả lời cho câu hỏi của OP là "có", tôi đồng ý với phần còn lại của bạn, rằng việc ngăn ngừa các chu kỳ không đến từ bất biến một mình. Trong khi bạn có thể xây dựng một cây theo hướng khác (từ trên xuống), nếu bạn làm thế, và nó không thay đổi, nó vẫn không thể có chu kỳ.

Khi bạn đang nói về đảm bảo lý thuyết mạnh mẽ như

một tính năng tốt đẹp của cấu trúc dữ liệu bất biến là nó là không thể vô tình (hay cố tình !) Tạo ra một cây mà chứa một chu kỳ [nhấn mạnh vào ảnh gốc]

"cây như vậy sẽ không hữu ích" so sánh với nhau - ngay cả khi nó đúng. Mọi người thường xuyên tạo ra các cấu trúc dữ liệu không hữu ích, hãy để một mình tạo ra những mục đích vô dụng. Các uselessness giả định không bảo vệ chương trình từ những cạm bẫy của chu kỳ trong cấu trúc dữ liệu của bạn. Một đảm bảo lý thuyết không (giả sử bạn thực sự đáp ứng các tiêu chí nó nói).

P.S. một tính năng tốt đẹp của cây hướng lên trên là bạn có thể đảm bảo một khía cạnh của định nghĩa cây rằng cấu trúc dữ liệu cây trỏ xuống (giống như của Eric Lippert) không: mỗi nút có tối đa một phụ huynh. (Xem David's comment và phản hồi của tôi.)

Answer 4

Nếu bạn thực sự muốn thử sức với nó, bạn có thể tạo ra một cái cây với chu kỳ trong đó là bất biến.Ví dụ, bạn có thể định nghĩa một lớp đồ thị bất biến và sau đó nói:

Graph g = Graph.Empty 
    .AddNode("A") 
    .AddNode("B") 
    .AddNode("C") 
    .AddEdge("A", "B") 
    .AddEdge("B", "C") 
    .AddEdge("C", "A"); 

Và hey, bạn đã có một "cây" với "chu kỳ" trong nó - bởi vì tất nhiên bạn không có một cây trong nơi đầu tiên, bạn có đồ thị được chỉ dẫn. Tuy nhiên, với một kiểu dữ liệu thực sự sử dụng một cây con "trái và phải" truyền thống của cây nhị phân thì không có cách nào để tạo ra cây cyclic (modulo các thủ thuật lén lút như sử dụng mã phản chiếu hoặc mã không an toàn).