ಸೂಚ್ಯಂಕ ಬೈನರಿ ಮರ

ನಾನು ಈ ಕೆಳಗಿನ ರೀತಿಯ ಸಮಸ್ಯೆಯನ್ನು ಎದುರಿಸಿದೆ. ಕೆಳಗಿನ ಕಾರ್ಯವನ್ನು ಒದಗಿಸುವ ಡೇಟಾ ಶೇಖರಣಾ ಧಾರಕವನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸುವುದು ಅವಶ್ಯಕ:

• ಹೊಸ ಅಂಶವನ್ನು ಸೇರಿಸಿ
• ಸರಣಿ ಸಂಖ್ಯೆಯ ಮೂಲಕ ಅಂಶವನ್ನು ತೆಗೆದುಹಾಕಿ
• ಆರ್ಡಿನಲ್ ಸಂಖ್ಯೆಯ ಮೂಲಕ ಅಂಶವನ್ನು ಪಡೆಯಿರಿ
• ಡೇಟಾವನ್ನು ವಿಂಗಡಿಸಲಾದ ರೂಪದಲ್ಲಿ ಸಂಗ್ರಹಿಸಲಾಗಿದೆ

ಡೇಟಾವನ್ನು ನಿರಂತರವಾಗಿ ಸೇರಿಸಲಾಗುತ್ತದೆ ಮತ್ತು ತೆಗೆದುಹಾಕಲಾಗುತ್ತದೆ, ರಚನೆಯು ವೇಗದ ಕಾರ್ಯಾಚರಣೆಯ ವೇಗವನ್ನು ಖಚಿತಪಡಿಸಿಕೊಳ್ಳಬೇಕು. ಮೊದಲಿಗೆ ನಾನು ಪ್ರಮಾಣಿತ ಧಾರಕಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಅಂತಹ ವಿಷಯವನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸಲು ಪ್ರಯತ್ನಿಸಿದೆ ಎಸ್‌ಟಿಡಿ. ಈ ಮಾರ್ಗವು ಯಶಸ್ಸಿನ ಕಿರೀಟವನ್ನು ಪಡೆದಿಲ್ಲ ಮತ್ತು ನಾನೇ ಏನನ್ನಾದರೂ ಕಾರ್ಯಗತಗೊಳಿಸಬೇಕು ಎಂಬ ತಿಳುವಳಿಕೆ ಬಂದಿತು. ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ ಅನ್ನು ಬಳಸುವುದು ಮಾತ್ರ ಮನಸ್ಸಿಗೆ ಬಂದಿತು. ಏಕೆಂದರೆ ಇದು ವೇಗದ ಅಳವಡಿಕೆ, ಅಳಿಸುವಿಕೆ ಮತ್ತು ವಿಂಗಡಿಸಲಾದ ರೂಪದಲ್ಲಿ ಡೇಟಾ ಸಂಗ್ರಹಣೆಯ ಅಗತ್ಯವನ್ನು ಪೂರೈಸುತ್ತದೆ. ಮರವು ಬದಲಾದಾಗ ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಹೇಗೆ ಸೂಚ್ಯಂಕ ಮಾಡುವುದು ಮತ್ತು ಸೂಚ್ಯಂಕಗಳನ್ನು ಮರು ಲೆಕ್ಕಾಚಾರ ಮಾಡುವುದು ಹೇಗೆ ಎಂದು ಲೆಕ್ಕಾಚಾರ ಮಾಡುವುದು ಮಾತ್ರ ಉಳಿದಿದೆ.

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