B-Trees in C++
The root has at least one key
Non-root nodes have at least m/2 subtrees (i.e., at least (m - 1)/2 keys)
All the empty subtrees (i.e., external nodes) are at the same level
B-trees are especially useful for trees stored on disks, since their height, and hence also the number of disk accesses, can be kept small.
The growth and contraction of m-way search trees occur at the leaves. On the other hand, B-trees grow and contract at the root.
Insertions
-Insert the key to a leaf
-Overfilled nodes should send the middle key to their parent, and split into two at the location of the submitted key.
Add 19
Add 21
Final tree
Deletions
Key that is to be removed from a node with non-empty subtrees is being replaced with the largest key of the left subtree or the smallest key in the right subtree. (The replacement is guaranteed to come from a leaf.)
Remove 26
If a node becomes under staffed, it looks for a sibling with an extra key. If such a sibling exist, the node takes a key from the parent, and the parent gets the extra key from the sibling. 
Remove 22
If a node becomes under staffed, and it can’t receive a key from a sibling, the node is merged with a sibling and a key from the parent is moved down to the node. 
Remove 18
AVL Trees
An AVL tree (also called an "admissible tree") is a tree in which the height of the left and right subtrees of every node differ by at most one - referred to as "height-balanced".
Example AVL trees:
Example non-AVL trees:
In order to indicate the differences between the heights of the right and left subtrees of a given (root) node, a balance factor is defined for that node of the subtree.
We define the balance factor, BF:
BF = (height of right subtree - height of left subtree)
So, BF = -1, 0 or +1 for an AVL tree.
Balance factors for example AVL
trees (node key values not shown):
When the AVL property is lost we can rebalance the tree via one of four rotations:
1)Single Right Rotation (SRR)
2)Single Left Rotation (SLR)
3)Double Left Rotation (DLR)
4)Double Right Rotation (DRR)
Single Right Rotation (SRR):
A is the node that the rotation is performed on. This rotation is performed when A is unbalanced to the left (the left subtree is 2 higher than the right subtree) and B is left-heavy (the left subtree of B is 1 higher than the right subtree of B). T1, T2 and T3 represent subtrees (a node was added to T1 which made B leftheavy and unbalanced A).
Single Left Rotation (SLR):
A is the node that the rotation is performed on. This rotation is performed when A is unbalanced to the right (the right subtree is 2 higher than the left subtree) and B is right-heavy (the right subtree of B is 1 higher than the left subtree of B). T1, T2 and T3 represent subtrees (a node was added to T3 which made B right-heavy and unbalanced A).
Double Left Rotation (DLR):
C is the node that the rotation is performed on. This rotation is performed when C is unbalanced to the left (the left subtree is 2 higher than the right subtree), A is right-heavy (the right subtree of A is 1 higher than the left subtree of A) and B is left-heavy. T1, T2, T3, and T4 represent subtrees (a node was added to T2 which made B left-heavy, made A right-heavy and unbalanced C). This consists of a single left rotation at node A, followed by a single right at node C.
Double Right Rotation (DRR):
A is the node that the rotation is performed on. This rotation is performed when A is unbalanced to the right (the right subtree is 2 higher than the left subtree), C is leftheavy (the left subtree of C is 1 higher than the right subtree of C) and B is right-heavy. T1, T2, T3, and T4 represent subtrees (a node was added to T3 which made B right-heavy, made C left-heavy and unbalanced A). This consists of a single right at node C, followed by a single left at node A.
Thanks for visiting this blog. How is the content?. Your comment is great gift to my work. Cheers.
No comments:
Post a Comment