Bor

Bor là cấu trúc dữ liệu để lưu trữ một tập hợp các chuỗi, là một cây có gốc với các ký hiệu trên các cạnh. < /div>
Mỗi đỉnh boron tương ứng với một tiền tố của một số chuỗi được thêm vào. Bản thân tiền tố này có được bằng cách viết tuần tự các ký tự trên các cạnh trên đường đi từ gốc đến đỉnh này. Đồng thời, chính xác một đỉnh tương ứng với mỗi tiền tố hiện có. Gốc Bor tương ứng với một chuỗi rỗng.

Ví dụ boron cho {be, bee, can, cat, cd}



Màu cam biểu thị các đỉnh tương ứng với các từ trong tập hợp. Chúng được gọi là thiết bị đầu cuối.

Dưới đây là mã để lưu trữ boron và thêm các dòng vào nó. Phương thức này lưu lỗ khoan thông qua một mảng. Ngoài ra còn có một triển khai thông qua con trỏ, được trình bày trong mã của nhiệm vụ dành cho đào tạo.
  // kích thước bảng chữ cái trong các từ được xem xét const int alpha = 26; // cấu trúc cho đỉnh của máy khoan nút cấu trúc { // vectơ các cạnh ở dạng bảng kề, nghĩa là: // next[0] - con khi nhảy qua ký tự số 0 ('a') // next[1] - con khi nhảy qua ký tự số 1 ('b') // vân vân. véc tơtiếp theo; // Tùy chọn thêm // trong trường hợp này, chiều cao của đỉnh h và cờ của thiết bị đầu cuối inth; thuật ngữ bool;; Nút (int h) { next.resize(alph, -1); // ban đầu không có cạnh này->h = h; // chiều cao bằng với quy định thuật ngữ = sai; // top không phải là terminal theo mặc định } }; // danh sách các đỉnh, ban đầu gốc ở độ cao bằng không vector trie(1, Nút(0)); // hàm thêm chuỗi vào boron void add(const string& s) { int v = 0; // số đỉnh hiện tại, bắt đầu từ gốc forn(i, (int)s.size()) { int c = s[i] - 'a'; // lấy số ký tự hiện tại trong chuỗi // nếu quá trình chuyển đổi mong muốn chưa tồn tại, thì chúng tôi sẽ tạo một quá trình chuyển đổi mới if (trie[v].next[c] == -1) { trie[v].next[c] = (int)trie.size(); // số đỉnh mới là   // kích thước mũi khoan hiện tại (có đánh số 0) trie.push_back(Nút(trie[v].h + 1)); // tạo 1 đỉnh mới có chiều cao thêm 1 } v = trie[v].next[c]; // di chuyển dọc theo cạnh mong muốn } // khi chúng tôi lên đến đỉnh,   // khớp với toàn bộ chuỗi,   // sau đó đánh dấu nó là thiết bị đầu cuối trie[v].term = true; }
Nếu bạn cần hỗ trợ xóa các hàng khỏi boron, thì có lẽ nó sẽ trở nên không trung thực. Nghĩa là, chỉ cần xóa cờ đầu cuối (hoặc, có lẽ, thay vì cờ, bạn sẽ cần lưu trữ một số thay đổi) và giữ nguyên bản thân cây boron.

Do đó, thao tác chèn/tìm kiếm/xóa không công bằng hoạt động theo thời gian tuyến tính tính từ độ dài của chuỗi truy vấn.

Trong trường hợp xấu nhất, bản thân boron sẽ chiếm bộ nhớ O(n|Σ|), trong đó n là tổng độ dài của tất cả các chuỗi và Σ > - bảng chữ cái của các chuỗi được sử dụng.