Trie adatstruktúra C/C++-ban

Trie Adatstruktúra C/C++-ban

Bevezetés

A trie, más néven prefix tree, egy olyan adatstruktúra, amely karakterláncokat tárol és keres. A karakterláncokat egy fában tárolja, ahol minden csomópont egy karaktert képvisel. A gyökér csomópont üres karaktert képvisel, és minden csomópontból a karakterláncok egy betűvel növekvő karakterláncokat ábrázoló csomópontok indulnak ki.

A trie adatstruktúrának számos előnye van:

* Gyors keresés: A trie lehetővé teszi a karakterláncok keresését O(m) időben, ahol m a keresett karakterlánc hossza.
* Prefix keresés: A trie támogatja az előtag kereséseket, amelyek megtalálják azokat a karakterláncokat, amelyek egy adott prefixszel kezdődnek.
* Memóriahatékonyság: A trie csak a karakterláncokban egyedi karaktereket tárol, ami memóriahatékonyabbá teszi, mint az olyan adatstruktúrák, mint a tömbök vagy a szólisták.

Csomópont szerkezete

Egy trie csomópontja általában a következő információkat tartalmazza:

* karakter: A csomóponthoz társított karakter
* gyermekek: A csomópontból kivezető gyermekeket tartalmazó tároló
* szó_vége: Egy jelző, amely megmutatja, hogy a csomópont egy teljes karakterlánc végét jelöli-e

Műveletek

A trie adatstruktúrán végrehajtható leggyakoribb műveletek a következők:

Karakterlánc beszúrása

1. Lépés: Navigáció a beillesztendő karakterláncig
* Hozzon létre egy mutató az aktuális csomópontra, amely a gyökér csomópontra mutat.
* Cikluson belül lépkedjen végig a karakterlánc karakterein, és hozzon létre új csomópontokat a hiányzó karakterekhez.
* Ha egy létező csomópontot talál, lépjen arra a csomópontra.

2. Lépés: Szó végét jelölő beállítása
* Ha a karakterlánc utolsó karakteréhez ért, állítsa a csomópont szó_vége értékét igaz értékre.

Karakterlánc keresése

1. Lépés: Navigáció a keresett karakterláncig
* Hozzon létre egy mutató az aktuális csomópontra, amely a gyökér csomópontra mutat.
* Cikluson belül lépkedjen végig a karakterlánc karakterein, és kövesse a megfelelő gyermekeket.

2. Lépés: Szó végét ellenőrzése
* Ha a karakterlánc utolsó karakteréhez ért, ellenőrizze a csomópont szó_vége tulajdonságát.
* Ha a szó_vége igaz, akkor a karakterlánc megtalálható a trie-ben.

Prefix keresése

1. Lépés: Navigáció a prefix végéig
* Hozzon létre egy mutató az aktuális csomópontra, amely a gyökér csomópontra mutat.
* Cikluson belül lépkedjen végig a prefix karakterein, és kövesse a megfelelő gyermekeket.

2. Lépés: Gyermekek átjárása
* Ha a prefix végéhez ért, járja be az adott csomópont összes gyermekét.
* A gyermekcsomópontok a prefixszel kezdődő összes karakterlánc utolsó karakterét ábrázolják.

C++ implementáció

Az alábbiakban egy C++ implementáció található a trie adatstruktúrához:

cpp
class TrieNode {
public:
bool isEndOfWord;
TrieNode* children[26];

TrieNode() {
isEndOfWord = false;
for (int i = 0; i < 26; i++) {
children[i] = nullptr;
}
}
};

class Trie {
public:
TrieNode* root;

Trie() {
root = new TrieNode();
}

void insert(string word) {
TrieNode* current = root;

for (char c : word) {
int index = c - 'a';
if (current->children[index] == nullptr) {
current->children[index] = new TrieNode();
}
current = current->children[index];
}

current->isEndOfWord = true;
}

bool search(string word) {
TrieNode* current = root;

for (char c : word) {
int index = c - 'a';
if (current->children[index] == nullptr) {
return false;
}
current = current->children[index];
}

return current->isEndOfWord;
}

bool startsWith(string prefix) {
TrieNode* current = root;

for (char c : prefix) {
int index = c - 'a';
if (current->children[index] == nullptr) {
return false;
}
current = current->children[index];
}

return true;
}
};


Következtetés

A trie adatstruktúra egy hatékony és sokoldalú adatstruktúra karakterláncok tárolására és keresésére. Gyors keresést, prefix keresést és memóriahatékony tárolást biztosít. A trie széles körben használják olyan alkalmazásokban, mint a szótárkeresés, az automatikus kiegészítés és a mintázatillesztés.

GYIK

* Mi a trie adatstruktúra célja?
* Karakterláncok tárolására és keresésére szolgál.

* Mi a fő előnye a trie-nek?
* Gyors keresést tesz lehetővé, és támogatja az előtag kereséseket.

* Milyen típusú alkalmazások használják a trie-ket?
* Szótárkeresés, automatikus kiegészítés, mintázatillesztés.

* Hogyan működik a trie adatstruktúra?
* Karakterláncokat tárol egy olyan fában, ahol minden csomópont egy karaktert képvisel.

* Meg tudja magyarázni a trie egyik csomópontjának szerkezetét?
* Tartalmazza az adott karaktert, a gyermekcsomópontokat és egy szóvégi jelzőt.

* Hogyan illesztene be egy karakterláncot a trie-be?
* Hozzon létre új csomópontokat a hiányzó karakterekhez, és állítsa a szóvégi jelzőt igazra az utolsó karakter csomópontján.

* Hogyan keresne meg egy karakterláncot a trie-ben?
* Navigáljon a trie-ben a karakterlánc karakterei alapján, és ellenőrizze a szóvégi jelzőt az utolsó karakter csomópontján.

* Meg tudná magyarázni, hogyan lehetne előtag keresést végrehajtani a trie-ben?
* Navigáljon a trie-ben az előtag karakterei alapján, és járja át az előtag végén található csomópont összes gyermekét.