Bor

Bor, kenarlarında semboller olan köklü bir ağaç olan bir dizi diziyi depolamak için kullanılan bir veri yapısıdır. < /div>
Her bir bor köşesi, bazı eklenen dizelerin bir önekine karşılık gelir. Bu ön ekin kendisi, kökten bu tepe noktasına giden yoldaki kenarlara sırayla karakterler yazılarak elde edilir. Aynı zamanda, varolan her öneke tam olarak bir tepe noktası karşılık gelir. Bor kökü, boş bir dizeye karşılık gelir.

{be, bee, can, cat, cd}
için bor örneği


Turuncu, kümedeki kelimelere karşılık gelen köşeleri gösterir. Bunlara terminaller denir.

Borun depolanması ve ona satır eklenmesi için kod aşağıdadır. Bu yöntem, deliği bir dizi aracılığıyla depolar. Eğitim için görev kodunda sunulan işaretçiler aracılığıyla bir uygulama da vardır.
  // dikkate alınan kelimelerdeki alfabe boyutu sabit int alfa = 26; // matkabın üst kısmı için yapı yapı Düğümü{ // komşuluk tablosu biçimindeki kenarların vektörü, yani: // next[0] - 0 numaralı karakterin üzerinden atlarken çocuk ('a') // next[1] - 1 numaralı karakterin üzerinden atlarken çocuk ('b') // vesaire. sonraki vektör; // Ekstra seçenekler // bu durumda, h tepe noktasının yüksekliği ve terminallik bayrağı int h; bol terim;; düğüm(int h) { next.resize(alph, -1); // başlangıçta kenarsız bu->h = h; // yükseklik belirtilene eşittir terim=yanlış; // üst varsayılan olarak terminal değildir } }; // köşelerin listesi, başlangıçta sıfır yükseklikte kök vektör trie(1, Düğüm(0)); // boruna bir dizi eklemek için fonksiyon geçersiz ekle(const string&s) { int v = 0; // kökten başlayarak geçerli tepe noktasının numarası forn(i, (int)s.size()) { int c = s[i] - 'a'; // dizedeki geçerli karakterin numarasını al // İstenen geçiş henüz mevcut değilse, yenisini yapacağız if (trie[v].sonraki[c] == -1) { trie[v].sonraki[c] = (int)trie.size(); // yeni köşe numarası   // mevcut matkap boyutu (0 numaralandırma ile) trie.push_back(Düğüm(trie[v].h + 1)); // yüksekliği 1 olan yeni bir köşe oluştur } v = trie[v].sonraki[c]; // istenen kenar boyunca ilerleyin } // zirveye ulaştığımızda,   // dizenin tamamıyla eşleşen,   // sonra terminal olarak işaretle trie[v].terim = doğru; }
Bordan satırların silinmesini desteklemeniz gerekiyorsa, muhtemelen sahtekâr olacaktır. Yani, uçbirim işaretini kaldırın (veya belki de bayrak yerine bir değişken numarası kaydetmeniz gerekir) ve boron ağacının kendisini değiştirmeden bırakın.

Böylece, ekleme/arama/haksız silme, sorgu dizesinin uzunluğundan itibaren doğrusal zamanda çalışır.

Borun kendisi, en kötü durumda, O(n|Σ|) belleğini kaplar, burada n tüm dizilerin toplam uzunluğudur ve Σ > - kullanılan dizelerin alfabesi.