主持人 > 博客 > 管理 > 索引二元樹

索引二元樹

索引二元樹

我遇到了以下類型的問題。 有必要實作一個提供以下功能的資料儲存容器：

  • 插入新元素
  • 依序號刪除元素
  • 按序號取得元素
  • 資料以排序形式存儲

資料不斷地被添加和刪除，結構必須確保快速的運算速度。 起初我嘗試使用標準容器來實現這樣的事情 STD。 這條道路並沒有成功，我意識到我需要自己實現一些東西。 唯一想到的是使用二元搜尋樹。 因為它滿足了資料以排序形式快速插入、刪除和儲存的要求。 剩下的就是弄清楚如何對所有元素建立索引並在樹發生變化時重新計算索引。

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，現在有兩種情況是可能的。 在第一個中，根元素的索引將改變，在第二個中它不會改變。

索引二元樹

在根處，左子樹的權重為 1。

第二種情況：

索引二元樹

根的索引沒有改變，因為它的左子樹的權重仍然是0。

節點的索引計算為其左子樹的權重+從父節點傳遞的數字。 這個數字是多少？，這是索引計數器，最初它等於 0， 因為根沒有父級。 然後這一切都取決於我們到哪裡去尋找左邊的孩子或右邊的孩子。 如果在左側，則不會將任何內容新增至計數器。 如果我們將目前節點的索引新增到右側節點。

索引二元樹

例如，如何計算鍵為 8（根的右子元素）的元素的索引。 這是「根索引」+「鍵為8的節點的左子樹的權重」+「1」== 3 + 2 + 1 == 6
鍵為 6 的元素的索引將為「Root Index」+ 1 == 3 + 1 == 4

因此，透過索引來取得和刪除元素需要時間 O（log 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（log n）
  • 依序號刪除元素發生在 O（log n）
  • 透過序號取得元素發生在 O（log n）

速度 O（log n） 我們為所有資料都以排序形式儲存這一事實付出了代價。

我不知道這樣的結構有什麼用處。 只是一個再次了解樹木如何運作的謎題。 感謝您的關注。

引用

此項目包含用於檢查運行速度的測試資料。 樹已經填滿了 1000000 元素。 並且有順序刪除、插入和檢索元素 1000000 一次。 那是 3000000 營運. 結果結果相當不錯~8秒。

來源： www.habr.com

添加評論