B-copac

În acest tutorial, veți afla ce este un copac B. De asemenea, veți găsi exemple de lucru ale operațiunii de căutare pe un copac B în C, C ++, Java și Python.

Arborele B este un tip special de arbore de căutare auto-echilibrat în care fiecare nod poate conține mai multe chei și poate avea mai mult de doi copii. Este o formă generalizată a arborelui binar de căutare.

Este, de asemenea, cunoscut sub numele de copac echilibrat pe înălțime.

B-copac

De ce arborele B?

Necesitatea arborelui B a apărut odată cu creșterea nevoii de timp mai mic în accesarea mediilor de stocare fizice, precum un hard disk. Dispozitivele de stocare secundare sunt mai lente cu o capacitate mai mare. Era nevoie de astfel de tipuri de structuri de date care să minimizeze accesul la disc.

Alte structuri de date, cum ar fi un copac de căutare binar, un copac avl, un copac roșu-negru, etc pot stoca o singură cheie într-un singur nod. Dacă trebuie să stocați un număr mare de taste, atunci înălțimea acestor copaci devine foarte mare și timpul de acces crește.

Cu toate acestea, arborele B poate stoca multe chei într-un singur nod și poate avea mai multe noduri copil. Aceasta scade înălțimea în mod semnificativ, permițând accesuri mai rapide pe disc.

Proprietățile arborelui B

  1. Pentru fiecare nod x, tastele sunt stocate în ordine crescătoare.
  2. În fiecare nod, există o valoare booleană x.leaf, care este adevărată dacă x este o frunză.
  3. Dacă n este ordinea arborelui, fiecare nod intern poate conține cel mult n - 1 taste împreună cu un indicator către fiecare copil.
  4. Fiecare nod, cu excepția rădăcinii, poate avea cel mult n copii și cel puțin n / 2 copii.
  5. Toate frunzele au aceeași adâncime (adică înălțimea-h a copacului).
  6. Rădăcina are cel puțin 2 copii și conține minimum 1 cheie.
  7. Dacă n ≧ 1, atunci pentru orice B-tree-n cheie de înălțime h și grad minim t ≧ 2, .h ≧ logt (n+1)/2

Operațiuni

In cautarea

Căutarea unui element într-un arbore B este forma generalizată de căutare a unui element într-un arbore de căutare binară. Următorii pași sunt urmați.

  1. Începând de la nodul rădăcină, comparați k cu prima cheie a nodului.
    Dacă k = the first key of the node, returnați nodul și indexul.
  2. Dacă k.leaf = true, returnează NULL (adică nu a fost găsit).
  3. Dacă k < the first key of the root node, căutați copilul stâng al acestei chei recursiv.
  4. Dacă există mai multe taste în nodul curent și k> the first key, comparați k cu următoarea cheie din nod.
    Dacă k < next key, căutați copilul din stânga al acestei taste (adică k se află între prima și a doua tastă).
    Altfel, caută copilul potrivit al cheii.
  5. Repetați pașii de la 1 la 4 până când se atinge frunza.

Exemplu de căutare

  1. Să căutăm cheia k = 17în arborele de mai jos de gradul 3. Arborele B.
  2. k nu se găsește în rădăcină, deci, comparați-l cu cheia rădăcină. k nu se găsește pe nodul rădăcină
  3. De aceea k> 11, mergeți la copilul drept al nodului rădăcină. Mergeți la subarborele din dreapta
  4. Comparați k cu 16. Deoarece k> 16, comparați k cu următoarea tastă 18. Comparați cu tastele de la stânga la dreapta
  5. Deoarece k < 18, k se află între 16 și 18. Căutați în copilul din dreapta de 16 sau copilul din stânga de 18. k se află între 16 și 18
  6. k este găsit. k este găsit

Algoritm pentru căutarea unui element

 BtreeSearch(x, k) i = 1 while i ≦ n(x) and k ≧ keyi(x) // n(x) means number of keys in x node 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)

Pentru a afla mai multe despre diferite operațiuni cu arborele B, vă rugăm să vizitați

  • Inserare pe arborele B.
  • Ștergere pe arborele B.

Exemple Python, Java și C / C ++

Python Java C C ++ 
# Searching a key on a B-tree in Python # Create node 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 # Print the tree def print_tree(self, x, l=0): print("Level ", 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) # Search key def search_key(self, k, x=None): if x is not None: i = 0 while i x.keys(i)(0): i += 1 if i  = 0 and k(0)  = 0 and k(0)  x.keys(i)(0): i += 1 self.insert_non_full(x.child(i), k) # Split 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("Found") else: print("Not found") if __name__ == '__main__': main()   
 // Searching a key on a B-tree in Java public class BTree ( private int T; // Node creation 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; // Search key 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); ) ) // Splitting the node 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 = 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; ) // Inserting a value 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); ) ) // Insert the node final private void insertValue(Node x, int k) ( if (x.leaf) ( int i = 0; for (i = x.n - 1; i>= 0 && k  = 0 && k x.key(i)) ( i++; ) ) insertValue(x.child(i), k); ) ) public void Show() ( Show(root); ) // Display 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)); ) ) ) // Check if present 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("found"); ) else ( System.out.println("not found"); ) ; ) ) 
// Searching a key on a B-tree in C #include #include #define MAX 3 #define MIN 2 struct BTreeNode ( int val(MAX + 1), count; struct BTreeNode *link(MAX + 1); ); struct BTreeNode *root; // Create a node 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; ) // Insert node 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++; ) // Split node 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 val(node->count); (*newNode)->link(0) = node->link(node->count); node->count--; ) // Set the value int setValue(int val, int *pval, struct BTreeNode *node, struct BTreeNode **child) ( int pos; if (!node) ( *pval = val; *child = NULL; return 1; ) if (val val(1)) ( pos = 0; ) else ( for (pos = node->count; (val val(pos) && pos> 1); pos--) ; if (val == node->val(pos)) ( printf("Duplicates are not permitted"); 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; ) // Insert the value void insert(int val) ( int flag, i; struct BTreeNode *child; flag = setValue(val, &i, root, &child); if (flag) root = createNode(i, child); ) // Search node void search(int val, int *pos, struct BTreeNode *myNode) ( if (!myNode) ( return; ) if (val val(1)) ( *pos = 0; ) else ( for (*pos = myNode->count; (val val(*pos) && *pos> 1); (*pos)--) ; if (val == myNode->val(*pos)) ( printf("%d is found", val); return; ) ) search(val, pos, myNode->link(*pos)); return; ) // Traverse then nodes void traversal(struct BTreeNode *myNode) ( int i; if (myNode) ( for (i = 0; i count; i++) ( traversal(myNode->link(i)); printf("%d ", myNode->val(i + 1)); ) traversal(myNode->link(i)); ) ) int main() ( int val, ch; insert(8); insert(9); insert(10); insert(11); insert(15); insert(16); insert(17); insert(18); insert(20); insert(23); traversal(root); printf(""); search(11, &ch, root); )
// Searching a key on a B-tree in 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 traverse(); cout << " " 
 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) 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) 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 keys(j) = y->keys(j + t); if (y->leaf == false) ( for (int j = 0; j 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() ( BTree t(3); t.insert(8); t.insert(9); t.insert(10); t.insert(11); t.insert(15); t.insert(16); t.insert(17); t.insert(18); t.insert(20); t.insert(23); cout << "The B-tree is: "; t.traverse(); int k = 10; (t.search(k) != NULL) ? cout << endl << k << " is found" : cout << endl << k << " is not Found"; k = 2; (t.search(k) != NULL) ? cout << endl << k << " is found" : cout << endl << k << " is not Found"; )

Căutarea complexității pe arborele B.

Cel mai prost caz Complexitatea timpului: Θ(log n)

Complexitate medie a cazului: Θ(log n)

Cel mai bun caz Complexitatea timpului: Θ(log n)

Cazul mediu Complexitatea spațiului: Θ(n)

Cel mai prost caz Complexitatea spațiului: Θ(n)

Aplicații B Tree

  • baze de date și sisteme de fișiere
  • pentru a stoca blocuri de date (medii de stocare secundare)
  • indexare pe mai multe niveluri

Articole interesante...