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

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

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

1 2
b-tree

1 ответ:

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

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

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

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

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

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

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

Если вы добавили следующие значения в пустое 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
9