streamalism.org

1. סקירה כללית

מבני נתונים מהווים נכס מכריע בתכנות מחשבים, וחשוב מאוד לדעת מתי ולמה להשתמש בהם.

מאמר זה הוא מבוא קצר למבנה הנתונים של טרי (מבוטא "נסה"), יישומו וניתוח המורכבות.

2. טרי

טריה הוא מבנה נתונים נפרד שאינו ידוע למדי או מוזכר באופן נרחב בקורסי אלגוריתמים טיפוסיים, אך עם זאת חשוב.

טריייה (המכונה גם עץ דיגיטלי) ולעיתים אף עץ רדיקס או עץ קידומת (שכן ניתן לחפש אותם על ידי קידומות), הוא מבנה עץ מסודר, המנצל את המקשים שהוא מאחסן - בדרך כלל מיתרים.

מיקומו של צומת בעץ מגדיר את המפתח אליו נקשר אותו הצומת, מה שהופך ניסיונות שונים בהשוואה לעצי חיפוש בינאריים, בהם צופן מאחסן מפתח שמתאים רק לאותו צומת.

לכל צאצאי הצומת יש קידומת משותפת של a חוּט הקשורים לאותו צומת, ואילו השורש משויך לריק חוּט.

הנה יש לנו תצוגה מקדימה של TrieNode בה נשתמש ביישום שלנו טרי:

מחלקה ציבורית TrieNode {ילדים HashMap פרטיים; תוכן מחרוזת פרטי; isWord בוליאני פרטי; // ...}

יתכנו מקרים בהם טריה הוא עץ חיפוש בינארי, אך באופן כללי, אלה שונים. גם עצי חיפוש בינאריים וגם ניסיונות הם עצים, אך לכל צומת בעצי חיפוש בינאריים תמיד יש שני ילדים, ואילו צמתים של נסיונות, לעומת זאת, יכולים להכיל יותר.

בטריאה, כל צומת (למעט צומת השורש) מאחסן תו אחד או ספרה. על ידי חציית הטרייה מצומת השורש לצומת מסוים נ, ניתן ליצור קידומת נפוצה של תווים או ספרות המשותפת לענפים אחרים של הטרי.

על ידי מעבר במעלה הטרי מצומת עלה לצומת השורש, א חוּט או ניתן ליצור רצף ספרות.

הנה ה טרי מחלקה, המייצגת יישום של מבנה נתוני הטרי:

Class class Trie {שורש פרטי של TrieNode; // ...}

3. פעולות נפוצות

עכשיו, בואו נראה כיצד ליישם פעולות בסיסיות.

3.1. הכנסת אלמנטים

הפעולה הראשונה שתיאר היא הכנסת צמתים חדשים.

לפני שנתחיל ביישום, חשוב להבין את האלגוריתם:

1. הגדר צומת נוכחי כצומת שורש
2. הגדר את האות הנוכחית כמו האות הראשונה של המילה
3. אם לצומת הנוכחי כבר יש התייחסות קיימת לאות הנוכחית (דרך אחד האלמנטים בשדה "ילדים"), הגדר את הצומת הנוכחי לאותו צומת הפניה. אחרת, צור צומת חדש, הגדר את האות שווה לאות הנוכחית, וכן אתחל את הצומת הנוכחי לצומת חדש זה
4. חזור על שלב 3 עד לחציית המפתח

המורכבות של פעולה זו היא עַל), איפה נ מייצג את גודל המפתח.

להלן יישום האלגוריתם הזה:

הוסף חלל ציבורי (מילת מחרוזת) {TrieNode הנוכחי = שורש; עבור (char l: word.toCharArray ()) {current = current.getChildren (). computeIfAbsent (l, c -> TrieNode חדש ()); } current.setEndOfWord (נכון); }

בואו נראה כיצד נוכל להשתמש בשיטה זו כדי להכניס אלמנטים חדשים לטרייה:

Trie פרטי createExampleTrie () {Trie trie = Trie חדש (); trie.insert ("תכנות"); trie.insert ("זה"); trie.insert ("a"); trie.insert ("דרך"); trie.insert ("of"); trie.insert ("חיים"); החזרת טריה; }

אנו יכולים לבדוק כי הטרי כבר מאוכלס בצמתים חדשים מהמבחן הבא:

@Test הציבור בטל givenATrie_WhenAddingElements_ThenTrieNotEmpty () {Trie trie = createTrie (); assertFalse (trie.isEmpty ()); }

3.2. מציאת אלמנטים

בואו נוסיף כעת שיטה לבדוק אם אלמנט מסוים כבר קיים בטרייה:

1. השג ילדים מהשורש
2. חזר דרך כל דמות של חוּט
3. בדוק אם הדמות הזו היא כבר חלק מתת-תנועה. אם זה לא נמצא בשום מקום בטרי, הפסק את החיפוש וחזור שֶׁקֶר
4. חזור על השלב השני והשלישי עד שלא נשאר שום תו ב חוּט. אם סוף ה חוּט הוא הגיע, תחזור נָכוֹן

המורכבות של אלגוריתם זה היא עַל), כאשר n מייצג את אורך המפתח.

יישום Java יכול להיראות כך:

ממצא בוליאני ציבורי (מילת מחרוזת) {TrieNode הנוכחי = שורש; עבור (int i = 0; i <word.length (); i ++) {char ch = word.charAt (i); צומת TrieNode = current.getChildren (). Get (ch); אם (node ​​== null) {return false; } הנוכחי = צומת; } להחזיר current.isEndOfWord (); }

ובפעולה:

@Test הציבור בטל givenATrie_WhenAddingElements_ThenTrieContainsThoseElements () {Trie trie = createExampleTrie (); assertFalse (trie.containsNode ("3")); assertFalse (trie.containsNode ("vida")); assertTrue (trie.containsNode ("חיים")); }

3.3. מחיקת אלמנט

מלבד הכנסה ומציאת אלמנט, ברור שאנחנו צריכים להיות מסוגלים למחוק אלמנטים.

לצורך תהליך המחיקה, עלינו לבצע את השלבים הבאים:

1. בדוק אם אלמנט זה כבר חלק מהטרי
2. אם האלמנט נמצא, הסר אותו מהטרי

המורכבות של אלגוריתם זה היא עַל), כאשר n מייצג את אורך המפתח.

בואו נסתכל במהירות על היישום:

מחיקה בטלה ציבורית (מילה מחרוזת) {מחיקה (שורש, מילה, 0); } מחיקה בוליאנית פרטית (TrieNode הנוכחי, מילת מחרוזת, אינדקס int) {if (index == word.length ()) {if (! current.isEndOfWord ()) {return false; } current.setEndOfWord (שקר); להחזיר current.getChildren (). isEmpty (); } char ch = word.charAt (אינדקס); צומת TrieNode = current.getChildren (). Get (ch); אם (node ​​== null) {return false; } בוליאני shouldDeleteCurrentNode = מחק (צומת, מילה, אינדקס + 1) &&! node.isEndOfWord (); אם (shouldDeleteCurrentNode) {current.getChildren (). remove (ch); להחזיר current.getChildren (). isEmpty (); } להחזיר שקר; }

ובפעולה:

@Test בטל כאשרDeletingElements_ThenTreeDoesNotContainThoseElements () {Trie trie = createTrie (); assertTrue (trie.containsNode ("תכנות")); trie.delete ("תכנות"); assertFalse (trie.containsNode ("תכנות")); }

4. מסקנה

במאמר זה ראינו מבוא קצר למבנה נתוני ה- trie ולפעולותיו הנפוצות ביותר ויישומם.

קוד המקור המלא לדוגמאות המוצגות במאמר זה ניתן למצוא באתר GitHub.