بور

Bor یک ساختار داده برای ذخیره مجموعه ای از رشته ها است که یک درخت ریشه دار با نمادها در لبه ها است. < /div>
هر رأس بور مربوط به پیشوندی از چند رشته اضافه شده است. این پیشوند خود با نوشتن متوالی کاراکترها در لبه های مسیر از ریشه تا این راس به دست می آید. در همان زمان، دقیقاً یک راس مربوط به هر پیشوند موجود است. ریشه Bor مربوط به یک رشته خالی است.

مثال بور برای {be, bee, can, cat, cd}



نارنجی رئوسی را نشان می دهد که با کلمات خود مجموعه مطابقت دارد. آنها ترمینال نامیده می شوند.

در زیر کد ذخیره بور و افزودن خطوط به آن آورده شده است. این روش حفره را از طریق یک آرایه ذخیره می کند. پیاده سازی از طریق اشاره گرها نیز وجود دارد که در کد وظیفه برای آموزش ارائه شده است.
  // اندازه الفبا در کلمات در نظر گرفته شده const int alpha = 26; // ساختار برای بالای مته گره ساختار{ // بردار یال ها به شکل جدول مجاورت، یعنی: // بعدی[0] - کودک هنگام پریدن از روی کاراکتر شماره 0 ('a') // بعدی[1] - کودک هنگام پریدن از روی کاراکتر شماره 1 ('b') // و غیره. برداربعدی; // گزینه های اضافی // در این مورد، ارتفاع راس h و پرچم پایانه int h; اصطلاح bool;; گره (int h) { next.resize(alph, -1); // ابتدا بدون لبه این->h = h; // ارتفاع برابر با مشخص شده است اصطلاح = نادرست; // top به طور پیش فرض ترمینال نیست } }; // لیست رئوس، در ابتدا ریشه در ارتفاع صفر vector trie(1, Node(0)); // تابع برای افزودن یک رشته به بور void add(const string&s) { int v = 0; // تعداد راس فعلی، از ریشه شروع می شود forn(i, (int)s.size()) { int c = s[i] - 'a'; // عدد کاراکتر فعلی در رشته را بدست آورید // اگر انتقال مورد نظر هنوز وجود نداشته باشد، یک انتقال جدید ایجاد می کنیم if (trie[v].next[c] == -1) { trie[v].next[c] = (int)trie.size(); // عدد راس جدید است   // اندازه مته فعلی (با شماره گذاری 0) trie.push_back(Node(trie[v].h + 1)); // یک راس جدید با ارتفاع 1 بیشتر ایجاد کنید } v = trye[v].next[c]; // در امتداد لبه مورد نظر حرکت کنید } // وقتی به اوج رسیدیم،   // که با کل رشته مطابقت دارد،   // سپس آن را به عنوان ترمینال علامت گذاری کنید trye[v].term = true; }
اگر نیاز به حمایت از حذف ردیف‌ها از بور دارید، احتمالاً نادرست است. یعنی به سادگی پرچم پایانه را حذف کنید (یا شاید به جای پرچم، باید یک عدد متغیر را ذخیره کنید)، و خود درخت بور را بدون تغییر رها کنید.

بنابراین، درج/جستجو/حذف ناعادلانه در زمان خطی از طول رشته پرس و جو کار می کند.

خود بور، در بدترین حالت، حافظه O(n|Σ|) را اشغال خواهد کرد، جایی که n طول کل تمام رشته ها و Σ > - الفبای رشته های مورد استفاده.