KEMBAR78
B Tree Assignment | PDF
Scribd
Upload
440 views4 pages

B Tree Assignment

This document discusses B-Trees, which are self-balancing tree data structures used to efficiently store large ordered datasets. B-Trees allow for insertion, deletion, and search operations in O(Log(n)) time. The key points are: 1) B-Trees are multi-way trees where each node can have multiple children determined by the B-Tree's order, or maximum children per node. 2) Insertion works by splitting full nodes and moving keys up the tree until an open slot is found in a leaf node. 3) Deletion is more complex as keys can be removed from internal nodes, requiring rearrangement of children.

Uploaded by

Zeeshan Ali
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
440 views4 pages

B Tree Assignment

This document discusses B-Trees, which are self-balancing tree data structures used to efficiently store large ordered datasets. B-Trees allow for insertion, deletion, and search operations in O(Log(n)) time. The key points are: 1) B-Trees are multi-way trees where each node can have multiple children determined by the B-Tree's order, or maximum children per node. 2) Insertion works by splitting full nodes and moving keys up the tree until an open slot is found in a leaf node. 3) Deletion is more complex as keys can be removed from internal nodes, requiring rearrangement of children.

Uploaded by

Zeeshan Ali
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

Data Structures and Algorithm

CC2042
V2
Assignment#4
B Tree:

A B-Tree is a self-balancing tree data structure that is used to store


ordered data in a way that allows for efficient insertion, deletion and search
operations. B-Tree is primarily used for external memory algorithms and for
large data sets that don't fit in the main memory.

A B-Tree is a multi-way tree, which means that a node in a B-Tree can have
more than two children. The number of children a node can have is determined
by the order of the B-Tree. The order of a B-Tree is defined as the maximum
number of children a node can have.

Time Complexity:

Search: O(Log(n))

Insertion: O(Log(n))

Deletion: O(Log(n))

Insertion Algorithm:
1) Initialize x as root.
2) While x is not leaf, do following
..a) Find the child of x that is going to be traversed next. Let the child be y.
..b) If y is not full, change x to point to y.
..c) If y is full, split it and change x to point to one of the two parts of y. If k is
smaller than mid key in y, then set x as the first part of y. Else second part of y.
When we split y, we move a key from y to its parent x.
3) The loop in step 2 stops when x is leaf. x must have space for 1 extra key as
we have been splitting all nodes in advance. So simply insert k to x

Let Study it with demonstration:


Let us now insert 60. Since root node is full, it will first split into two, then 60 will
be inserted into the appropriate child.

Let us now insert 70 and 80.


Let us now insert 90.

Deletion Algorithm:

Deletion from a B-tree is more complicated than insertion, because we can


delete a key from any node-not just a leaf—and when we delete a key from an
internal node, we will have to rearrange the node’s children.

You might also like