Главная » Деревья

Сбалансированное дерево b tree

Содержание
  1. B-дерево
  2. Зачем нужно
  3. Свойства
  4. Операции с B-деревом
  5. Поиск элемента
  6. Алгоритм:
  7. Реализация на языках программирования
  8. Python
  9. Java
  10. C
  11. C++
  12. Где используется

B-дерево

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

Зачем нужно

Вторичные запоминающие устройства (жесткие диски, SSD) медленно работают с большим объемом данных. Людям захотелось сократить время доступа к физическим носителям информации, поэтому возникла потребность в таких структурах данных, которые способны это сделать.

Двоичное дерево поиска, АВЛ-дерево, красно-черное дерево и т. д. могут хранить только один ключ в одном узле. Если нужно хранить больше, высота деревьев резко начинает расти, из-за этого время доступа сильно увеличивается.

С B-деревом все не так. Оно позволяет хранить много ключей в одном узле и при этом может ссылаться на несколько дочерних узлов. Это значительно уменьшает высоту дерева и, соответственно, обеспечивает более быстрый доступ к диску.

Свойства

  1. Ключи в каждом узле x упорядочены по неубыванию.
  2. В каждом узле есть логическое значение x.leaf . Оно истинно, если x — лист.
  3. Каждый узел, кроме корня, содержит не менее t-1 ключей, а каждый внутренний узел имеет как минимум t дочерних узлов, где t — минимальная степень B-дерева.
  4. Все листья находятся на одном уровне, т. е. обладают одинаковой глубиной, равной высоте дерева.
  5. Корень имеет не менее 2 дочерних элементов и содержит не менее 1 ключа.

Операции с B-деревом

Поиск элемента

Средняя временная сложность: Θ(log n)
Худшая временная сложность: Θ(log n)

Поиск ключа в B-дереве работает так же, как и в двоичном дереве поиска.

  1. Сравниваем k с первым ключом узла, начиная с корня. Если k = первый ключ узла , возвращаем узел и индекс.
  2. Если k.leaf = true , возвращаем NULL . Элемент не найден.
  3. Если k < первый ключ корня , рекурсивно ищем левый дочерний элемент этого ключа.
  4. Если в текущем узле более одного ключа и k > первый ключ , сравниваем k со следующим ключом в узле.
    Если k < следующий ключ , ищем левый дочерний элемент этого ключа (k находится между первым и вторым ключами).
    Иначе иначе ищем правый дочерний элемент ключа.
  5. Повторяем шаги с 1 по 4, пока не дойдем до листа.

Алгоритм:

BtreeSearch(x, k) 
i = 1 
while i ≤ n[x] and k ≥ keyi[x] // n[x] — количество ключей в узле x 
do i = i + 1
if i n[x] and k = keyi[x] 
then return (x, i)
if leaf [x] 
then return NIL
else 
return BtreeSearch(ci[x], k)
Применим на примере

• Хотим найти ключ k = 17 в этом дереве.

• k нет в корне → сравниваем k с ключом корня.

• k > 11 → идем через правого «ребенка».

• Сравниваем k с первым ключом узла: k > 16 → сравниваем k со вторым ключом узла.

Читайте также:  Дорога среди деревьев вднх

• k > 18 → k лежит между 16 и 18. Ищем либо в правом «ребенке» 16, либо в левом «ребенке» 18.

Реализация на языках программирования

Python

# Поиска ключа в B-дереве на Python # Создаем узел class BTreeNode: def __init__(self, leaf=False): self.leaf = leaf self.keys = [] self.child = [] class BTree: def __init__(self, t): self.root = BTreeNode(True) self.t = t # Выводим дерево на экран def print_tree(self, x, l=0): print("Уровень", l, " ", len(x.keys), end=":") for i in x.keys: print(i, end=" ") print() l += 1 if len(x.child) > 0: for i in x.child: self.print_tree(i, l) # Поиск ключа def search_key(self, k, x=None): if x is not None: i = 0 while i < len(x.keys) and k >x.keys[i][0]: i += 1 if i < len(x.keys) and k == x.keys[i][0]: return (x, i) elif x.leaf: return None else: return self.search_key(k, x.child[i]) else: return self.search_key(k, self.root) # Вставка ключа def insert_key(self, k): root = self.root if len(root.keys) == (2 * self.t) - 1: temp = BTreeNode() self.root = temp temp.child.insert_key(0, root) self.split(temp, 0) self.insert_non_full(temp, k) else: self.insert_non_full(root, k) # Вставка ключа k в узел x, который должен быть # незаполненным при вызове def insert_non_full(self, x, k): i = len(x.keys) - 1 if x.leaf: x.keys.append((None, None)) while i >= 0 and k[0] < x.keys[i][0]: x.keys[i + 1] = x.keys[i] i -= 1 x.keys[i + 1] = k else: while i >= 0 and k[0] < x.keys[i][0]: i -= 1 i += 1 if len(x.child[i].keys) == (2 * self.t) - 1: self.split(x, i) if k[0] >x.keys[i][0]: i += 1 self.insert_non_full(x.child[i], k) # Разбиение узла def split(self, x, i): t = self.t y = x.child[i] z = BTreeNode(y.leaf) x.child.insert_key(i + 1, z) x.keys.insert_key(i, y.keys[t - 1]) z.keys = y.keys[t: (2 * t) - 1] y.keys = y.keys[0: t - 1] if not y.leaf: z.child = y.child[t: 2 * t] y.child = y.child[0: t - 1] def main(): B = BTree(3) for i in range(10): B.insert_key((i, 2 * i)) B.print_tree(B.root) if B.search_key(8) is not None: print("\nНайдено") else: print("\nНе найдено") if __name__ == '__main__': main()

Java

/ Поиск ключа в B-дереве на Java public class BTree < private int T; // Создаем узел public class Node < int n; int key[] = new int[2 * T - 1]; Node child[] = new Node[2 * T]; boolean leaf = true; public int Find(int k) < for (int i = 0; i < this.n; i++) < if (this.key[i] == k) < return i; >> return -1; >; > public BTree(int t) < T = t; root = new Node(); root.n = 0; root.leaf = true; >private Node root; // Поиск ключа private Node Search(Node x, int key) < int i = 0; if (x == null) return x; for (i = 0; i < x.n; i++) < if (key < x.key[i]) < break; >if (key == x.key[i]) < return x; >> if (x.leaf) < return null; >else < return Search(x.child[i], key); >> // Разбиение узла private void Split(Node x, int pos, Node y) < Node z = new Node(); z.leaf = y.leaf; z.n = T - 1; for (int j = 0; j < T - 1; j++) < z.key[j] = y.key[j + T]; >if (!y.leaf) < for (int j = 0; j < T; j++) < z.child[j] = y.child[j + T]; >> y.n = T - 1; for (int j = x.n; j >= pos + 1; j--) < x.child[j + 1] = x.child[j]; >x.child[pos + 1] = z; for (int j = x.n - 1; j >= pos; j--) < x.key[j + 1] = x.key[j]; >x.key[pos] = y.key[T - 1]; x.n = x.n + 1; > // Вставка значения public void Insert(final int key) < Node r = root; if (r.n == 2 * T - 1) < Node s = new Node(); root = s; s.leaf = false; s.n = 0; s.child[0] = r; Split(s, 0, r); insertValue(s, key); >else < insertValue(r, key); >> // Вставка узла final private void insertValue(Node x, int k) < if (x.leaf) < int i = 0; for (i = x.n - 1; i >= 0 && k < x.key[i]; i--) < x.key[i + 1] = x.key[i]; >x.key[i + 1] = k; x.n = x.n + 1; > else < int i = 0; for (i = x.n - 1; i >= 0 && k < x.key[i]; i--) < >; i++; Node tmp = x.child[i]; if (tmp.n == 2 * T - 1) < Split(x, i, tmp); if (k >x.key[i]) < i++; >> insertValue(x.child[i], k); > > public void Show() < Show(root); >// Вывод на экран private void Show(Node x) < assert (x == null); for (int i = 0; i < x.n; i++) < System.out.print(x.key[i] + " "); >if (!x.leaf) < for (int i = 0; i < x.n + 1; i++) < Show(x.child[i]); >> > // Проверка, содержится ли ключ public boolean Contain(int k) < if (this.Search(root, k) != null) < return true; >else < return false; >> public static void main(String[] args) < BTree b = new BTree(3); b.Insert(8); b.Insert(9); b.Insert(10); b.Insert(11); b.Insert(15); b.Insert(20); b.Insert(17); b.Show(); if (b.Contain(12)) < System.out.println("\nнайдено"); >else < System.out.println("\nне найдено"); >; > >

C

// Поиск ключа в B-дереве на C #include #include # MAX 3 # MIN 2 struct BTreeNode < int val[MAX + 1], count; struct BTreeNode *link[MAX + 1]; >; struct BTreeNode *root; // Создаем узел struct BTreeNode *createNode(int val, struct BTreeNode *child) < struct BTreeNode *newNode; newNode = (struct BTreeNode *)malloc(sizeof(struct BTreeNode)); newNode->val[1] = val; newNode->count = 1; newNode->link[0] = root; newNode->link[1] = child; return newNode; > // Вставка узла void insertNode(int val, int pos, struct BTreeNode *node, struct BTreeNode *child) < int j = node->count; while (j > pos) < node->val[j + 1] = node->val[j]; node->link[j + 1] = node->link[j]; j--; > node->val[j + 1] = val; node->link[j + 1] = child; node->count++; > // Разбиение узла void splitNode(int val, int *pval, int pos, struct BTreeNode *node, struct BTreeNode *child, struct BTreeNode **newNode) < int median, j; if (pos >MIN) median = MIN + 1; else median = MIN; *newNode = (struct BTreeNode *)malloc(sizeof(struct BTreeNode)); j = median + 1; while (j val[j - median] = node->val[j]; (*newNode)->link[j - median] = node->link[j]; j++; > node->count = median; (*newNode)->count = MAX - median; if (pos else < insertNode(val, pos - median, *newNode, child); >*pval = node->val[node->count]; (*newNode)->link[0] = node->link[node->count]; node->count--; > // Устанавливаем значение int setValue(int val, int *pval, struct BTreeNode *node, struct BTreeNode **child) < int pos; if (!node) < *pval = val; *child = NULL; return 1; >if (val < node->val[1]) < pos = 0; >else < for (pos = node->count; (val < node->val[pos] && pos > 1); pos--) ; if (val == node->val[pos]) < printf("Повторения недопустимы\n"); return 0; >> if (setValue(val, pval, node->link[pos], child)) < if (node->count < MAX) < insertNode(*pval, pos, node, *child); >else < splitNode(*pval, pval, pos, node, *child, child); return 1; >> return 0; > // Вставка значения void insert(int val) < int flag, i; struct BTreeNode *child; flag = setValue(val, &i, root, &child); if (flag) root = createNode(i, child); >// Поиск узла void search(int val, int *pos, struct BTreeNode *myNode) < if (!myNode) < return; >if (val < myNode->val[1]) < *pos = 0; >else < for (*pos = myNode->count; (val < myNode->val[*pos] && *pos > 1); (*pos)--) ; if (val == myNode->val[*pos]) < printf("%d is found", val); return; >> search(val, pos, myNode->link[*pos]); return; > // Обход узлов void traversal(struct BTreeNode *myNode) < int i; if (myNode) < for (i = 0; i < myNode->count; i++) < traversal(myNode->link[i]); printf("%d ", myNode->val[i + 1]); > traversal(myNode->link[i]); > > int main()

C++

// Поиск ключа в B-дереве на C++ #include using namespace std; class TreeNode < int *keys; int t; TreeNode **C; int n; bool leaf; public: TreeNode(int temp, bool bool_leaf); void insertNonFull(int k); void splitChild(int i, TreeNode *y); void traverse(); TreeNode *search(int k); friend class BTree; >; class BTree < TreeNode *root; int t; public: BTree(int temp) < root = NULL; t = temp; >void traverse() < if (root != NULL) root->traverse(); > TreeNode *search(int k) < return (root == NULL) ? NULL : root->search(k); > void insert(int k); >; TreeNode::TreeNode(int t1, bool leaf1) < t = t1; leaf = leaf1; keys = new int[2 * t - 1]; C = new TreeNode *[2 * t]; n = 0; >void TreeNode::traverse() < int i; for (i = 0; i < n; i++) < if (leaf == false) C[i]->traverse(); cout if (leaf == false) C[i]->traverse(); > TreeNode *TreeNode::search(int k) < int i = 0; while (i < n && k >keys[i]) i++; if (keys[i] == k) return this; if (leaf == true) return NULL; return C[i]->search(k); > void BTree::insert(int k) < if (root == NULL) < root = new TreeNode(t, true); root->keys[0] = k; root->n = 1; > else < if (root->n == 2 * t - 1) < TreeNode *s = new TreeNode(t, false); s->C[0] = root; s->splitChild(0, root); int i = 0; if (s->keys[0] < k) i++; s->C[i]->insertNonFull(k); root = s; > else root->insertNonFull(k); > > void TreeNode::insertNonFull(int k) < int i = n - 1; if (leaf == true) < while (i >= 0 && keys[i] > k) < keys[i + 1] = keys[i]; i--; >keys[i + 1] = k; n = n + 1; > else < while (i >= 0 && keys[i] > k) i--; if (C[i + 1]->n == 2 * t - 1) < splitChild(i + 1, C[i + 1]); if (keys[i + 1] < k) i++; >C[i + 1]->insertNonFull(k); > > void TreeNode::splitChild(int i, TreeNode *y) < TreeNode *z = new TreeNode(y->t, y->leaf); z->n = t - 1; for (int j = 0; j < t - 1; j++) z->keys[j] = y->keys[j + t]; if (y->leaf == false) < for (int j = 0; j < t; j++) z->C[j] = y->C[j + t]; > y->n = t - 1; for (int j = n; j >= i + 1; j--) C[j + 1] = C[j]; C[i + 1] = z; for (int j = n - 1; j >= i; j--) keys[j + 1] = keys[j]; keys[i] = y->keys[t - 1]; n = n + 1; > int main()

Где используется

  • В базах данных и файловых системах.
  • Для хранения блоков данных (вторичные носители).
  • Для многоуровневой индексации.
Читайте также:  Где растет дерево кассия

Источник

Оцените статью
© 2024 Деревья и растения