Trees với giá trị trên lá chỉ

Question

Một vài năm trước, trong một C# Tất nhiên tôi đã học để viết một cây nhị phân mà nhìn nhiều hơn hoặc ít hơn như thế này:

data Tree a = Branch a (Tree a) (Tree a) | Leaf 

tôi thấy lợi ích của nó, nó có giá trị của nó trên cành, cho phép tra cứu nhanh chóng và dễ dàng và chèn các giá trị, bởi vì nó sẽ gặp phải một giá trị trên gốc của mỗi nhánh xuống cho đến khi nó chạm vào một chiếc lá, không giữ giá trị.

Kể từ khi tôi bắt đầu học Haskell, tuy nhiên; Tôi đã thấy nhiều ví dụ về cây được xác định như sau:

data Tree a = Branch (Tree a) (Tree a) | Leaf a 

Định nghĩa đó giải thích tôi. Tôi không thể nhìn thấy tính hữu ích của việc có số liệu về các yếu tố không chi nhánh, bởi vì nó sẽ kết thúc dẫn đến một cái cây trông như thế này:

nào với tôi, có vẻ như một thiết kế kém thay thế cho Danh sách. Nó cũng khiến tôi đặt câu hỏi về thời gian tra cứu của nó, vì nó không thể lừa được nhánh nào đi xuống để tìm giá trị mà nó đang tìm kiếm; nhưng thay vào đó cần phải đi qua mọi nút để tìm những gì nó đang tìm kiếm.

Vì vậy, bất kỳ ai cũng có thể làm sáng tỏ lý do tại sao phiên bản thứ hai (giá trị trên lá) lại phổ biến hơn nhiều trong Haskell so với phiên bản đầu tiên?

Answer 1

Tôi nghĩ điều này phụ thuộc vào những gì bạn đang cố gắng lập mô hình và cách bạn đang cố gắng mô hình hóa.

Một cây nơi các nút bên trong lưu trữ các giá trị và lá chỉ là một cây nhị phân chuẩn (cây mỗi lá là NULL và về cơ bản bạn có cây nhị phân bắt buộc). Nếu các giá trị được lưu trữ theo thứ tự sắp xếp, bây giờ bạn có một cây tìm kiếm nhị phân. Có rất nhiều lợi thế cụ thể để lưu trữ dữ liệu theo cách này, hầu hết trong số đó chuyển trực tiếp từ các thiết lập bắt buộc.

Cây nơi lá lưu trữ dữ liệu và các nút bên trong chỉ dành cho cấu trúc có lợi thế. Ví dụ, cây đỏ/đen hỗ trợ hai hoạt động mạnh mẽ được gọi là split và join có lợi thế trong một số trường hợp. split lấy làm đầu vào một khóa, sau đó triệt tiêu sửa đổi cây để tạo ra hai cây, một trong số đó chứa tất cả các khóa nhỏ hơn khóa đầu vào được chỉ định và một khóa chứa các phím còn lại. join, theo nghĩa đen, ngược lại: nó lấy trong hai cây nơi giá trị của một cây là tất cả ít hơn giá trị của cây khác, sau đó kết hợp chúng với nhau thành một cây duy nhất. Các hoạt động này đặc biệt khó thực hiện trên hầu hết các cây đỏ/đen, nhưng đơn giản hơn nhiều nếu tất cả dữ liệu được lưu trữ trong lá chỉ thay vì trong các nút bên trong. This paper detailing an imperative implementation of red/black trees đề cập rằng một số triển khai cũ hơn của cây đỏ/đen sử dụng phương pháp này vì lý do này rất.

Là một lợi thế tiềm năng khác của việc lưu trữ khóa trong lá, giả sử bạn muốn triển khai phép toán nối, kết hợp hai danh sách với nhau. Nếu bạn không có dữ liệu trong lá, điều này đơn giản như

concat first second = Branch first second 

Điều này làm việc vì không có dữ liệu được lưu trữ trong các nút đó. Nếu dữ liệu được lưu trữ trong lá, bạn cần bằng cách nào đó di chuyển một chìa khóa từ một trong các lá lên đến nút ghép mới, mất nhiều thời gian hơn và sẽ phức tạp hơn để làm việc.

Cuối cùng, trong một số trường hợp, bạn có thể muốn lưu trữ dữ liệu trong các lá vì các lá về cơ bản khác với các nút bên trong. Hãy xem xét một cây phân tích, ví dụ, nơi lá lưu trữ các thiết bị đầu cuối cụ thể từ phân tích cú pháp và các nút bên trong lưu trữ tất cả các nonterminals trong quá trình sản xuất. Trong trường hợp này, có hai loại nút khác nhau, do đó, không có ý nghĩa để lưu trữ dữ liệu tùy ý trong các nút bên trong.

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

Answer 2

Khác là tốt hơn tệ hơn nhiều hơn. Tôi sẽ giải thích chỉ một vài lời khuyên cơ bản để cho thấy lý do tại sao trực giác của bạn không thành công. Tuy nhiên, ý tưởng chung là các cấu trúc dữ liệu khác nhau cần những thứ khác nhau.

Các nút lá trống thực tế có thể là vấn đề về không gian (và do đó thời gian) trong một số ngữ cảnh. Nếu một nút được biểu thị bằng một chút thông tin và hai con trỏ tới con của nó, bạn sẽ kết thúc với hai con trỏ null cho mỗi nút có con là cả hai lá. Đó là hai từ máy trên mỗi nút lá, có thể thêm đến một chút không gian. Một số cấu trúc tránh điều này bằng cách đảm bảo rằng mỗi chiếc lá chứa ít nhất một mẩu thông tin để biện minh cho sự tồn tại của nó. Trong một số trường hợp (chẳng hạn như ropes), mỗi chiếc lá có thể có trọng tải khá lớn và dày đặc.

Làm cho các nút bên trong lớn hơn (bằng cách lưu trữ thông tin trong chúng) làm cho việc sửa đổi cây trở nên tốn kém hơn. Thay đổi một chiếc lá trong một cây cân bằng thường buộc bạn phải phân bổ thay thế cho các nút nội bộ O(log n). Nếu mỗi cái lớn hơn, bạn chỉ cần phân bổ nhiều không gian hơn và dành nhiều thời gian hơn để sao chép nhiều từ hơn. Kích thước thêm của các nút bên trong cũng có nghĩa là bạn có thể vừa với cấu trúc cây vào bộ đệm CPU.

Answer 3

Bạn đã mô tả một cây có dữ liệu ở lá là "một thiết kế kém được thay thế cho Danh sách".

Tôi đồng ý rằng điều này có thể được sử dụng làm phương án thay thế cho danh sách nhưng không nhất thiết phải được thiết kế kém! Hãy xem xét các kiểu dữ liệu

data Tree t = Leaf t | Branch (Tree t) (Tree t) 

Bạn có thể xác định cons và snoc (append đến cuối danh sách) hoạt động -

cons :: t -> Tree t -> Tree t 
cons t (Leaf s)  = Branch (Leaf t) (Leaf s) 
cons t (Branch l r) = Branch (cons t l) r 

snoc :: Tree t -> t -> Tree t 
snoc (Leaf s)  t = Branch (Leaf s) (Leaf t) 
snoc (Branch l r) t = Branch l (snoc r t) 

Những chạy (đối với danh sách tương đối cân bằng) trong thời gian O (log n) thời gian trong đó n là độ dài của danh sách. Điều này trái ngược với danh sách được liên kết tiêu chuẩn, có các hoạt động O (1) cons và O (n) snoc. Bạn cũng có thể xác định một hằng số thời gian append (như trong câu trả lời templatetypedef của)

append :: Tree t -> Tree t -> Tree t 
append l r = Branch l r 

mà là O (1) cho hai danh sách của bất kỳ kích thước, trong khi danh sách tiêu chuẩn là O (n) trong đó n là chiều dài của đối số bên trái.

Trong thực tế, bạn sẽ muốn xác định phiên bản thông minh hơn một chút của các chức năng này cố gắng giữ cho cây cân bằng.Để làm điều này, thường có ích khi có một số thông tin bổ sung tại các nhánh, có thể được thực hiện bằng cách có nhiều loại nhánh (như trong một cây đỏ đen có các nút "đỏ" và "đen") hoặc bao gồm dữ liệu bổ sung tại các chi nhánh, như trong

data Tree b a = Leaf a | Branch b (Tree b a) (Tree b a) 

Ví dụ, bạn có thể hỗ trợ một O (1) size hoạt động bằng cách lưu trữ tổng số phần tử trong cả hai subtrees trong các nút. Tất cả các hoạt động của bạn trên cây trở nên phức tạp hơn một chút vì bạn cần phải duy trì chính xác thông tin về kích thước subtree - trong thực tế công việc tính toán kích thước của cây được phân bổ trên tất cả các hoạt động xây dựng cây (và khéo léo kiên trì, để công việc tối thiểu được thực hiện bất cứ khi nào bạn cần phải tạo lại kích thước sau).