ດັດສະນີຕົ້ນໄມ້ຄູ່

ຂ້ອຍພົບບັນຫາປະເພດຕໍ່ໄປນີ້. ມັນເປັນສິ່ງຈໍາເປັນເພື່ອປະຕິບັດກ່ອງເກັບຂໍ້ມູນທີ່ສະຫນອງຫນ້າທີ່ດັ່ງຕໍ່ໄປນີ້:

• ໃສ່ອົງປະກອບໃຫມ່
• ເອົາອົງປະກອບອອກໂດຍເລກລໍາດັບ
• ໄດ້ຮັບອົງປະກອບໂດຍຈໍານວນຄໍາສັ່ງ
• ຂໍ້ມູນຖືກເກັບໄວ້ໃນຮູບແບບຈັດຮຽງ

ຂໍ້ມູນຖືກເພີ່ມແລະເອົາອອກຢ່າງຕໍ່ເນື່ອງ, ໂຄງສ້າງຕ້ອງຮັບປະກັນຄວາມໄວໃນການດໍາເນີນງານໄວ. ທໍາອິດຂ້າພະເຈົ້າພະຍາຍາມປະຕິບັດສິ່ງດັ່ງກ່າວໂດຍໃຊ້ຖັງມາດຕະຖານຈາກ std. ເສັ້ນທາງນີ້ບໍ່ໄດ້ຖືກຄອບຄອງດ້ວຍຄວາມສໍາເລັດແລະຄວາມເຂົ້າໃຈມາວ່າຂ້ອຍຈໍາເປັນຕ້ອງປະຕິບັດບາງສິ່ງບາງຢ່າງດ້ວຍຕົນເອງ. ສິ່ງດຽວທີ່ເຂົ້າມາໃນໃຈແມ່ນການໃຊ້ຕົ້ນໄມ້ຄົ້ນຫາຄູ່. ເນື່ອງຈາກວ່າມັນຕອບສະຫນອງຄວາມຕ້ອງການຂອງການແຊກໄວ, ການລຶບແລະການເກັບຮັກສາຂໍ້ມູນໃນຮູບແບບການຈັດລຽງ. ທັງຫມົດທີ່ຍັງເຫຼືອແມ່ນເພື່ອຄິດວິທີການດັດສະນີອົງປະກອບທັງຫມົດແລະຄິດໄລ່ຕົວຊີ້ວັດຄືນໃຫມ່ເມື່ອຕົ້ນໄມ້ປ່ຽນແປງ.

struct node_s {    
    data_t data;

    uint64_t weight; // вес узла

    node_t *left;
    node_t *right;

    node_t *parent;
};

ບົດຄວາມຈະມີຮູບພາບແລະທິດສະດີຫຼາຍກ່ວາລະຫັດ. ລະຫັດສາມາດເບິ່ງໄດ້ທີ່ລິ້ງຂ້າງລຸ່ມນີ້.

ນ້ໍາຫນັກ

ເພື່ອເຮັດສິ່ງນີ້, ຕົ້ນໄມ້ໄດ້ຮັບການດັດແປງເລັກນ້ອຍ, ຂໍ້ມູນເພີ່ມເຕີມໄດ້ຖືກເພີ່ມກ່ຽວກັບ ນ້ຳໜັກ node. ນ້ໍາຫນັກຂອງຂໍ້ແມ່ນ ຈໍາ​ນວນ​ຂອງ​ລູກ​ຫລານ​ຂອງ​ຂໍ້​ນີ້​ + 1 (ນ້ໍາຫນັກຂອງອົງປະກອບດຽວ).

ຟັງຊັນສໍາລັບການຮັບນ້ໍາຫນັກຂອງຂໍ້:

uint64_t bntree::get_child_weight(node_t *node) {
    if (node) {
        return node->weight;
    }

    return 0;
}

ນ້ ຳ ໜັກ ຂອງແຜ່ນແມ່ນເທົ່າກັບ 0.

ຕໍ່ໄປ, ໃຫ້ເຮົາກ້າວໄປສູ່ການສະແດງພາບຂອງຕົວຢ່າງຂອງຕົ້ນໄມ້ດັ່ງກ່າວ. ດຳ ປຸ່ມ node ຈະຖືກສະແດງເປັນສີ (ຄ່າຈະບໍ່ສະແດງ, ເພາະວ່າມັນບໍ່ຈໍາເປັນ), ສີແດງ - ນ​້​ໍາ​ຫນັກ knot​, ສີຂຽວ - ດັດຊະນີ node.

ເມື່ອຕົ້ນໄມ້ຂອງພວກເຮົາຫວ່າງເປົ່າ, ນ້ໍາຫນັກຂອງມັນແມ່ນ 0. ໃຫ້ເພີ່ມອົງປະກອບຂອງຮາກກັບມັນ:

ນ້ໍາຫນັກຂອງຕົ້ນໄມ້ກາຍເປັນ 1, ນ້ໍາຫນັກຂອງອົງປະກອບຂອງຮາກກາຍເປັນ 1. ນ້ໍາຫນັກຂອງອົງປະກອບຂອງຮາກແມ່ນນ້ໍາຫນັກຂອງຕົ້ນໄມ້.

ໃຫ້ເພີ່ມອົງປະກອບອີກສອງສາມຢ່າງ:

ແຕ່ລະຄັ້ງທີ່ອົງປະກອບໃຫມ່ຖືກເພີ່ມ, ພວກເຮົາລົງໄປຫາຂໍ້ແລະເພີ່ມນ້ໍາຫນັກຂອງແຕ່ລະ node ຜ່ານ. ເມື່ອໂຫນດໃຫມ່ຖືກສ້າງຂື້ນ, ນ້ໍາຫນັກຖືກມອບຫມາຍໃຫ້ມັນ 1. ຖ້າ node ທີ່ມີລະຫັດດັ່ງກ່າວມີຢູ່ແລ້ວ, ພວກເຮົາຈະຂຽນທັບມູນຄ່າແລະກັບຄືນໄປບ່ອນເຖິງຮາກ, ຍົກເລີກການປ່ຽນແປງຂອງນ້ໍາຫນັກຂອງ nodes ທັງຫມົດທີ່ພວກເຮົາໄດ້ຜ່ານ.
ຖ້າ node ຖືກໂຍກຍ້າຍ, ຫຼັງຈາກນັ້ນພວກເຮົາລົງໄປແລະຫຼຸດລົງນ້ໍາຫນັກຂອງ nodes ຜ່ານ.

ດັດນີ

ຕອນນີ້ໃຫ້ພວກເຮົາກ້າວໄປສູ່ວິທີການດັດສະນີ nodes. Nodes ບໍ່ໄດ້ເກັບຮັກສາດັດຊະນີຂອງພວກເຂົາຢ່າງຊັດເຈນ, ມັນຖືກຄິດໄລ່ໂດຍອີງໃສ່ນ້ໍາຫນັກຂອງ nodes. ຖ້າພວກເຂົາເກັບຮັກສາດັດສະນີຂອງພວກເຂົາ, ຫຼັງຈາກນັ້ນມັນຈະຖືກຕ້ອງການ O (n) ເວລາທີ່ຈະປັບປຸງດັດສະນີຂອງທຸກ nodes ຫຼັງຈາກການປ່ຽນແປງແຕ່ລະຕົ້ນໄມ້.
ໃຫ້ກ້າວໄປສູ່ການສະແດງພາບ. ຕົ້ນໄມ້ຂອງພວກເຮົາຫວ່າງເປົ່າ, ໃຫ້ເພີ່ມຂໍ້ທີ 1 ໃສ່ມັນ:

node ທໍາອິດມີດັດຊະນີ 0, ແລະໃນປັດຈຸບັນແມ່ນເປັນໄປໄດ້ 2 ກໍລະນີ. ໃນຄັ້ງທໍາອິດ, ດັດຊະນີຂອງອົງປະກອບຮາກຈະປ່ຽນແປງ, ໃນຄັ້ງທີສອງມັນຈະບໍ່ປ່ຽນແປງ.

ຢູ່ຮາກ, ຕົ້ນໄມ້ຍ່ອຍຊ້າຍມີນໍ້າໜັກ 1.

ກໍລະນີທີສອງ:

ດັດຊະນີຂອງຮາກບໍ່ປ່ຽນແປງເພາະວ່ານ້ໍາຫນັກຂອງຕົ້ນໄມ້ຍ່ອຍຊ້າຍຂອງມັນຍັງຄົງຢູ່ 0.

ດັດຊະນີຂອງ node ຖືກຄິດໄລ່ເປັນນ້ໍາຫນັກຂອງ subtree ຊ້າຍຂອງມັນ + ຕົວເລກທີ່ຜ່ານຈາກພໍ່ແມ່. ຕົວເລກນີ້ແມ່ນຫຍັງ?, ນີ້ແມ່ນຕົວນັບດັດຊະນີ, ໃນເບື້ອງຕົ້ນມັນເທົ່າກັບ 0, ເນື່ອງຈາກວ່າ ຮາກບໍ່ມີພໍ່ແມ່. ຫຼັງຈາກນັ້ນ, ມັນທັງຫມົດແມ່ນຂຶ້ນກັບບ່ອນທີ່ພວກເຮົາລົງໄປຫາເດັກຊ້າຍຫຼືຂວາ. ຖ້າໄປທາງຊ້າຍ, ຫຼັງຈາກນັ້ນບໍ່ມີຫຍັງຖືກເພີ່ມໃສ່ເຄົາເຕີ. ຖ້າພວກເຮົາເພີ່ມດັດຊະນີຂອງໂຫນດປະຈຸບັນໃຫ້ຖືກຕ້ອງ.

ຕົວຢ່າງ, ວິທີການດັດສະນີຂອງອົງປະກອບທີ່ມີລະຫັດ 8 (ລູກທີ່ຖືກຕ້ອງຂອງຮາກ) ຖືກຄິດໄລ່. ນີ້ແມ່ນ "Root Index" + "ນ້ໍາຫນັກຂອງ subtree ຊ້າຍຂອງ node ກັບທີ່ສໍາຄັນ 8" + "1" == 3 + 2 + 1 == 6
ດັດຊະນີຂອງອົງປະກອບທີ່ມີກຸນແຈ 6 ຈະເປັນ "ດັດຊະນີຮາກ" + 1 == 3 + 1 == 4

ດັ່ງນັ້ນ, ມັນໃຊ້ເວລາເພື່ອໃຫ້ໄດ້ຮັບແລະລຶບອົງປະກອບໂດຍດັດສະນີ O (log n), ເນື່ອງຈາກວ່າເພື່ອໃຫ້ໄດ້ອົງປະກອບທີ່ຕ້ອງການພວກເຮົາທໍາອິດຕ້ອງຊອກຫາມັນ (ລົງຈາກຮາກໄປຫາອົງປະກອບນີ້).

ຄວາມເລິກ

ອີງຕາມນ້ໍາຫນັກ, ທ່ານຍັງສາມາດຄິດໄລ່ຄວາມເລິກຂອງຕົ້ນໄມ້. ມີຄວາມຈໍາເປັນສໍາລັບການດຸ່ນດ່ຽງ.
ເພື່ອເຮັດສິ່ງນີ້, ນ້ ຳ ໜັກ ຂອງໂນດປະຈຸບັນຕ້ອງຖືກປັດເປັນຕົວເລກ ທຳ ອິດໄປຫາພະລັງງານຂອງ 2 ເຊິ່ງໃຫຍ່ກວ່າຫຼືເທົ່າກັບນ້ ຳ ໜັກ ທີ່ໃຫ້ແລະເອົາ logarithm ສອງຈາກມັນ. ນີ້ຈະເຮັດໃຫ້ພວກເຮົາມີຄວາມເລິກຂອງຕົ້ນໄມ້, ສົມມຸດວ່າມັນມີຄວາມສົມດູນ. ຕົ້ນໄມ້ມີຄວາມສົມດູນຫຼັງຈາກໃສ່ອົງປະກອບໃຫມ່. ຂ້ອຍຈະບໍ່ໃຫ້ທິດສະດີກ່ຽວກັບວິທີດຸ່ນດ່ຽງຕົ້ນໄມ້. ລະຫັດແຫຼ່ງສະຫນອງຫນ້າທີ່ການດຸ່ນດ່ຽງ.

ລະຫັດສໍາລັບການປ່ຽນນ້ໍາຫນັກໄປສູ່ຄວາມເລິກ.

/*
 * Возвращает первое число в степени 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));
}

ຜົນໄດ້ຮັບ

• ການແຊກຂອງອົງປະກອບໃຫມ່ເກີດຂຶ້ນໃນ O (log n)
• ການລຶບອົງປະກອບໂດຍເລກລໍາດັບເກີດຂຶ້ນໃນ O (log n)
• ການໄດ້ຮັບອົງປະກອບໂດຍເລກລໍາດັບເກີດຂຶ້ນໃນ O (log n)

ຄວາມໄວ O (log n) ພວກເຮົາຈ່າຍຄ່າຄວາມຈິງທີ່ວ່າຂໍ້ມູນທັງຫມົດຖືກເກັບໄວ້ໃນຮູບແບບຈັດຮຽງ.

ຂ້ອຍບໍ່ຮູ້ວ່າໂຄງສ້າງດັ່ງກ່າວອາດຈະເປັນປະໂຫຍດຢູ່ໃສ. ເປັນການປິດສະໜາເພື່ອເຂົ້າໃຈອີກເທື່ອໜຶ່ງວ່າຕົ້ນໄມ້ເຮັດວຽກແນວໃດ. ຂອບໃຈສໍາລັບຄວາມສົນໃຈຂອງທ່ານ.

ເອກະສານ

• ລະຫັດແຫຼ່ງຕົ້ນໄມ້

ໂຄງການປະກອບດ້ວຍຂໍ້ມູນການທົດສອບເພື່ອກວດກາເບິ່ງຄວາມໄວຂອງການດໍາເນີນງານ. ຕົ້ນໄມ້ກໍາລັງຖົມຂຶ້ນ 1000000 ອົງປະກອບ. ແລະມີການລຶບຕາມລໍາດັບ, ການແຊກແລະການດຶງຂໍ້ມູນອົງປະກອບ 1000000 ຄັ້ງດຽວ. ນັ້ນ​ແມ່ນ 3000000 ການດໍາເນີນງານ. ຜົນໄດ້ຮັບໄດ້ຫັນອອກມາຂ້ອນຂ້າງດີ ~ 8 ວິນາທີ.

ແຫຼ່ງຂໍ້ມູນ: www.habr.com