Fusion Tree is a part of advanced data structures which is used for maintaining the ordered set of elements.
On a finite universe, if each input integers has size less than 2w and if those numbers are non-negative, it implements an associative array on W-bit integers.
It uses the combination of a B-Tree and a hash table which help in reducing the time complexity of the operations like insertion, deletion and searching in the tree.
How Fusion Tree Works?
Following factors are considered while implementing a fusion tree:
- Bit manipulation : The tree extracts specific bits from stored integers and processes them in order to speed up the operations.
- Parallelism : It uses 64 or 128 bits machine words to compare and manipulate multiple keys at same time.
- Sketching : Sketching means summarizing integers into smaller representation (called as sketches) which can be used to compare the integers. It is done by extracting most important bits from the integers. that reduces the number of comparisons it usually requires to compare two integers.
- Precomputed Operations : It pre-computes the operations like min, max, successor and predecessor which are used frequently in the tree.
Representation of Fusion Tree
Fusion tree is represented as a B-tree of height logWn where n is the number of elements in the tree.
Here, W is the number of bits in the integer.
Each node can hold child point upto B+1 just like a B-tree where B is the maximum number of children a node can have.
Operations on Fusion Tree
Following are the operations that can be performed on a fusion tree:
- Insertion
- Deletion
- Searching
Implementation of Fusion Tree
Algorithm to Insert and Create Elements in Fusion Tree
2. Create a fusion tree with root node as NULL 3. Insert the elements in the tree 4. If the tree is empty, create a new node and insert the element in it 5. If the tree is not empty, find the appropriate node to insert the element 6. If the node is full, split the node and insert the element in the appropriate node 7. Repeat the steps 5 and 6 until all the elements are inserted
Code to Insert Elements in Fusion Tree
Now let’s see how we can implement a fusion tree in C, C++, Java and Python:
#include <stdio.h>#include <stdlib.h>#define W 32 // Word size (number of bits in an integer)#define B 4 // Max number of keys per nodestructnode{int keys[B];// Keys in the nodestructnode*child[B +1];// Child pointers (B+1 for B keys)int n;// Number of keys in the nodeint leaf;// 1 if the node is a leaf, 0 otherwise};// Root of the treestructnode*root =NULL;// Function to create a new nodestructnode*createNode(){structnode*newNode =(structnode*)malloc(sizeof(structnode));
newNode->n =0;
newNode->leaf =1;for(int i =0; i <= B; i++){
newNode->child[i]=NULL;}return newNode;}// Split the child node if it is fullvoidsplitChild(structnode*parent,int i,structnode*fullChild){structnode*halfChild =createNode();
halfChild->leaf = fullChild->leaf;
halfChild->n = B /2;// Move the last B/2 keys of fullChild to halfChildfor(int j =0; j < B /2; j++){
halfChild->keys[j]= fullChild->keys[j + B /2];}// Move the child pointers of fullChild to halfChildif(fullChild->leaf ==0){for(int j =0; j < B /2+1; j++){
halfChild->child[j]= fullChild->child[j + B /2];}}
fullChild->n = B /2;// Move the middle key from fullChild to parentfor(int j = parent->n; j > i; j--){
parent->child[j +1]= parent->child[j];}
parent->child[i +1]= halfChild;for(int j = parent->n -1; j >= i; j--){
parent->keys[j +1]= parent->keys[j];}
parent->keys[i]= fullChild->keys[B /2];
parent->n++;}// Insert a key into a node (when the node is not full)voidinsertNonFull(structnode*current,int key){int i = current->n -1;if(current->leaf){// Find the position to insert the keywhile(i >=0&& current->keys[i]> key){
current->keys[i +1]= current->keys[i];
i--;}
current->keys[i +1]= key;
current->n++;}else{// Find the correct child to insert the keywhile(i >=0&& current->keys[i]> key){
i--;}
i++;if(current->child[i]->n == B){// If the child is full, split itsplitChild(current, i, current->child[i]);if(current->keys[i]< key){
i++;}}insertNonFull(current->child[i], key);}}// Insert a key into the treevoidinsert(int key){if(root ==NULL){
root =createNode();
root->keys[0]= key;
root->n =1;}else{if(root->n == B){// If root is full, split itstructnode*newNode =createNode();
newNode->child[0]= root;
root = newNode;splitChild(root,0, newNode->child[0]);}insertNonFull(root, key);}}// Display the treevoiddisplay(structnode*root){if(root ==NULL){return;}for(int i =0; i < root->n; i++){if(root->leaf ==0){display(root->child[i]);}printf("%d ", root->keys[i]);}if(root->leaf ==0){display(root->child[root->n]);}}// Main functionintmain(){insert(10);insert(20);insert(30);insert(40);printf("Fusion Tree keys: ");display(root);return0;}
Output
Following is the output of the above code:
Fusion Tree keys: 10 20 30 40
Search and Delete Operations in Fusion Tree
Search and delete operations in a fusion tree are similar to the insertion operation. You can implement these operations by modifying the above code.
Search operation is used to find the element in the tree and delete operation is used to delete the element from the tree.
Algorithm to Search and Delete Elements in Fusion Tree
Following are the steps to implement search and delete operations in a fusion tree:
2. Search the element in the tree 3. If the element is found, delete the element from the tree 4. If the element is not found, display the message "Element not found"
Code to Search and Delete Elements in Fusion Tree
Now let’s see how we can implement search and delete operations in a fusion tree in C, C++, Java and Python:
#include <stdio.h>#include <stdlib.h>#define W 32#define B 4 // The branching factor (maximum number of keys per node)structnode{int keys[B];// Array to store keysstructnode*child[B +1];// Array of child pointersint n;// Number of keys in the nodeint leaf;// Flag to check if it's a leaf node};structnode*root =NULL;// Create a new nodestructnode*createNode(){structnode*newNode =(structnode*)malloc(sizeof(structnode));
newNode->n =0;
newNode->leaf =1;return newNode;}// Split the child nodevoidsplitChild(structnode*parent,int i,structnode*fullChild){structnode*halfChild =createNode();
halfChild->leaf = fullChild->leaf;
halfChild->n = B /2;// Move the second half of the keys to the new childfor(int j =0; j < B /2; j++){
halfChild->keys[j]= fullChild->keys[j + B /2];}// Move the second half of the childrenif(!fullChild->leaf){for(int j =0; j < B /2+1; j++){
halfChild->child[j]= fullChild->child[j + B /2];}}
fullChild->n = B /2;// Move the children of the parent to make spacefor(int j = parent->n; j > i; j--){
parent->child[j +1]= parent->child[j];}// Make room for the new child
parent->child[i +1]= halfChild;// Move the keys of the parent to make spacefor(int j = parent->n -1; j >= i; j--){
parent->keys[j +1]= parent->keys[j];}// Move the middle key up to the parent
parent->keys[i]= fullChild->keys[B /2];
parent->n++;}// Insert the key into a non-full nodevoidinsertNonFull(structnode*node,int key){int i = node->n -1;if(node->leaf){// Find the position to insert the keywhile(i >=0&& node->keys[i]> key){
node->keys[i +1]= node->keys[i];
i--;}
node->keys[i +1]= key;
node->n++;}else{// Find the correct child to insert the keywhile(i >=0&& node->keys[i]> key){
i--;}
i++;if(node->child[i]->n == B){splitChild(node, i, node->child[i]);if(node->keys[i]< key){
i++;}}insertNonFull(node->child[i], key);}}// Insert a key into the treevoidinsert(int key){if(root ==NULL){
root =createNode();
root->keys[0]= key;
root->n =1;}else{if(root->n == B){structnode*newRoot =createNode();
newRoot->child[0]= root;
root = newRoot;splitChild(root,0, newRoot->child[0]);}insertNonFull(root, key);}}// Display the keys in the treevoiddisplay(structnode*root){if(root !=NULL){for(int i =0; i < root->n; i++){if(!root->leaf){display(root->child[i]);}printf("%d ", root->keys[i]);}if(!root->leaf){display(root->child[root->n]);}}}// Search for a key in the treevoidsearch(structnode*root,int key){if(root !=NULL){for(int i =0; i < root->n; i++){if(root->keys[i]== key){printf("Element %d found\n", key);return;}}for(int i =0; i < root->n; i++){if(key < root->keys[i]){search(root->child[i], key);return;}}search(root->child[root->n], key);}}// Delete a key from the treevoiddelete(structnode*root,int key){if(root !=NULL){int i;for(i =0; i < root->n; i++){if(root->keys[i]== key){break;}}if(i < root->n){for(int j = i; j < root->n -1; j++){
root->keys[j]= root->keys[j +1];}
root->n--;printf("Element %d deleted\n", key);}else{printf("Element %d not found\n", key);}}}intmain(){insert(10);insert(20);insert(30);insert(40);printf("Fusion Tree keys: ");display(root);printf("\n");search(root,20);delete(root,20);search(root,20);printf("Fusion Tree keys after deletion: ");display(root);printf("\n");return0;}
Output
Following is the output of the above code:
Fusion Tree keys: 10 20 30 40 Element 20 found Element 20 deleted Element 20 not found Fusion Tree keys after deletion: 10 30 40
Time Complexity of Fusion Tree
Time complexity of the operations on a fusion tree is as follows:
- Insertion: O(logWn)
- Deletion: O(logWn)
- Searching: O(logWn)
Here, n is the number of elements in the tree and W is the word size.
Applications of Fusion Tree
Fusion trees are used in various applications where we need to store a large number of elements and perform operations like insertion, deletion, and searching efficiently. Some of the applications of fusion trees are:
- Database indexing
- File systems
- Geographic information systems
- Network routing
- Computer graphics
These are some of the applications where fusion trees are used to store and manage large datasets efficiently.
Conclusion
In this chapter, we learned about fusion trees, a data structure that is used to store a large number of elements efficiently. We discussed the structure of a fusion tree, its operations like insertion, deletion, and searching, and the time complexity of these operations. We also saw how to implement fusion trees in C, C++, Java, and Python and perform search and delete operations on them. We also discussed the applications of fusion trees in various fields.
Leave a Reply