ืืื ืืขืงืืืขื ืึทืจืืืขืจ ืื ืคืืืืขื ืืข ืืืคึผ ืคืื ืคึผืจืึธืืืขื. ืขืก ืืื ื ืืืืืง ืฆื ืื ืกืืจืืืขื ื ืึท ืืึทืื ืกืืึธืจืืืืฉ ืงืึทื ืืืื ืขืจ ืืืึธืก ืืื ืื ืคืืืืขื ืืข ืคืึทื ืืงืฉืึทื ืึทืืืื:
- ืึทืจืืึทื ืืืืื ื ืืึท ืขืืขืืขื ื
- ืึทืจืึธืคึผื ืขืืขื ืขืืขืืขื ื ืืืจื ืกืืจืืึทื ื ืืืขืจ
- ืืึทืงืืืขื ืขืืขืืขื ื ืืืจื ืึธืจืืึทื ืึทื ื ืืืขืจ
- ืืึทืืข ืืื ืกืืึธืจื ืืื ืกืึธืจืืืจื ืคืึธืจืขื
ืืึทืื ืืขื ืขื ืงืขืกืืืืขืจ ืืืกืืฃ ืืื ืึทืืืขืงืืขื ืืืขื, ืื ืกืืจืืงืืืจ ืืืื ืขื ืฉืืจ ืฉื ืขื ืึธืคึผืขืจืึทืฆืืข ืืืืงืืึทื. ืืื ืขืจืฉืืขืจ ืืื ืืขืคืจืืืื ืฆื ืื ืกืืจืืืขื ื ืึทืืึท ืึท ืืึทื ื ืืฆื ื ืึธืจืืึทื ืงืึทื ืืืื ืขืจื ืคืื ืกืื. ืืขืจ ืืืขื ืืื ื ืืฉื ืืขืงืจืืื ื ืืขืืืืจื ืืื ืืขืจืคืืื ืืื ืขืก ืืื ืืขืงืืืขื ืื ืคืืจืฉืืื ื ืื ืืื ืืืจืฃ ืืืืื ืก ืขืคืขืก ืืืื ืคืืจื. ืืขืจ ืืืืื ืืึทื ืืืึธืก ืืื ืืขืงืืืขื ืฆื ืืืื ืื ื ืืื ืฆื ื ืืฆื ืึท ืืืื ืขืจื ืืืื ืืืื. ืืืืึทื ืขืก ืืืฅ ืื ืคืึธืืขืจืื ื ืคืื ืฉื ืขื ืื ืกืขืจืฉืึทื, ืืืืืฉืึทื ืืื ืกืืึธืจืืืืฉ ืคืื ืืึทืื ืืื ืืืืกืืขืฉืืขืื ืคืึธืจืขื. ืึทืืข ืืืึธืก ืืืืืื ืืื ืฆื ืจืขืืขื ืขื ืืืืก ืืื ืฆื ืืื ืืขืงืก ืึทืืข ืื ืขืืขืืขื ืื ืืื ืจืขืงืึทืืงืืืืจื ืื ืื ืืืกืขืก ืืืขื ืืขืจ ืืืื ืขื ืืขืจืื ืืขื.
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), ืืืืึทื ืืื ืกืืจ ืฆื ืืึทืงืืืขื ืื ืืขืืขืื ืขืืขืืขื ื ืืืจ ืืืื ืขืจืฉืืขืจ ืืขืคึฟืื ืขื ืขืก (ืืืื ืึทืจืึธืคึผ ืคืื ืื ืืืึธืจืฆื ืฆื ืืขื ืขืืขืืขื ื).
Depth
ืืึทืืืจื ืืืืฃ ืื ืืืึธื, ืืืจ ืงืขื ืขื ืืืื ืจืขืืขื ืขื ืื ืืืคืงืืึทื ืคืื ืืขื ืืืื. ื ืืืืืง ืคึฟืึทืจ ืืึทืืึทื ืกืื ื.
ืฆื ืืึธื ืืึธืก, ืื ืืืึธื ืคืื ืื ืงืจืึทื ื ื ืึธืืข ืืืื ืืืื ืจืึทืื ืืื ืฆื ืืขืจ ืขืจืฉืืขืจ ื ืืืขืจ ืฆื ืื ืืึทืื ืคืื 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