Насколько сбалансированы сбалансированные B-деревья? - PullRequest
Новая
       10

Насколько сбалансированы сбалансированные B-деревья?

2 голосов
/ 17 октября 2010

Скажем, у меня B-дерево с узлами в конфигурации 3-4 (3 элемента и 4 указателя).Предполагая, что я строю свое дерево законно в соответствии с правилами, могу ли я достичь ситуации, когда в слое есть два узла, и у одного узла есть 4 выходных указателя, а у другого только два выходных указателя?

В общем, какие у меня есть гарантии относительно сбалансированности правильно используемого B-Tree

1 Ответ

9 голосов
/ 17 октября 2010

Идея баланса (в общих сбалансированных древовидных структурах данных) заключается в том, что разница в глубинах между любыми двумя поддеревьями равна нулю или единице (в зависимости от дерева). Другими словами, число сравнений, используемых для поиска конечного узла, всегда одинаково.

Так что да, вы можете оказаться в ситуации, которую вы описываете, просто потому, что глубины одинаковы. Количество элементов в каждом узле не имеет значения для баланса (но см. Ниже).

Это совершенно законно, хотя в левом узле больше элементов, чем в правом (нулевые указатели не отображаются): 

                 +---+---+---+
                 | 8 |   |   |
                 +---+---+---+
        ________/    |
       /             |
      |              |
+---+---+---+  +---+---+---+
| 1 | 2 | 3 |  | 9 |   |   |
+---+---+---+  +---+---+---+

Однако очень необычно иметь 3-4 BTree (некоторые на самом деле говорят, что это вовсе не BTree, а какая-то другая структура данных).

С BTrees у вас обычно есть четное количество ключей как максимум в каждом узле (например, дерево 4-5), чтобы разделение и объединение было легче. При использовании дерева 4-5 решение о том, какой ключ повышается при заполнении узла, является простым - оно является средним из пяти. Это не такой четкий вопрос с деревом 3-4, так как он может быть одним из двух (нет определенной середины для четырех элементов).

Это также позволяет вам следовать правилу, согласно которому ваши узлы должны содержать от n до 2n элементов. Кроме того (для «правильных» BTrees) все конечные узлы находятся на одинаковой глубине, а не только друг в друге.

Если вы добавили следующие значения в пустое BTree, вы можете получить описанную вами ситуацию: 

Add           Tree Structure
---          ----------------
 1                  1

 2                 1,2

 5                1,2,5

 6               1,2,5,6

 7                  5
                   / \
                1,2   6,7

 8                  5
                   / \
                1,2   6,7,8

 9                  5
                   / \
                1,2   6,7,8,9
...