B-puu

Selles õpetuses saate teada, mis on B-puu. Lisaks leiate toimivaid näiteid otsinguoperatsioonidest B-puus C, C ++, Java ja Python.

B-puu on spetsiaalne isetasakaalustuva otsingupuu tüüp, milles iga sõlm võib sisaldada rohkem kui ühte võtit ja võib olla rohkem kui kaks last. See on kahendotsingu puu üldistatud vorm.

Tuntud on ka kui kõrguselt tasakaalustatud m-tee puu.

B-puu

Miks just B-puu?

Vajadus B-puu järele tekkis seoses vajadusega vähem aega füüsilisele andmekandjale nagu kõvakettale juurde pääseda. Sekundaarsed mäluseadmed on suurema mahutavusega aeglasemad. Oli vaja sellist tüüpi andmestruktuure, mis minimeerivad kettale juurdepääsu.

Muud andmestruktuurid, nagu kahendotsingupuu, AVL-puu, punamust puu jne, saavad ühte sõlme salvestada ainult ühe võtme. Kui peate salvestama palju võtmeid, siis selliste puude kõrgus muutub väga suureks ja juurdepääsuaeg pikeneb.

Kuid B-puu võib ühte sõlme salvestada palju võtmeid ja sellel võib olla mitu alamsõlme. See vähendab kõrgust, võimaldades kettale kiiremini juurde pääseda.

B-puu omadused

  1. Iga sõlme x jaoks salvestatakse võtmed järjest kasvavas järjekorras.
  2. Igas sõlmes on tõeväärtus x.leaf, mis on tõene, kui x on leht.
  3. Kui n on puu järjekord, võib iga sisemine sõlm sisaldada maksimaalselt n - 1 võtit koos osutusega igale lapsele.
  4. Igas sõlmes, välja arvatud juur, võib olla kuni n last ja vähemalt n / 2 last.
  5. Kõigil lehtedel on sama sügavus (st puu kõrgus-h).
  6. Juuril on vähemalt 2 last ja see sisaldab vähemalt ühte võtit.
  7. Kui n ≧ 1, siis iga n-klahvi B-puu kõrguse h ja minimaalne t ≧ 2, .h ≧ logt (n+1)/2

Operatsioonid

Otsimine

B-puu elemendi otsimine on kahendotsingu puust elemendi otsimise üldine vorm. Järgitakse järgmisi samme.

  1. Alustades juursõlmest, võrrelge k sõlme esimese võtmega.
    Kui k = the first key of the nodetagastate sõlme ja indeksi.
  2. Kui k.leaf = true, tagastage NULL (st ei leitud).
  3. Kui k < the first key of the root node, otsige selle klahvi vasakust lapsest rekursiivselt.
  4. Kui praeguses sõlmes on mitu võtit ja k> the first keyvõrrelge k sõlme järgmise võtmega.
    Kui k < next key, otsige selle võtme vasakust lapsest (st k asub esimese ja teise klahvi vahel).
    Muidu otsige võtme õigest lapsest.
  5. Korrake samme 1 kuni 4, kuni leht on kätte jõudnud.

Näite otsimine

  1. Otsime klahvi k = 173. astme all olevast puust. B-puu
  2. k ei leidu juurest, seega võrrelge seda juurvõtmega. k ei leidu juursõlmes
  3. Kuna k> 11, minge juursõlme parema lapse juurde. Minge paremale alampuule
  4. Võrdle k-ga 16. Kuna k> 16võrrelda k-d järgmise klahviga 18. Võrdle vasakult paremale suunatud klahvidega
  5. Kuna k < 18k jääb vahemikku 16–18. Otsige paremat 16-aastast last või 18-aastast vasakut k-d . K on 16–18
  6. k on leitud. k on leitud

Elemendi otsimise algoritm

 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)

Erinevate B-puu toimingute kohta lisateabe saamiseks külastage aadressi

  • Lisamine B-puule
  • Kustutamine B-puus

Pythoni, Java ja C / C ++ näited

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"; )

Keerukuse otsimine B-puult

Halvimal juhul on aja keerukus: Θ(log n)

Keskmine juhtum Aja keerukus: Θ(log n)

Parimal juhul aja keerukus: Θ(log n)

Keskmine juhtum Ruumi keerukus: Θ(n)

Halvimal juhul on ruumi keerukus: Θ(n)

B puu rakendused

  • andmebaasid ja failisüsteemid
  • andmeplokkide (teiseste andmekandjate) salvestamiseks
  • mitmetasandiline indekseerimine

Huvitavad Artiklid...