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

আমাকে নিম্নলিখিত কাজটি করতে হয়েছিল: এমন একটি ডেটা স্টোরেজ কন্টেইনার তৈরি করতে হতো যা নিম্নলিখিত কার্যকারিতাগুলো প্রদান করবে।

• একটি নতুন উপাদান যোগ করুন
• ক্রমিক সংখ্যা অনুসারে একটি উপাদান মুছে ফেলুন
• ক্রমিক সংখ্যা দ্বারা একটি উপাদান পান
• ডেটা সাজানো আকারে সংরক্ষণ করা হয়

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

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.

এরপরে, আমরা এই ধরনের একটি গাছের উদাহরণের চাক্ষুষ উপস্থাপনা দেখব। কালো রঙটি নোড কী (key) দেখাবে (এর মান দেখানো হবে না, কারণ সেটির কোনো প্রয়োজন নেই), লাল — নোডের ওজন, সবুজ — নোড সূচক।

যখন আমাদের ট্রি খালি থাকে, তখন এর ওয়েট হয় ০। চলুন এতে একটি রুট এলিমেন্ট যোগ করি:

ট্রি-টির ওয়েট ১ হয়ে যায়, রুট এলিমেন্টের ওয়েটও ১। রুট এলিমেন্টের ওয়েটই হলো ট্রি-টির ওয়েট।

চলুন আরও কয়েকটি উপাদান যোগ করা যাক:

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

সূচকের

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

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

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

দ্বিতীয় ঘটনা:

রুট ইনডেক্স পরিবর্তিত হয়নি, কারণ এর বাম সাবট্রির ওয়েট ০ রয়েছে।

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

উদাহরণস্বরূপ, ৮ কী-যুক্ত একটি এলিমেন্টের (রুটের ডান চাইল্ড) ইন্ডেক্স কীভাবে গণনা করা হয়? এটি হলো "রুট ইন্ডেক্স" + "৮ কী-যুক্ত নোডের বাম সাবট্রির ওয়েট" + "১" == ৩ + ২ + ১ == 6
৬ কী-যুক্ত এলিমেন্টের ইন্ডেক্স হবে "রুট ইন্ডেক্স" + 1 == 3 + 1 == 4

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

গভীরতা

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

ওজন থেকে গভীরতায় রূপান্তরের কোড।

/*
 * Возвращает первое число в степени 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 অপারেশনগুলো। ফলাফল বেশ ভালো ছিল: প্রায় ৮ সেকেন্ড।

উত্স: www.habr.com