সূচিবদ্ধ বাইনারি গাছ

আমি নিম্নলিখিত ধরনের সমস্যা জুড়ে এসেছি. নিম্নলিখিত কার্যকারিতা প্রদান করে এমন একটি ডেটা স্টোরেজ ধারক প্রয়োগ করা প্রয়োজন:

• নতুন উপাদান সন্নিবেশ করান
• সিরিয়াল নম্বর দ্বারা উপাদান সরান
• ক্রমিক সংখ্যা দ্বারা উপাদান পান
• তথ্য সাজানো আকারে সংরক্ষণ করা হয়

ডেটা ক্রমাগত যোগ করা এবং অপসারণ করা হচ্ছে, গঠন দ্রুত অপারেশন গতি নিশ্চিত করা আবশ্যক. প্রথমে আমি স্ট্যান্ডার্ড পাত্রে ব্যবহার করে এমন একটি জিনিস বাস্তবায়ন করার চেষ্টা করেছি এসটিডি. এই পথটি সাফল্যের সাথে মুকুট দেওয়া হয়নি এবং বোঝা গেল যে আমার নিজের কিছু বাস্তবায়ন করা দরকার। একমাত্র জিনিস যা মনে এসেছিল তা হল একটি বাইনারি অনুসন্ধান গাছ ব্যবহার করা। কারণ এটি সাজানো আকারে ডেটা দ্রুত সন্নিবেশ, মুছে ফেলা এবং সংরক্ষণের প্রয়োজনীয়তা পূরণ করে। যা অবশিষ্ট থাকে তা হল কিভাবে সমস্ত উপাদানগুলিকে সূচীকরণ করা যায় এবং গাছের পরিবর্তন হলে সূচকগুলি পুনরায় গণনা করা যায়।

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. যদি এই জাতীয় কী সহ একটি নোড ইতিমধ্যেই বিদ্যমান থাকে, তাহলে আমরা মানটি ওভাররাইট করব এবং রুট পর্যন্ত ফিরে যাব, আমরা পাস করা সমস্ত নোডের ওজনের পরিবর্তনগুলি বাতিল করব।
যদি একটি নোড সরানো হয়, তাহলে আমরা নিচে যাই এবং পাস করা নোডগুলির ওজন হ্রাস করি।

সূচকের

এখন আসুন কিভাবে নোড সূচী করা যায়। নোডগুলি স্পষ্টভাবে তাদের সূচক সংরক্ষণ করে না, এটি নোডগুলির ওজনের উপর ভিত্তি করে গণনা করা হয়। যদি তারা তাদের সূচক সংরক্ষণ করে, তাহলে এটি প্রয়োজন হবে উপর) গাছের প্রতিটি পরিবর্তনের পরে সমস্ত নোডের সূচী আপডেট করার সময়।
এর একটি চাক্ষুষ উপস্থাপনা এগিয়ে চলুন. আমাদের গাছটি খালি, আসুন এটিতে 1ম নোড যোগ করি:

প্রথম নোডের একটি সূচক আছে 0, এবং এখন 2 টি ক্ষেত্রে সম্ভব। প্রথমটিতে, মূল উপাদানটির সূচক পরিবর্তন হবে, দ্বিতীয়টিতে এটি পরিবর্তন হবে না।

মূলে, বাম সাবট্রির ওজন 1।

দ্বিতীয় ক্ষেত্রে:

মূলের সূচী পরিবর্তন হয়নি কারণ এর বাম উপবৃক্ষের ওজন 0 রয়ে গেছে।

একটি নোডের সূচকটি তার বাম উপবৃক্ষের ওজন + পিতামাতার কাছ থেকে পাস করা সংখ্যা হিসাবে গণনা করা হয়। এই সংখ্যাটি কী?, এটি সূচক কাউন্টার, প্রাথমিকভাবে এটি সমান 0, কারণ মূলের কোন পিতামাতা নেই। তারপর এটা সব নির্ভর করে যেখানে আমরা বাম সন্তান বা ডান এক নিচে যেতে. যদি বাম দিকে থাকে, তাহলে কাউন্টারে কিছুই যোগ করা হয় না। যদি আমরা বর্তমান নোডের সূচকটি ডানদিকে যোগ করি।

উদাহরণস্বরূপ, কী 8 (মূলের ডান সন্তান) সহ একটি উপাদানের সূচক কীভাবে গণনা করা হয়। এটি হল "রুট ইনডেক্স" + "8 কী সহ নোডের বাম সাবট্রির ওজন" + "1" == 3 + 2 + 1 == 6
কী 6 সহ উপাদানটির সূচকটি হবে "রুট সূচক" + 1 == 3 + 1 == 4

তদনুসারে, সূচক দ্বারা একটি উপাদান পেতে এবং মুছতে সময় লাগে ও (লগ এন), কারণ পছন্দসই উপাদান পেতে আমাদের প্রথমে এটি খুঁজে বের করতে হবে (মূল থেকে এই উপাদানটিতে যান)।

গভীরতা

ওজনের উপর ভিত্তি করে, আপনি গাছের গভীরতাও গণনা করতে পারেন। ভারসাম্য বজায় রাখার জন্য প্রয়োজনীয়।
এটি করার জন্য, বর্তমান নোডের ওজনকে অবশ্যই প্রথম সংখ্যা থেকে 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));
}

ফলাফল

• একটি নতুন উপাদান সন্নিবেশ ঘটে ও (লগ এন)
• সিরিয়াল নম্বর দ্বারা একটি উপাদান মুছে ফেলা হয় ও (লগ এন)
• ক্রমিক সংখ্যা দ্বারা একটি উপাদান প্রাপ্ত করা হয় ও (লগ এন)

গতি ও (লগ এন) আমরা এই সত্যের জন্য অর্থ প্রদান করি যে সমস্ত ডেটা সাজানো আকারে সংরক্ষণ করা হয়।

আমি জানি না এই ধরনের কাঠামো কোথায় উপযোগী হতে পারে। গাছগুলি কীভাবে কাজ করে তা আবার বোঝার জন্য কেবল একটি ধাঁধা। আপনার মনোযোগের জন্য আপনাকে ধন্যবাদ।

রেফারেন্স

• ট্রি সোর্স কোড

অপারেশনের গতি পরীক্ষা করার জন্য প্রকল্পটিতে পরীক্ষার ডেটা রয়েছে। গাছ ভরে যাচ্ছে 1000000 উপাদান এবং উপাদানগুলির একটি অনুক্রমিক মুছে ফেলা, সন্নিবেশ এবং পুনরুদ্ধার রয়েছে 1000000 একদা. এটাই 3000000 অপারেশন ফলাফল বেশ ভাল হতে পরিণত ~ 8 সেকেন্ড.

উত্স: www.habr.com