인덱스 이진 트리

다음과 같은 유형의 문제를 발견했습니다. 다음 기능을 제공하는 데이터 스토리지 컨테이너를 구현해야 합니다.

• 새 요소 삽입
• 일련번호로 요소 제거
• 서수로 요소 가져오기
• 데이터는 정렬된 형식으로 저장됩니다.

데이터는 지속적으로 추가되고 제거되므로 빠른 작업 속도를 보장하는 구조가 필요합니다. 처음에는 표준 컨테이너를 사용하여 그런 것을 구현하려고했습니다. 표준. 이 길은 성공으로 이어지지 않았고 스스로 무언가를 구현해야한다는 것을 이해하게되었습니다. 마음에 떠오른 유일한 것은 이진 검색 트리를 사용하는 것이었습니다. 데이터를 정렬된 형식으로 빠르게 삽입, 삭제 및 저장해야 하는 요구 사항을 충족하기 때문입니다. 남은 것은 모든 요소를 ​​인덱싱하는 방법을 파악하고 트리가 변경될 때 인덱스를 다시 계산하는 것입니다.

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