குறியீட்டு பைனரி மரம்

நான் பின்வரும் வகை பிரச்சனையை சந்தித்தேன். பின்வரும் செயல்பாடுகளை வழங்கும் தரவு சேமிப்பக கொள்கலனை செயல்படுத்த வேண்டியது அவசியம்:

• புதிய உறுப்பைச் செருகவும்
• வரிசை எண் மூலம் உறுப்பை அகற்று
• வரிசை எண் மூலம் உறுப்பு கிடைக்கும்
• தரவு வரிசைப்படுத்தப்பட்ட வடிவத்தில் சேமிக்கப்படுகிறது

தரவு தொடர்ந்து சேர்க்கப்படுகிறது மற்றும் அகற்றப்படுகிறது, கட்டமைப்பு வேகமான செயல்பாட்டு வேகத்தை உறுதி செய்ய வேண்டும். முதலில் நான் நிலையான கொள்கலன்களைப் பயன்படுத்தி அத்தகைய விஷயத்தை செயல்படுத்த முயற்சித்தேன் வகுப்பு. இந்தப் பாதை வெற்றி மகுடம் சூடவில்லை, நானே எதையாவது செயல்படுத்த வேண்டும் என்ற புரிதல் வந்தது. பைனரி சர்ச் ட்ரீயைப் பயன்படுத்துவதே நினைவுக்கு வந்தது. ஏனெனில், வரிசைப்படுத்தப்பட்ட வடிவத்தில் தரவை வேகமாகச் செருகுதல், நீக்குதல் மற்றும் சேமிப்பது ஆகியவற்றின் தேவையை இது பூர்த்தி செய்கிறது. மரம் மாறும்போது அனைத்து கூறுகளையும் எவ்வாறு அட்டவணைப்படுத்துவது மற்றும் குறியீடுகளை மீண்டும் கணக்கிடுவது எப்படி என்பதை கண்டுபிடிப்பதே எஞ்சியுள்ளது.

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. அத்தகைய விசையுடன் ஒரு முனை ஏற்கனவே இருந்தால், மதிப்பை மேலெழுதுவோம் மற்றும் ரூட்டிற்குச் செல்வோம், நாம் கடந்து சென்ற அனைத்து முனைகளின் எடைகளிலும் ஏற்படும் மாற்றங்களை ரத்துசெய்வோம்.
ஒரு முனை அகற்றப்பட்டால், நாம் கீழே சென்று, கடந்து செல்லும் முனைகளின் எடையைக் குறைக்கிறோம்.

குறியீடுகள்

இப்போது எப்படி குறியீட்டு முனைகளுக்கு செல்லலாம். முனைகள் அவற்றின் குறியீட்டை வெளிப்படையாக சேமிக்காது, இது கணுக்களின் எடையின் அடிப்படையில் கணக்கிடப்படுகிறது. அவர்கள் தங்கள் குறியீட்டை சேமித்து வைத்திருந்தால், அது தேவைப்படும் ஓ (n) மரத்தின் ஒவ்வொரு மாற்றத்திற்குப் பிறகும் அனைத்து முனைகளின் குறியீடுகளையும் புதுப்பிக்கும் நேரம்.
காட்சி பிரதிநிதித்துவத்திற்கு செல்லலாம். எங்கள் மரம் காலியாக உள்ளது, அதில் 1வது முனையைச் சேர்ப்போம்:

முதல் முனையில் ஒரு குறியீட்டு உள்ளது 0, இப்போது 2 வழக்குகள் சாத்தியமாகும். முதலாவதாக, ரூட் உறுப்புகளின் குறியீடு மாறும், இரண்டாவதாக அது மாறாது.

வேரில், இடது துணை மரத்தின் எடை 1.

இரண்டாவது வழக்கு:

அதன் இடது துணை மரத்தின் எடை 0 ஆக இருந்ததால் ரூட்டின் குறியீடு மாறவில்லை.

ஒரு முனையின் குறியீடு அதன் இடது துணை மரத்தின் எடை + பெற்றோரிடமிருந்து அனுப்பப்பட்ட எண்ணாக கணக்கிடப்படுகிறது. இந்த எண் என்ன?, இது குறியீட்டு கவுண்டர், ஆரம்பத்தில் இது சமம் 0, ஏனெனில் வேருக்கு பெற்றோர் இல்லை. இடது குழந்தை அல்லது வலதுபுறம் நாம் எங்கு செல்கிறோம் என்பதைப் பொறுத்தது. இடதுபுறம் இருந்தால், கவுண்டரில் எதுவும் சேர்க்கப்படாது. தற்போதைய முனையின் குறியீட்டை வலதுபுறத்தில் சேர்த்தால்.

எடுத்துக்காட்டாக, விசை 8 (ரூட்டின் சரியான குழந்தை) கொண்ட ஒரு தனிமத்தின் குறியீடு எவ்வாறு கணக்கிடப்படுகிறது. இது "ரூட் இன்டெக்ஸ்" + "விசை 8 உடன் முனையின் இடது சப்ட்ரீயின் எடை" + "1" == 3 + 2 + 1 == 6
விசை 6 உடன் உள்ள உறுப்பின் குறியீடு "ரூட் இன்டெக்ஸ்" + 1 == 3 + 1 == 4

அதன்படி, குறியீட்டின் மூலம் ஒரு உறுப்பைப் பெறவும் நீக்கவும் நேரம் எடுக்கும் ஓ (பதிவு 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));
}

முடிவுகளை

• ஒரு புதிய உறுப்பு செருகல் நிகழ்கிறது ஓ (பதிவு n)
• வரிசை எண் மூலம் ஒரு உறுப்பை நீக்குவது இதில் நிகழ்கிறது ஓ (பதிவு n)
• வரிசை எண் மூலம் ஒரு உறுப்பைப் பெறுவது இதில் நிகழ்கிறது ஓ (பதிவு n)

வேகம் ஓ (பதிவு n) எல்லா தரவும் வரிசைப்படுத்தப்பட்ட வடிவத்தில் சேமிக்கப்படுவதற்கு நாங்கள் பணம் செலுத்துகிறோம்.

அத்தகைய அமைப்பு எங்கு பயனுள்ளதாக இருக்கும் என்று எனக்குத் தெரியவில்லை. மரங்கள் எவ்வாறு செயல்படுகின்றன என்பதை மீண்டும் ஒருமுறை புரிந்துகொள்ள ஒரு புதிர். உங்கள் கவனத்திற்கு நன்றி.

குறிப்புகள்

• மரத்தின் மூல குறியீடு

செயல்பாட்டின் வேகத்தை சரிபார்க்க திட்டத்தில் சோதனை தரவு உள்ளது. மரம் நிரம்புகிறது 1000000 உறுப்புகள். மற்றும் உறுப்புகளின் தொடர்ச்சியான நீக்கம், செருகல் மற்றும் மீட்டெடுப்பு உள்ளது 1000000 ஒருமுறை. அது 3000000 செயல்பாடுகள். முடிவு மிகவும் நன்றாக இருந்தது ~ 8 வினாடிகள்.

ஆதாரம்: www.habr.com