درخت دودویی نمایه شده

من با نوع مشکل زیر مواجه شدم. لازم است یک محفظه ذخیره سازی داده پیاده سازی شود که عملکرد زیر را ارائه دهد:

• درج عنصر جدید
• حذف عنصر با شماره سریال
• عنصر را با عدد ترتیبی بدست آورید
• داده ها به شکل مرتب شده ذخیره می شوند

داده ها به طور مداوم اضافه و حذف می شوند، ساختار باید سرعت عملیات سریع را تضمین کند. در ابتدا سعی کردم چنین چیزی را با استفاده از کانتینرهای استاندارد از پیاده سازی کنم 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 (ورود به سیستم)، زیرا برای به دست آوردن عنصر مورد نظر ابتدا باید آن را پیدا کنیم (از ریشه به این عنصر پایین برویم).

عمق

بر اساس وزن، می توانید عمق درخت را نیز محاسبه کنید. برای تعادل لازم است.
برای این کار باید وزن گره فعلی را به عدد اول به توان 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 (ورود به سیستم)
• حذف یک عنصر با شماره سریال اتفاق می افتد O (ورود به سیستم)
• به دست آوردن یک عنصر با شماره سریال اتفاق می افتد O (ورود به سیستم)

سرعت O (ورود به سیستم) ما برای این واقعیت هزینه می کنیم که همه داده ها به شکل مرتب شده ذخیره می شوند.

من نمی دانم چنین ساختاری در کجا ممکن است مفید باشد. فقط یک پازل برای یک بار دیگر درک نحوه عملکرد درختان. با تشکر از توجه شما.

مراجع

• کد منبع درخت

این پروژه حاوی داده های آزمایشی برای بررسی سرعت عملیات است. درخت در حال پر شدن است 1000000 عناصر. و حذف، درج و بازیابی متوالی عناصر وجود دارد 1000000 یک بار. به این معنا که 3000000 عملیات نتیجه بسیار خوب بود ~ 8 ثانیه.

منبع: www.habr.com