Tìm xem cây có phải là cây con của

Question

Có hai cây nhị phân T1 và T2 lưu trữ dữ liệu ký tự, các bản sao được cho phép hay không.
Làm cách nào để tìm T2 có phải là cây con của T1 không? .
T1 có hàng triệu nút và T2 có hàng trăm nút.

Answer 1

Traverse T1. Nếu nút hiện tại bằng nút gốc của T2, đi qua cả hai cây (T2 và cây con hiện tại của T1) cùng một lúc. So sánh nút hiện tại. Nếu chúng luôn bằng nhau, T2 là một cây con của T1.

Answer 2

Nếu cây của bạn không được sắp xếp theo bất kỳ cách nào, tôi không thấy cách nào khác ngoài việc thực hiện tìm kiếm brute-force: đi qua cây T1 và kiểm tra xem bạn có đạt được nút nào khớp với nút đầu tiên không nút của cây T2. Nếu không, hãy tiếp tục đi qua T1. Nếu vậy, hãy kiểm tra xem các nút tiếp theo có phù hợp hay không, cho đến khi bạn tìm thấy kết thúc của T2, trong trường hợp đó bạn có một lần truy cập: cây của bạn T2 thực sự là một cây con của T1.

Nếu bạn biết độ sâu của mỗi nút đơn của T1 (từ lá đến nút), bạn có thể bỏ qua bất kỳ nút nào không sâu như cây con bạn đang tìm kiếm. Điều này có thể giúp bạn loại bỏ rất nhiều so sánh không cần thiết. Giả sử rằng T1 và T2 cân bằng, thì cây T1 sẽ có tổng độ sâu là 20 (2**20>1,000,000) và cây T2 sẽ có độ sâu 7 (2**7>100). Bạn sẽ chỉ phải đi bộ 13 lớp đầu tiên của T1 (8192 nodes -? Hay là 14 lớp và 16384 nodes) và sẽ có thể bỏ qua khoảng 90% T1 ...

Tuy nhiên, nếu bằng cách subtree bạn có nghĩa là các nút lá của T2 cũng là các nút lá của T1, thì bạn có thể thực hiện lần duyệt đầu tiên của T1 và tính toán độ sâu của mỗi nút (khoảng cách từ lá đến nút) và sau đó chỉ kiểm tra các subtrees cùng chiều sâu với T2.

Answer 3

Tôi đề nghị một thuật toán, sử dụng tiền xử lý:

1) Pre-quá trình cây T1, giữ danh sách của tất cả các rễ cây con có thể (danh sách bộ nhớ cache sẽ có một triệu lần nhập cảnh);

2) Sắp xếp danh sách bộ nhớ đệm đã lưu trong bộ nhớ cache theo thứ tự dữ liệu giảm dần, được giữ trong thư mục gốc. Bạn có thể chọn chức năng sắp xếp thanh lịch hơn, ví dụ, phân tích cú pháp một cây ký tự thành chuỗi.

3) Sử dụng tìm kiếm nhị phân để xác định vị trí cây con cần thiết. Bạn có thể nhanh chóng từ chối các subtrees, với số lượng nút, không bằng số T2 của các nút (hoặc với độ sâu khác nhau).

Lưu ý rằng các bước 1) và 2) chỉ được thực hiện một lần, sau đó bạn có thể thử nghiệm nhiều ứng cử viên cây con, sử dụng cùng một kết quả được xử lý trước.

Answer 4

Tôi không chắc chắn, cho dù ý tưởng của tôi là chính xác. Tuy nhiên, đối với của bạn persual.

1. Tiến hành đi bộ theo thứ tự trong Cây 1 & Cây 2, gọi nó là P1 và P2.
2. So sánh P1 & P2. Nếu chúng khác nhau. Cây không phải là cây con. Lối thoát.
3. Nếu chúng giống nhau hoặc P1 chứa trong P2. Bạn có thể quyết định cái nào là cây con.

Answer 5

Nếu bạn là bộ nhớ/lưu trữ bị ràng buộc (tức là không thể trước thao tác và lưu trữ các cây trong hình thức thay thế), có thể bạn sẽ không thể làm bất cứ điều gì tốt hơn so với việc tìm kiếm brute force được đề xuất bởi một số khác câu trả lời (đi ngang P1 tìm kiếm gốc phù hợp của P2, duyệt qua cả hai để xác định liệu nút trên thực tế là gốc của một cây con phù hợp, tiếp tục với quá trình truyền tải ban đầu nếu nó không khớp). Tìm kiếm này hoạt động trong O (n * m) trong đó n là kích thước của P1 và m là kích thước của P2. Với kiểm tra độ sâu và tối ưu hóa tiềm năng khác tùy thuộc vào dữ liệu cây bạn có sẵn, người này được tối ưu hóa một chút, nhưng nó vẫn thường là O (n * m). Tùy thuộc vào hoàn cảnh cụ thể của bạn, đây có thể là cách tiếp cận hợp lý duy nhất.

Nếu bạn không nhớ/lưu trữ bị ràng buộc và không ngại một chút phức tạp, tôi tin rằng điều này có thể được cải thiện để O (n + m) bằng cách giảm xuống một vấn đề longest common substring với sự giúp đỡ của một generalized suffix tree. Một số cuộc thảo luận về vấn đề này cho một vấn đề tương tự có thể được tìm thấy here. Có lẽ khi tôi có nhiều thời gian hơn, tôi sẽ quay lại và chỉnh sửa với nhiều chi tiết cụ thể về việc triển khai.

Answer 6

Nếu được đưa vào gốc của cả hai cây, và cho rằng các nút có cùng loại, tại sao sau đó chỉ xác định rằng gốc của T2 là T1 không đủ?

Tôi giả định rằng "cho một cây T" có nghĩa là đưa một con trỏ tới gốc của T và kiểu dữ liệu của nút.

Trân trọng.

Answer 7

Tôi nghĩ rằng chúng ta cần phải đi theo sức mạnh vũ phu, nhưng tại sao bạn cần phải phù hợp với cây sau khi bạn tìm thấy gốc của T2 trong T1. Nó không giống như khi chúng ta không được phép tìm thấy nếu cây giống hệt nhau. (Sau đó chúng ta chỉ cần so sánh toàn bộ cây)

Bạn được cung cấp cây T1 và T2, con trỏ chứ không phải giá trị.

Nếu nút T2 (là con trỏ), có mặt trong cây T1.

Sau đó cây T2 là cây con của T1.

---

Edit:

Chỉ khi nó nói rằng T2 thực sự là một cây khác nhau bởi đối tượng khôn ngoan, và chúng ta cần phải tìm ra rằng nếu có một Subtree trong T1, đó là giống hệt nhau để T2.

Sau đó, điều này sẽ không hoạt động.

Và chúng tôi không có lựa chọn nào khác ngoài các giải pháp đã được thảo luận ở đây.

Answer 8

Giả sử chúng ta có T1 là cây cha và T2 làm cây có thể là cây con của T1. Làm như sau. Giả định được thực hiện là T1 và T2 là cây nhị phân mà không có bất kỳ yếu tố cân bằng nào.

1) Tìm kiếm gốc của T2 trong T1. Nếu không tìm thấy T2 không phải là một cây con. Tìm kiếm phần tử trong BT sẽ mất thời gian O (n).

2) Nếu tìm thấy phần tử, hãy thực hiện tra cứu trước của T1 từ phần tử gốc của nút T2. Điều này sẽ mất thời gian o (n). Thực hiện quá trình truyền tải trước của T2. Sẽ mất thời gian O (n). Kết quả của quá trình truyền tải trước khi đặt hàng có thể được lưu trữ trong ngăn xếp. Chèn trong ngăn xếp sẽ chỉ có O (1).

3) Nếu kích thước của hai ngăn xếp không bằng nhau, T2 không phải là một cây con.

4) Bật một phần tử từ mỗi ngăn xếp và kiểm tra tính bình đẳng. Nếu không khớp, T2 không phải là một cây con.

5) Nếu tất cả các elments phù hợp với T2 là một cây con.

Answer 9

Tôi giả định rằng cây của bạn là cây bất biến vì vậy bạn không bao giờ thay đổi bất kỳ cây con nào (bạn không làm set-car! trong cách nói), nhưng bạn chỉ đang xây dựng cây mới từ lá hoặc từ cây hiện có.

Sau đó, tôi khuyên cố giữ trong mọi nút (hoặc subtree) mã băm của nút đó. Theo cách nói C, hãy khai báo các cây là

struct tree_st { 
    const unsigned hash; 
    const bool isleaf; 
    union { 
    const char*leafstring; // when isleaf is true 
    struct { // when isleaf is false 
     const struct tree_st* left; 
     const struct tree_st* right; 
    }; 
    }; 
}; 

rồi tính giá trị băm tại thời điểm xây dựng và khi so sánh các nút cho bình đẳng đầu tiên so sánh giá trị băm của chúng cho bình đẳng; hầu hết thời gian mã băm sẽ khác nhau (và bạn sẽ không bận tâm so sánh nội dung).

Đây là một chức năng xây dựng lá có thể:

struct tree_st* make_leaf (const char*string) { 
    assert (string != NULL); 
    struct tree_st* t = malloc(sizeof(struct tree_st)); 
    if (!t) { perror("malloc"); exit(EXIT_FAILURE); }; 
    t->hash = hash_of_string(string); 
    t->isleaf = true; 
    t->leafstring = string; 
    return t; 
} 

Chức năng để tính toán một mã băm là

unsigned tree_hash(const struct tree_st *t) { 
    return (t==NULL)?0:t->hash; 
} 

Chức năng để xây dựng một nút từ hai subtrees sleft & sright được

struct tree_st*make_node (const struct tree_st* sleft, 
          const struct tree_st* sright) { 
    struct tree_st* t = malloc(sizeof(struct tree_st)); 
    if (!t) { perror("malloc"); exit(EXIT_FAILURE); }; 
    /// some hashing composition, e.g. 
    unsigned h = (tree_hash(sleft)*313)^(tree_hash(sright)*617); 
    t->hash = h; 
    t->left = sleft; 
    t->right = sright; 
    return t; 
} 

The com pare chức năng (hai cây tx & ty) tận dụng lợi thế rằng nếu hashcodes là khác nhau là khác nhau comparands

bool equal_tree (const struct tree_st* tx, const struct tree_st* ty) { 
    if (tx==ty) return true; 
    if (tree_hash(tx) != tree_hash(ty)) return false; 
    if (!tx || !ty) return false; 
    if (tx->isleaf != ty->isleaf) return false; 
    if (tx->isleaf) return !strcmp(tx->leafstring, ty->leafstring); 
    else return equal_tree(tx->left, ty->left) 
       && equal_tree(tx->right, ty->right); 

}

Hầu hết thời gian thử nghiệm tree_hash(tx) != tree_hash(ty) sẽ thành công và bạn sẽ không phải recurse.

Đọc khoảng hash consing.

Khi bạn có chức năng equal_tree dựa trên băm hiệu quả, bạn có thể sử dụng các kỹ thuật được đề cập trong các câu trả lời khác (hoặc trong sổ tay).

Answer 10

Một trong những cách đơn giản là viết() phương pháp is_equal cho cây và làm như sau,

bool contains_subtree(TNode*other) { 
    // optimization 
    if(nchildren < other->nchildren) return false; 
    if(height < other->height) return false; 

    // go for real check 
    return is_equal(other) || (left != NULL && left->contains_subtree(other)) || (right != NULL && right->contains_subtree(other)); 
} 

Lưu ý rằng is_equal() có thể được tối ưu hóa bằng cách sử dụng hashcode cho cây. Nó có thể được thực hiện theo cách đơn giản bằng cách lấy chiều cao của cây hoặc số lượng con hoặc phạm vi của các giá trị như hashcode.

bool is_equal(TNode*other) { 
    if(x != other->x) return false; 
    if(height != other->height) return false; 
    if(nchildren != other->nchildren) return false; 
    if(hashcode() != other->hashcode()) return false; 
    // do other checking for example check if the children are equal .. 
} 

Khi cây tương tự danh sách được liên kết, sẽ mất thời gian O (n). Chúng tôi cũng có thể sử dụng một số heuristic trong khi lựa chọn các trẻ em để so sánh.

bool contains_subtree(TNode*other) { 
    // optimization 
    if(nchildren < other->nchildren) return false; 
    if(height < other->height) return false; 

    // go for real check 
    if(is_equal(other)) return true; 
    if(left == NULL || right == NULL) { 
      return (left != NULL && left->contains_subtree(other)) || (right != NULL && right->contains_subtree(other)); 
    } 
    if(left->nchildren < right->nchildren) { // find in smaller child tree first 
      return (left->contains_subtree(other)) || right->contains_subtree(other); 
    } else { 
      return (right->contains_subtree(other)) || left->contains_subtree(other); 
    } 
} 

Một cách khác là để serialize cả cây như chuỗi và tìm thấy nếu chuỗi thứ hai (đăng từ T2) là sub-string của chuỗi đầu tiên (đăng từ T1).

Mã sau tuần tự hóa theo thứ tự trước.

void serialize(ostream&strm) { 
      strm << x << '('; 
      if(left) 
        left->serialize(strm); 
      strm << ','; 
      if(right) 
        right->serialize(strm); 
      strm << ')'; 
    } 

Và chúng ta có thể sử dụng một số thuật toán tối ưu hóa, ví dụ, Knuth–Morris–Pratt algorithm để tìm (có thể trong thời gian O (n) thời gian) sự tồn tại của các tiểu chuỗi và cuối cùng tìm thấy nếu một cây là một cây con của khác .

Một lần nữa, chuỗi có thể được nén hiệu quả với Burrows – Wheeler_transform. Và có thể bzgrep để tìm kiếm chuỗi con trong dữ liệu đã nén.

Cách khác là sắp xếp các cây con trong cây theo chiều cao và số lượng con.

bool compare(TNode*other) { 
    if(height != other->height) 
     return height < other->height; 

    return nchildren < other->nchildren; 
} 

Lưu ý rằng sẽ có các cây con O (n^2). Để giảm số lượng chúng tôi có thể sử dụng một số phạm vi dựa trên chiều cao. Ví dụ: chúng tôi chỉ có thể quan tâm đến các cây con có chiều cao 1000 đến 1500.

Khi dữ liệu được sắp xếp được tạo, có thể thực hiện tìm kiếm nhị phân trong đó và tìm xem liệu nó có tập hợp con trong O (lg n) hay không thời gian (xem xét rằng không có bản sao trong dữ liệu được sắp xếp).