ਇੰਡੈਕਸਡ ਬਾਈਨਰੀ ਟ੍ਰੀ

ਮੈਨੂੰ ਹੇਠ ਦਿੱਤੀ ਸਮੱਸਿਆ ਦਾ ਸਾਹਮਣਾ ਆਇਆ. ਇੱਕ ਡੇਟਾ ਸਟੋਰੇਜ ਕੰਟੇਨਰ ਨੂੰ ਲਾਗੂ ਕਰਨਾ ਜ਼ਰੂਰੀ ਹੈ ਜੋ ਹੇਠਾਂ ਦਿੱਤੀ ਕਾਰਜਕੁਸ਼ਲਤਾ ਪ੍ਰਦਾਨ ਕਰਦਾ ਹੈ:

• ਨਵਾਂ ਤੱਤ ਸ਼ਾਮਲ ਕਰੋ
• ਸੀਰੀਅਲ ਨੰਬਰ ਦੁਆਰਾ ਤੱਤ ਹਟਾਓ
• ਆਰਡੀਨਲ ਨੰਬਰ ਦੁਆਰਾ ਤੱਤ ਪ੍ਰਾਪਤ ਕਰੋ
• ਡੇਟਾ ਨੂੰ ਕ੍ਰਮਬੱਧ ਰੂਪ ਵਿੱਚ ਸਟੋਰ ਕੀਤਾ ਜਾਂਦਾ ਹੈ

ਡੇਟਾ ਨੂੰ ਲਗਾਤਾਰ ਜੋੜਿਆ ਅਤੇ ਹਟਾਇਆ ਜਾ ਰਿਹਾ ਹੈ, ਬਣਤਰ ਨੂੰ ਤੇਜ਼ ਸੰਚਾਲਨ ਦੀ ਗਤੀ ਨੂੰ ਯਕੀਨੀ ਬਣਾਉਣਾ ਚਾਹੀਦਾ ਹੈ. ਪਹਿਲਾਂ ਮੈਂ ਸਟੈਂਡਰਡ ਕੰਟੇਨਰਾਂ ਦੀ ਵਰਤੋਂ ਕਰਕੇ ਅਜਿਹੀ ਚੀਜ਼ ਨੂੰ ਲਾਗੂ ਕਰਨ ਦੀ ਕੋਸ਼ਿਸ਼ ਕੀਤੀ ਐੱਸ. ਇਹ ਮਾਰਗ ਸਫਲਤਾ ਨਾਲ ਤਾਜ ਨਹੀਂ ਸੀ ਅਤੇ ਸਮਝ ਆਈ ਕਿ ਮੈਨੂੰ ਆਪਣੇ ਆਪ ਨੂੰ ਕੁਝ ਲਾਗੂ ਕਰਨ ਦੀ ਜ਼ਰੂਰਤ ਹੈ. ਇਕੋ ਗੱਲ ਜੋ ਮਨ ਵਿਚ ਆਈ ਉਹ ਸੀ ਬਾਈਨਰੀ ਖੋਜ ਦੇ ਰੁੱਖ ਦੀ ਵਰਤੋਂ ਕਰਨਾ. ਕਿਉਂਕਿ ਇਹ ਕ੍ਰਮਬੱਧ ਰੂਪ ਵਿੱਚ ਡੇਟਾ ਦੇ ਤੇਜ਼ ਸੰਮਿਲਨ, ਮਿਟਾਉਣ ਅਤੇ ਸਟੋਰੇਜ ਦੀ ਜ਼ਰੂਰਤ ਨੂੰ ਪੂਰਾ ਕਰਦਾ ਹੈ। ਸਭ ਕੁਝ ਇਹ ਪਤਾ ਲਗਾਉਣਾ ਹੈ ਕਿ ਸਾਰੇ ਤੱਤਾਂ ਨੂੰ ਕਿਵੇਂ ਸੂਚਕਾਂਕ ਕਰਨਾ ਹੈ ਅਤੇ ਜਦੋਂ ਰੁੱਖ ਬਦਲਦਾ ਹੈ ਤਾਂ ਸੂਚਕਾਂਕ ਦੀ ਮੁੜ ਗਣਨਾ ਕਰਨੀ ਹੈ।

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) ਟ੍ਰੀ ਵਿੱਚ ਹਰੇਕ ਤਬਦੀਲੀ ਤੋਂ ਬਾਅਦ ਸਾਰੇ ਨੋਡਾਂ ਦੇ ਸੂਚਕਾਂਕ ਨੂੰ ਅੱਪਡੇਟ ਕਰਨ ਦਾ ਸਮਾਂ।
ਆਓ ਇੱਕ ਵਿਜ਼ੂਅਲ ਪ੍ਰਤੀਨਿਧਤਾ ਵੱਲ ਵਧੀਏ। ਸਾਡਾ ਰੁੱਖ ਖਾਲੀ ਹੈ, ਆਓ ਇਸ ਵਿੱਚ ਪਹਿਲਾ ਨੋਡ ਜੋੜੀਏ:

ਪਹਿਲੇ ਨੋਡ ਵਿੱਚ ਇੱਕ ਸੂਚਕਾਂਕ ਹੁੰਦਾ ਹੈ 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