Xác định xem hai cây nhị phân có bằng nhau hay không

Question

Thuật toán hiệu quả sẽ tìm ra điều gì nếu hai cây nhị phân được cho là bằng nhau - về cấu trúc và nội dung?

Answer 1

đó là một vấn đề nhỏ, nhưng tôi muốn thích nghi với giải pháp trước đó như sau ...

eq(t1, t2) = 
    t1.data=t2.data && eq(t1.left, t2.left) && eq(t1.right, t2.right) 

lý do là m ismatches có khả năng là phổ biến, và nó là tốt hơn để phát hiện (và ngừng so sánh) sớm - trước khi đệ quy thêm. Tất nhiên, tôi giả định một nhà điều hành ngắn mạch & & tại đây.

Tôi cũng sẽ chỉ ra rằng điều này đang làm sáng tỏ một số vấn đề với việc xử lý các cây có cấu trúc khác nhau một cách chính xác và kết thúc đệ quy. Về cơ bản, có cần phải có một số kiểm tra null cho t1.left vv Nếu một cây có một null .left nhưng khác không, bạn đã tìm thấy một sự khác biệt về cấu trúc. Nếu cả hai đều có giá trị rỗng, không có sự khác biệt, nhưng bạn đã đạt đến một chiếc lá - không được tiếp tục thêm nữa. Chỉ khi cả hai giá trị .left không phải là null, bạn có thể kiểm tra lại để kiểm tra cây con. Điều tương tự cũng áp dụng, tất nhiên, cho đúng.

Bạn có thể bao gồm séc, ví dụ: (t1.left == t2.left), nhưng điều này chỉ có ý nghĩa nếu subtrees có thể được chia sẻ vật lý (cùng một nút cấu trúc dữ liệu) cho hai cây. Kiểm tra này sẽ là một cách khác để tránh đệ quy nơi không cần thiết - nếu t1.left và t2.left là cùng một nút vật lý, bạn đã biết rằng toàn bộ các subtrees đó giống hệt nhau.

thực hiện AC có thể là ...

bool tree_compare (const node* t1, const node* t2) 
{ 
    // Same node check - also handles both NULL case 
    if (t1 == t2) return true; 

    // Gone past leaf on one side check 
    if ((t1 == NULL) || (t2 == NULL)) return false; 

    // Do data checks and recursion of tree 
    return ((t1->data == t2->data) && tree_compare (t1->left, t2->left) 
           && tree_compare (t1->right, t2->right)); 
} 

EDIT Đáp lại nhận xét ...

Thời gian chạy để so sánh cây đầy đủ sử dụng này chỉ đơn giản là hầu hết các quy định như O (n) trong đó n là kích thước của một cái cây. Nếu bạn sẵn sàng chấp nhận một ràng buộc phức tạp hơn, bạn có thể nhận được một nhỏ hơn như O (tối thiểu (n1, n2)) trong đó n1 và n2 là kích thước của cây.

Giải thích về cơ bản là cuộc gọi đệ quy chỉ được thực hiện (nhiều nhất) một lần cho mỗi nút trong cây bên trái và chỉ được thực hiện (tối đa) một lần cho mỗi nút trong cây bên phải. Vì bản thân hàm (không bao gồm việc thu thập) chỉ xác định tối đa một lượng công việc không đổi (không có vòng lặp), công việc bao gồm tất cả các cuộc gọi đệ quy chỉ có thể bằng kích thước của cây nhỏ hơn hằng số đó.

Bạn có thể phân tích thêm để có được một ranh giới phức tạp hơn nhưng nhỏ hơn bằng cách sử dụng ý tưởng giao điểm của cây, nhưng O lớn chỉ cho một giới hạn trên - không nhất thiết là giới hạn trên thấp nhất có thể. Nó có thể không đáng làm phân tích đó trừ khi bạn đang cố gắng xây dựng một thuật toán/cấu trúc dữ liệu lớn hơn với thành phần này, và kết quả là bạn biết rằng một số tài sản sẽ luôn áp dụng cho những cây có thể cho phép bạn ràng buộc chặt chẽ hơn thuật toán lớn hơn.

Một cách để tạo thành một giới hạn tigher là xem xét các bộ đường dẫn đến các nút trong cả hai cây. Mỗi bước là L (cây con trái) hoặc R (cây con phải). Vì vậy, gốc được chỉ định với một đường dẫn trống. Con phải của con trái của gốc là "LR". Xác định một hàm "đường dẫn (T)" (toán học - không phải là một phần của chương trình) để biểu diễn tập các đường dẫn hợp lệ thành một cây - một đường dẫn cho mỗi nút.

Vì vậy, chúng ta có thể có ...

paths(t1) = { "", "L", "LR", "R", "RL" } 
paths(t2) = { "", "L", "LL", "R", "RR" } 

Các thông số kỹ thuật cùng một con đường áp dụng cho cả cây. Và mỗi đệ quy luôn đi theo cùng một liên kết trái/phải cho cả hai cây. Vì vậy, đệ quy thăm các đường dẫn trong itersection của các bộ, và ràng buộc chặt chẽ chúng tôi có thể chỉ định bằng cách sử dụng này là cardinality của giao lộ đó (vẫn còn với liên tục ràng buộc vào công việc cho mỗi đệ quy gọi).

Đối với các cấu trúc cây ở trên, chúng ta làm recursions cho các đường dẫn sau đây ...

paths(t1) intersection paths(t2) = { "", "L", "R" } 

Vì vậy, công việc của chúng tôi trong trường hợp này được bao bọc để tối đa là ba lần so với chi phí tối đa công việc không đệ quy trong function tree_compare.

Đây thường là số lượng chi tiết không cần thiết, nhưng rõ ràng giao lộ của các tập hợp đường dẫn tối đa bằng số nút trong cây gốc nhỏ nhất. Và liệu n trong O (n) đề cập đến số lượng các nút trong một cây gốc hoặc tổng của các nút trong cả hai, điều này rõ ràng là không nhỏ hơn mức tối thiểu hoặc giao lộ của chúng ta. Vì vậy O (n) không phải là một ràng buộc chặt chẽ, nhưng nó vẫn là một ràng buộc trên hợp lệ, ngay cả khi chúng ta có một chút mơ hồ mà kích thước chúng ta đang nói đến.

Answer 2

Cụm từ chung chung hơn cho những gì bạn có thể đang cố gắng hoàn thành là graph isomorphism. Có một số thuật toán để làm điều này trên trang đó.

Answer 3

Modulo stack overflow, một cái gì đó giống như

eq(t1, t2) = 
    eq(t1.left, t2.left) && t1.data=t2.data && eq(t1.right, t2.right) 

(này khái quát một vị bình đẳng cho tất cả các loại dữ liệu đại số cây có cấu trúc - cho bất kỳ mảnh dữ liệu có cấu trúc, kiểm tra xem mỗi tiểu bộ phận của nó đều bình đẳng cho mỗi tiểu phần người khác.)

Answer 4

Tôi sẽ viết như sau. Các mã sau đây sẽ làm việc trong ngôn ngữ chức năng nhất, và ngay cả trong python nếu kiểu dữ liệu của bạn là hashable (ví dụ không điển hoặc danh sách):

• topo bình đẳng (tương tự trong cấu trúc, tức là Tree(1,Tree(2,3))==Tree(Tree(2,3),1)):

  tree1==tree2 nghĩa set(tree1.children)==set(tree2.children)

• ra lệnh bình đẳng:

  tree1==tree2 nghĩa tree1.children==tree2.children

(Tree.children là một danh sách có thứ tự các trẻ em)

Bạn không cần phải xử lý các trường hợp cơ sở (lá), vì bình đẳng đã được xác định cho họ rồi.

Answer 5

Chúng tôi cũng có thể thực hiện bất kỳ thao tác nào trong hai lần duyệt qua (đặt hàng trước, sau khi đặt hàng hoặc theo thứ tự) và sau đó so sánh kết quả của cả hai cây. Nếu chúng giống nhau, chúng ta có thể chắc chắn về sự tương đương của chúng.

Answer 6

Kể từ đó là một thực tế chứng minh rằng - chúng ta có thể tái tạo một cây nhị phân miễn là chúng ta có những điều sau đây:

1. Trình tự các nút được gặp trong một trong thứ tự Traversal.
2. Trình tự các nút được gặp trong một đặt hàng trước hoặc sau theo thứ tự Traversal

Nếu hai cây nhị phân có cùng trong trật tự và [pre-order HOẶC hậu thứ tự] chuỗi, sau đó họ nên bằng cả về mặt cấu trúc lẫn giá trị.

Mỗi lần truyền tải là một hoạt động O (n). Các traversals được thực hiện 4 lần trong tổng số và kết quả từ cùng một loại traversal được so sánh. O (n) * 4 + 2 => O (n) Do đó, tổng số thứ tự thời gian phức tạp sẽ là O (n)