๋ค์๊ณผ ๊ฐ์ ์ ํ์ ๋ฌธ์ ๋ฅผ ๋ฐ๊ฒฌํ์ต๋๋ค. ๋ค์ ๊ธฐ๋ฅ์ ์ ๊ณตํ๋ ๋ฐ์ดํฐ ์คํ ๋ฆฌ์ง ์ปจํ ์ด๋๋ฅผ ๊ตฌํํด์ผ ํฉ๋๋ค.
- ์ ์์ ์ฝ์
- ์ผ๋ จ๋ฒํธ๋ก ์์ ์ ๊ฑฐ
- ์์๋ก ์์ ๊ฐ์ ธ์ค๊ธฐ
- ๋ฐ์ดํฐ๋ ์ ๋ ฌ๋ ํ์์ผ๋ก ์ ์ฅ๋ฉ๋๋ค.
๋ฐ์ดํฐ๋ ์ง์์ ์ผ๋ก ์ถ๊ฐ๋๊ณ ์ ๊ฑฐ๋๋ฏ๋ก ๋น ๋ฅธ ์์ ์๋๋ฅผ ๋ณด์ฅํ๋ ๊ตฌ์กฐ๊ฐ ํ์ํฉ๋๋ค. ์ฒ์์๋ ํ์ค ์ปจํ ์ด๋๋ฅผ ์ฌ์ฉํ์ฌ ๊ทธ๋ฐ ๊ฒ์ ๊ตฌํํ๋ ค๊ณ ํ์ต๋๋ค. ํ์ค. ์ด ๊ธธ์ ์ฑ๊ณต์ผ๋ก ์ด์ด์ง์ง ์์๊ณ ์ค์ค๋ก ๋ฌด์ธ๊ฐ๋ฅผ ๊ตฌํํด์ผํ๋ค๋ ๊ฒ์ ์ดํดํ๊ฒ๋์์ต๋๋ค. ๋ง์์ ๋ ์ค๋ฅธ ์ ์ผํ ๊ฒ์ ์ด์ง ๊ฒ์ ํธ๋ฆฌ๋ฅผ ์ฌ์ฉํ๋ ๊ฒ์ด์์ต๋๋ค. ๋ฐ์ดํฐ๋ฅผ ์ ๋ ฌ๋ ํ์์ผ๋ก ๋น ๋ฅด๊ฒ ์ฝ์ , ์ญ์ ๋ฐ ์ ์ฅํด์ผ ํ๋ ์๊ตฌ ์ฌํญ์ ์ถฉ์กฑํ๊ธฐ ๋๋ฌธ์ ๋๋ค. ๋จ์ ๊ฒ์ ๋ชจ๋ ์์๋ฅผ โโ์ธ๋ฑ์ฑํ๋ ๋ฐฉ๋ฒ์ ํ์ ํ๊ณ ํธ๋ฆฌ๊ฐ ๋ณ๊ฒฝ๋ ๋ ์ธ๋ฑ์ค๋ฅผ ๋ค์ ๊ณ์ฐํ๋ ๊ฒ์ ๋๋ค.
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. ๊ทธ๋ฌํ ํค๋ฅผ ๊ฐ์ง ๋
ธ๋๊ฐ ์ด๋ฏธ ์กด์ฌํ๋ ๊ฒฝ์ฐ ๊ฐ์ ๋ฎ์ด์ฐ๊ณ ๋ฃจํธ๋ก ๋์๊ฐ์ ํต๊ณผํ ๋ชจ๋ ๋
ธ๋์ ๊ฐ์ค์น ๋ณ๊ฒฝ์ ์ทจ์ํฉ๋๋ค.
๋
ธ๋๊ฐ ์ ๊ฑฐ๋๋ ๊ฒฝ์ฐ ์๋๋ก ๋ด๋ ค๊ฐ ์ ๋ฌ๋ ๋
ธ๋์ ๊ฐ์ค์น๋ฅผ ์ค์
๋๋ค.
์ง์
์ด์ ๋
ธ๋๋ฅผ ์ธ๋ฑ์ฑํ๋ ๋ฐฉ๋ฒ์ ์ดํด๋ณด๊ฒ ์ต๋๋ค. ๋
ธ๋๋ ์ธ๋ฑ์ค๋ฅผ ๋ช
์์ ์ผ๋ก ์ ์ฅํ์ง ์์ผ๋ฉฐ ๋
ธ๋์ ๊ฐ์ค์น๋ฅผ ๊ธฐ๋ฐ์ผ๋ก ๊ณ์ฐ๋ฉ๋๋ค. ์์ธ์ ์ ์ฅํ ๊ฒฝ์ฐ์๋ ๋ค์์ด ํ์ํฉ๋๋ค. O (N) ํธ๋ฆฌ์ ๊ฐ ๋ณ๊ฒฝ ํ ๋ชจ๋ ๋
ธ๋์ ์ธ๋ฑ์ค๋ฅผ ์
๋ฐ์ดํธํ๋ ๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ์
๋๋ค.
์๊ฐ์ ํํ์ผ๋ก ๋์ด ๊ฐ์๋ค. ์ฐ๋ฆฌ์ ํธ๋ฆฌ๋ ๋น์ด ์์ต๋๋ค. ์ฌ๊ธฐ์ ์ฒซ ๋ฒ์งธ ๋
ธ๋๋ฅผ ์ถ๊ฐํด ๋ณด๊ฒ ์ต๋๋ค.
์ฒซ ๋ฒ์งธ ๋ ธ๋์๋ ์ธ๋ฑ์ค๊ฐ ์์ต๋๋ค. 0, ์ด์ 2๊ฐ์ง ๊ฒฝ์ฐ๊ฐ ๊ฐ๋ฅํฉ๋๋ค. ์ฒซ ๋ฒ์งธ์์๋ ๋ฃจํธ ์์์ ์ธ๋ฑ์ค๊ฐ ๋ณ๊ฒฝ๋๊ณ ๋ ๋ฒ์งธ์์๋ ๋ณ๊ฒฝ๋์ง ์์ต๋๋ค.
๋ฃจํธ์์ ์ผ์ชฝ ํ์ ํธ๋ฆฌ์ ๊ฐ์ค์น๋ 1์ ๋๋ค.
๋ ๋ฒ์งธ ๊ฒฝ์ฐ:
์ผ์ชฝ ํ์ ํธ๋ฆฌ์ ๊ฐ์ค์น๊ฐ 0์ผ๋ก ์ ์ง๋์๊ธฐ ๋๋ฌธ์ ๋ฃจํธ์ ์ธ๋ฑ์ค๋ ๋ณ๊ฒฝ๋์ง ์์์ต๋๋ค.
๋ ธ๋์ ์ธ๋ฑ์ค๋ ์ผ์ชฝ ํ์ ํธ๋ฆฌ์ ๊ฐ์ค์น + ์์ ๋ ธ๋์์ ์ ๋ฌ๋ ์ซ์๋ก ๊ณ์ฐ๋ฉ๋๋ค. ์ด ์ซ์๋ ๋ฌด์์ ๋๊น? ์ด๊ฒ์ ์ธ๋ฑ์ค ์นด์ดํฐ์ ๋๋ค. ์ฒ์์๋ ๋ค์๊ณผ ๊ฐ์ต๋๋ค. 0, ์๋ํ๋ฉด ๋ฃจํธ์๋ ๋ถ๋ชจ๊ฐ ์์ต๋๋ค. ๊ทธ๋ฌ๋ฉด ๋ชจ๋ ๊ฒ์ ์ฐ๋ฆฌ๊ฐ ์ผ์ชฝ ์์ ๋๋ ์ค๋ฅธ์ชฝ ์์์ผ๋ก ์ด๋๋ก ๋ด๋ ค๊ฐ๋์ง์ ๋ฐ๋ผ ๋ฌ๋ผ์ง๋๋ค. ์ผ์ชฝ์ด๋ฉด ์นด์ดํฐ์ ์๋ฌด๊ฒ๋ ์ถ๊ฐ๋์ง ์์ต๋๋ค. ํ์ฌ ๋ ธ๋์ ์ธ๋ฑ์ค๋ฅผ ์ค๋ฅธ์ชฝ ๋ ธ๋์ ์ถ๊ฐํ๋ฉด.
์๋ฅผ ๋ค์ด ํค๊ฐ 8์ธ ์์(๋ฃจํธ์ ์ค๋ฅธ์ชฝ ์์)์ ์ธ๋ฑ์ค๊ฐ ๊ณ์ฐ๋๋ ๋ฐฉ๋ฒ์
๋๋ค. ์ด๊ฒ์ "๋ฃจํธ ์ธ๋ฑ์ค" + "ํค 8์ ๊ฐ๋ ๋
ธ๋์ ์ผ์ชฝ ํ์ ํธ๋ฆฌ์ ๊ฐ์ค์น" + "1" == 3 + 2 + 1 ==์
๋๋ค. 6
ํค๊ฐ 6์ธ ์์์ ์ธ๋ฑ์ค๋ "๋ฃจํธ ์ธ๋ฑ์ค" + 1 == 3 + 1 ==์
๋๋ค. 4
๋ฐ๋ผ์ ์ธ๋ฑ์ค๋ณ๋ก ์์๋ฅผ ๊ฐ์ ธ์ค๊ณ ์ญ์ ํ๋ ๋ฐ ์๊ฐ์ด ๊ฑธ๋ฆฝ๋๋ค. O (๋ก๊ทธ 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));
}
๊ฒฐ๊ณผ
- ์ ์์ ์ฝ์ ์ด ๋ฐ์ํฉ๋๋ค. O (๋ก๊ทธ n)
- ์ผ๋ จ ๋ฒํธ๋ก ์์๋ฅผ ์ญ์ ํ๋ ๊ฒฝ์ฐ O (๋ก๊ทธ n)
- ์ผ๋ จ ๋ฒํธ๋ก ์์๋ฅผ ์ป๋ ๊ฒ์ ๋ค์์์ ๋ฐ์ํฉ๋๋ค. O (๋ก๊ทธ n)
์๋ O (๋ก๊ทธ n) ์ฐ๋ฆฌ๋ ๋ชจ๋ ๋ฐ์ดํฐ๊ฐ ์ ๋ ฌ๋ ํ์์ผ๋ก ์ ์ฅ๋๋ค๋ ์ฌ์ค์ ๋ํ ๋น์ฉ์ ์ง๋ถํฉ๋๋ค.
๊ทธ๋ฌํ ๊ตฌ์กฐ๊ฐ ์ด๋์ ์ ์ฉํ ์ง ๋ชจ๋ฅด๊ฒ ์ต๋๋ค. ๋๋ฌด๊ฐ ์ด๋ป๊ฒ ์๋ํ๋์ง ๋ค์ ํ๋ฒ ์ดํดํ๊ธฐ ์ํ ํผ์ฆ์ ๋๋ค. ๊ด์ฌ์ ๊ฐ์ ธ์ฃผ์ ์ ๊ฐ์ฌํฉ๋๋ค.
์ฐธ์กฐ
ํ๋ก์ ํธ์๋ ์๋ ์๋๋ฅผ ํ์ธํ๊ธฐ ์ํ ํ ์คํธ ๋ฐ์ดํฐ๊ฐ ํฌํจ๋์ด ์์ต๋๋ค. ๋๋ฌด๊ฐ ์ฑ์์ง๊ณ ์์ด์ 1000000 ๊ฐ์. ๊ทธ๋ฆฌ๊ณ ์์์ ์์ฐจ์ ์ธ ์ญ์ , ์ฝ์ , ๊ฒ์์ด ์์ต๋๋ค. 1000000 ํ ๋ฒ. ๊ทธ๊ฑด 3000000 ์ด์. ๊ฒฐ๊ณผ๋ ๊ฝค ์ข์ ๊ฒ์ผ๋ก ๋ํ๋ฌ์ต๋๋ค ~ 8 ์ด.
์ถ์ฒ : habr.com