עץ בינארי עם אינדקס

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

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

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

struct node_s {    
    data_t data;

    uint64_t weight; // вес узла

    node_t *left;
    node_t *right;

    node_t *parent;
};

המאמר יכיל יותר תמונות ותיאוריה מאשר קוד. ניתן לראות את הקוד בקישור למטה.

משקל

כדי להשיג זאת, העץ עבר שינוי קל, נוסף מידע נוסף על מִשׁקָל צוֹמֶת. משקל הצומת הוא מספר הצאצאים של צומת זה + 1 (משקל של אלמנט בודד).

פונקציה להשגת משקל הצומת:

uint64_t bntree::get_child_weight(node_t *node) {
    if (node) {
        return node->weight;
    }

    return 0;
}

משקל הסדין שווה בהתאמה ל 0.

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

כשהעץ שלנו ריק, משקלו הוא 0. בואו נוסיף לו אלמנט שורש:

משקל העץ הופך ל-1, משקל אלמנט השורש הופך ל-1. משקל אלמנט השורש הוא משקל העץ.

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

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

מדדים

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

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

בשורש, תת העץ השמאלי שוקל 1.

מקרה שני:

האינדקס של השורש לא השתנה מכיוון שהמשקל של תת העץ השמאלי שלו נשאר 0.

האינדקס של צומת מחושב כמשקל המשנה השמאלי שלו + המספר שהועבר מהאב. מה זה המספר הזה?, זהו מונה האינדקס, בהתחלה הוא שווה 0, כי לשורש אין הורה. ואז הכל תלוי איפה אנחנו יורדים לילד השמאלי או הימני. אם שמאלה, אז שום דבר לא מתווסף לדלפק. אם נוסיף את האינדקס של הצומת הנוכחי לימין.

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

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

עומק

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

קוד להמרת משקל לעומק.

/*
 * Возвращает первое число в степени 2, которое больше или ровно x
 */
uint64_t bntree::cpl2(uint64_t x) {
    x = x - 1;
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);
    x = x | (x >> 32);

    return x + 1;
}

/*
 * Двоичный логарифм от числа
 */
long bntree::ilog2(long d) {
    int result;
    std::frexp(d, &result);
    return result - 1;
}

/*
 * Вес к глубине
 */
uint64_t bntree::weight_to_depth(node_t *p) {
    if (p == NULL) {
        return 0;
    }

    if (p->weight == 1) {
        return 1;
    } else if (p->weight == 2) {
        return 2;
    }

    return this->ilog2(this->cpl2(p->weight));
}

תוצאות של

• הכנסת אלמנט חדש מתרחשת ב O (יומן n)
• מחיקת אלמנט לפי מספר סידורי מתרחשת ב O (יומן n)
• השגת אלמנט לפי מספר סידורי מתרחשת ב O (יומן n)

מְהִירוּת O (יומן n) אנו משלמים על העובדה שכל הנתונים מאוחסנים בצורה ממוינת.

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

תזכור

• קוד מקור של עץ

הפרויקט מכיל נתוני בדיקה לבדיקת מהירות הפעולה. העץ מתמלא 1000000 אלמנטים. ויש מחיקה, הכנסה ושליפה ברצף של אלמנטים 1000000 פַּעַם. זה 3000000 פעולות. התוצאה התבררה כטובה למדי ~ 8 שניות.

מקור: www.habr.com