Fusion Tree

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 2^w 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 log_Wn 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 node

struct node {
   int keys[B];               // Keys in the node
   struct node *child[B + 1]; // Child pointers (B+1 for B keys)
   int n;                     // Number of keys in the node
   int leaf;                  // 1 if the node is a leaf, 0 otherwise
};

// Root of the tree
struct node *root = NULL;

// Function to create a new node
struct node *createNode() {
   struct node *newNode = (struct node *)malloc(sizeof(struct node));
   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 full
void splitChild(struct node *parent, int i, struct node *fullChild) {
   struct node *halfChild = createNode();
   halfChild->leaf = fullChild->leaf;
   halfChild->n = B / 2;

   // Move the last B/2 keys of fullChild to halfChild
   for (int j = 0; j < B / 2; j++) {
      halfChild->keys[j] = fullChild->keys[j + B / 2];
   }

    // Move the child pointers of fullChild to halfChild
   if (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 parent
   for (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)
void insertNonFull(struct node *current, int key) {
   int i = current->n - 1;
   if (current->leaf) {
      // Find the position to insert the key
      while (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 key
      while (i >= 0 && current->keys[i] > key) {
         i--;
      }
      i++;
      if (current->child[i]->n == B) {
         // If the child is full, split it
         splitChild(current, i, current->child[i]);
         if (current->keys[i] < key) {
            i++;
         }
      }
      insertNonFull(current->child[i], key);
   }
}

// Insert a key into the tree
void insert(int key) {
   if (root == NULL) {
      root = createNode();
      root->keys[0] = key;
      root->n = 1;
   } else {
      if (root->n == B) {
         // If root is full, split it
         struct node *newNode = createNode();
         newNode->child[0] = root;
         root = newNode;
         splitChild(root, 0, newNode->child[0]);
        }
      insertNonFull(root, key);
   }
}

// Display the tree
void display(struct node *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 function
int main() {
   insert(10);
   insert(20);
   insert(30);
   insert(40);
    
   printf("Fusion Tree keys: ");
   display(root);
   return 0;
}

Fusion Tree keys: 10 20 30 40

// C++ Program to implement Fusion Tree
#include <iostream>
using namespace std;

#define W 32
#define B 4

struct node {
   int keys[B];
   struct node *child[B + 1];
   int n;
   int leaf;
};

struct node *root = NULL;

struct node *createNode() {
   struct node *newNode = new node;
   newNode->n = 0;
   newNode->leaf = 1;
   for (int i = 0; i <= B; i++) {
      newNode->child[i] = NULL;
   }
   return newNode;
}

void splitChild(struct node *parent, int i, struct node *fullChild) {
   struct node *halfChild = createNode();
   halfChild->leaf = fullChild->leaf;
   halfChild->n = B / 2;

   for (int j = 0; j < B / 2; j++) {
      halfChild->keys[j] = fullChild->keys[j + B / 2];
   }

   if (fullChild->leaf == 0) {
      for (int j = 0; j < B / 2 + 1; j++) {
         halfChild->child[j] = fullChild->child[j + B / 2];
      }
   }

   fullChild->n = B / 2;

   for (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++;
}

void insertNonFull(struct node *current, int key) {
   int i = current->n - 1;
   if (current->leaf) {
      while (i >= 0 && current->keys[i] > key) {
         current->keys[i + 1] = current->keys[i];
         i--;
      }
      current->keys[i + 1] = key;
      current->n++;
   } else {
      while (i >= 0 && current->keys[i] > key) {
         i--;
      }
      i++;
      if (current->child[i]->n == B) {
         splitChild(current, i, current->child[i]);
         if (current->keys[i] < key) {
            i++;
         }
      }
      insertNonFull(current->child[i], key);
   }
}

void insert(int key) {
   if (root == NULL) {
      root = createNode();
      root->keys[0] = key;
      root->n = 1;
   } else {
      if (root->n == B) {
         struct node *newNode = createNode();
         newNode->child[0] = root;
         root = newNode;
         splitChild(root, 0, newNode->child[0]);
      }
      insertNonFull(root, key);
   }
}

void display(struct node *root) {
   if (root == NULL) {
      return;
   }

   for (int i = 0; i < root->n; i++) {
      if (root->leaf == 0) {
         display(root->child[i]);
      }
      cout << root->keys[i] << " ";
   }

   if (root->leaf == 0) {
      display(root->child[root->n]);
   }
}

int main() {
   insert(10);
   insert(20);
   insert(30);
   insert(40);
   cout << "Fusion Tree keys: ";
   display(root);
   return 0;
}

Fusion Tree keys: 10 20 30 40

// Java Program to implement Fusion Tree
public class Main {
   static final int W = 32;
   static final int B = 4;

   static class Node {
      int keys[] = new int[B];
      Node child[] = new Node[B + 1];
      int n;
      int leaf;
   }

   static Node root = null;

   static Node createNode() {
      Node newNode = new Node();
      newNode.n = 0;
      newNode.leaf = 1;
      return newNode;
   }

   static void splitChild(Node parent, int i, Node fullChild) {
      Node halfChild = createNode();
      halfChild.leaf = fullChild.leaf;
      halfChild.n = B / 2;

      // Move the second half of the keys to the new halfChild node
      for (int j = 0; j < B / 2; j++) {
         halfChild.keys[j] = fullChild.keys[j + B / 2];
      }

      // Move the child pointers of fullChild to halfChild
      if (fullChild.leaf == 0) {
         for (int j = 0; j < B / 2 + 1; j++) {
            halfChild.child[j] = fullChild.child[j + B / 2];
         }
      }

      // Update the number of keys in the fullChild node
      fullChild.n = B / 2;

      // Move the child pointers in the parent node
      for (int j = parent.n; j > i; j--) {
         parent.child[j + 1] = parent.child[j];
      }
      parent.child[i + 1] = halfChild;

      // Move the middle key from fullChild to the parent node
      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++;
   }

   static void insertNonFull(Node current, int key) {
      int i = current.n - 1;

      // If the node is a leaf, insert the key
      if (current.leaf == 1) {
         while (i >= 0 && current.keys[i] > key) {
            current.keys[i + 1] = current.keys[i];
            i--;
         }
         current.keys[i + 1] = key;
         current.n++;
      } else {
         // If the node is not a leaf, find the correct child and recurse
         while (i >= 0 && current.keys[i] > key) {
            i--;
         }
         i++;

         // If the child is full, split it
         if (current.child[i].n == B) {
            splitChild(current, i, current.child[i]);
            if (current.keys[i] < key) {
               i++;
            }
         }

         insertNonFull(current.child[i], key);
      }
   }

   static void insert(int key) {
      if (root == null) {
         root = createNode();
         root.keys[0] = key;
         root.n = 1;
      } else {
         if (root.n == B) {
            Node newNode = createNode();
            newNode.child[0] = root;
            root = newNode;
            splitChild(root, 0, newNode.child[0]);
         }
         insertNonFull(root, key);
      }
   }

   static void display(Node root) {
      if (root == null) {
         return;
      }

      // Print the keys in the current node
      for (int i = 0; i < root.n; i++) {
         if (root.leaf == 0) {
            display(root.child[i]);
         }
         System.out.print(root.keys[i] + " ");
      }

      // If the current node is not a leaf, display the children
      if (root.leaf == 0) {
         display(root.child[root.n]);
      }
   }

   public static void main(String[] args) {
      insert(10);
      insert(20);
      insert(30);
      insert(40);

      System.out.print("Fusion Tree keys: ");
      display(root);
   }
}

Fusion Tree keys: 10 20 30 40

# Python Program to implement Fusion Tree
W = 32  # Word size
B = 4   # Branching factor

class Node:
   def __init__(self):
      self.keys = [0] * B  # Keys array
      self.child = [None] * (B + 1)  # Child pointers array
      self.n = 0  # Number of keys
      self.leaf = 1  # Flag if leaf node

root = None

# Create a new node
def createNode():
   newNode = Node()
   newNode.n = 0
   newNode.leaf = 1
   return newNode

# Split a full child node
def splitChild(parent, i, fullChild):
   halfChild = createNode()
   halfChild.leaf = fullChild.leaf
   halfChild.n = B // 2  # Move half keys

   # Move second half of keys to halfChild
   for j in range(B // 2, B):
      halfChild.keys[j - B // 2] = fullChild.keys[j]

   # Move children if not leaf
   if not fullChild.leaf:
      for j in range(B // 2 + 1):
         halfChild.child[j] = fullChild.child[j + B // 2]
   
   fullChild.n = B // 2  # Update fullChild keys count

   # Shift parent's children and keys
   for j in range(parent.n, i, -1):
      parent.child[j + 1] = parent.child[j]
   parent.child[i + 1] = halfChild

   # Move parent's keys
   for j in range(parent.n - 1, i - 1, -1):
      parent.keys[j + 1] = parent.keys[j]
   parent.keys[i] = fullChild.keys[B // 2]
   parent.n += 1

# Insert into non-full node
def insertNonFull(current, key):
   i = current.n - 1
   if current.leaf:
      # Insert key into leaf node
      while i >= 0 and current.keys[i] > key:
         current.keys[i + 1] = current.keys[i]
         i -= 1
      current.keys[i + 1] = key
      current.n += 1
   else:
      # Find appropriate child
      while i >= 0 and current.keys[i] > key:
         i -= 1
      i += 1
      if current.child[i].n == B:
         splitChild(current, i, current.child[i])  # Split full child
         if current.keys[i] < key:
            i += 1
      insertNonFull(current.child[i], key)

# Insert a key into the tree
def insert(key):
   global root
   if root is None:
      root = createNode()
      root.keys[0] = key
      root.n = 1
   else:
      if root.n == B:
         newNode = createNode()
         newNode.child[0] = root
         root = newNode
         splitChild(root, 0, newNode.child[0])
      insertNonFull(root, key)

# Display the tree keys
def display(root):
   for i in range(root.n):
      if root.leaf == 0:
         display(root.child[i])
      print(root.keys[i], end=" ")
   if root.leaf == 0:
      display(root.child[root.n])

# Insert test values
insert(10)
insert(20)
insert(30)
insert(40)

# Display Fusion Tree
print("Fusion Tree keys:", end=" ")
display(root)

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)

struct node {
   int keys[B];            // Array to store keys
   struct node *child[B + 1]; // Array of child pointers
   int n;                  // Number of keys in the node
   int leaf;               // Flag to check if it's a leaf node
};

struct node *root = NULL;

// Create a new node
struct node* createNode() {
   struct node *newNode = (struct node*)malloc(sizeof(struct node));
   newNode->n = 0;
   newNode->leaf = 1;
   return newNode;
}

// Split the child node
void splitChild(struct node *parent, int i, struct node *fullChild) {
   struct node *halfChild = createNode();
   halfChild->leaf = fullChild->leaf;
   halfChild->n = B / 2;

   // Move the second half of the keys to the new child
   for (int j = 0; j < B / 2; j++) {
      halfChild->keys[j] = fullChild->keys[j + B / 2];
   }

   // Move the second half of the children
   if (!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 space
   for (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 space
   for (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 node
void insertNonFull(struct node *node, int key) {
   int i = node->n - 1;
   if (node->leaf) {
      // Find the position to insert the key
      while (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 key
      while (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 tree
void insert(int key) {
   if (root == NULL) {
      root = createNode();
      root->keys[0] = key;
      root->n = 1;
   } else {
      if (root->n == B) {
         struct node *newRoot = createNode();
         newRoot->child[0] = root;
         root = newRoot;
         splitChild(root, 0, newRoot->child[0]);
      }
      insertNonFull(root, key);
   }
}

// Display the keys in the tree
void display(struct node *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 tree
void search(struct node *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 tree
void delete(struct node *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);
      }
   }
}

int main() {
   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");

   return 0;
}

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

//C++ Program Search and Delete Elements in Fusion Tree
#include <iostream>
using namespace std;

#define W 32
#define B 4  // Maximum number of keys in a node (B+1 children)

struct node{
   int keys[W];
   struct node *child[W+1];
   int n;
   int leaf;
};

struct node *root = NULL;

struct node *createNode(){
   struct node *newNode = new node;
   newNode->n = 0;
   newNode->leaf = 1;
   return newNode;
}

// Split a full child node
void splitChild(struct node *parent, int i, struct node *fullChild){
   struct node *halfChild = createNode();
   halfChild->leaf = fullChild->leaf;
   halfChild->n = B / 2;
   
   // Move second half of keys to the new child
   for (int j = 0; j < B / 2; j++){
      halfChild->keys[j] = fullChild->keys[j + B / 2];
   }
   
   if (!fullChild->leaf){
      // Move second half of children to the new child
      for (int j = 0; j < B / 2 + 1; j++){
         halfChild->child[j] = fullChild->child[j + B / 2];
      }
   }
   
   fullChild->n = B / 2;
   
   // Move children of parent to make space
   for (int j = parent->n; j > i; j--){
      parent->child[j + 1] = parent->child[j];
   }
   
   parent->child[i + 1] = halfChild;
   
   // Move keys in parent to make space
   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 key into a non-full node
void insertNonFull(struct node *node, int key){
   int i = node->n - 1;
   if (node->leaf){
      // Find position to insert the key
      while (i >= 0 && node->keys[i] > key){
         node->keys[i + 1] = node->keys[i];
         i--;
      }
      node->keys[i + 1] = key;
      node->n++;
   }
   else{
      // Find child to insert into
      while (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 key into the tree
void insert(int key){
   if (root == NULL){
      root = createNode();
      root->keys[0] = key;
      root->n = 1;
   }
   else{
      if (root->n == B){
         struct node *newNode = createNode();
         newNode->child[0] = root;
         root = newNode;
         splitChild(root, 0, newNode->child[0]);
      }
      insertNonFull(root, key);
   }
}

// Display the keys in the tree
void display(struct node *root){
   if (root != NULL){
      for (int i = 0; i < root->n; i++){
         if (root->leaf == 0){
            display(root->child[i]);
         }
         cout << root->keys[i] << " ";
      }
      if (root->leaf == 0){
         display(root->child[root->n]);
      }
      cout << endl;
   }
}

// Search the tree for a key
void search(int key){
   for (int i = 0; i < root->n; i++){
      if (root->keys[i] == key){
         cout << "Element " << key << "found " <<endl;
         return;
      }
   }
   cout << "Element " << key << " not found " << endl;
}

// Delete the element from the tree
void deleteElement(int key){
   for (int i = 0; i < root->n; i++){
      if (root->keys[i] == key){
         for (int j = i; j < root->n - 1; j++){
            root->keys[j] = root->keys[j + 1];
         }
         root->n--;
         cout << "Element " << key << " deleted " << endl;
         return;
      }
   }
   cout << "Element " << key << " not found " << endl;
}


int main(){
   insert(10);
   insert(20);
   insert(30);
   insert(40);
   cout << "Fusion Tree keys: ";
   display(root);
   search(20);
   deleteElement(20);
   search(20);
   cout << "Fusion Tree after deletion: ";
   display(root);
   return 0;
}

Fusion Tree keys: 10 20 30 40
Element found 20
Element deleted 20
Element not found 20
Fusion Tree after deletion: 10 30 40

   //Java Program Search and Delete Elements in Fusion Tree

public class Main{
   static final int W = 32;
   static final int B = 4;  // Maximum number of keys in a node (B+1 children)

   static class Node{
      int keys[] = new int[W];
      Node child[] = new Node[W + 1];
      int n;
      int leaf;
   }

   static Node root = null;

   static Node createNode(){
      Node newNode = new Node();
      newNode.n = 0;
      newNode.leaf = 1;
      return newNode;
   }

   static void splitChild(Node parent, int i, Node fullChild){
      Node halfChild = createNode();
      halfChild.leaf = fullChild.leaf;
      halfChild.n = B / 2;

      // Move second half of keys to the new child
      for (int j = 0; j < B / 2; j++){
         halfChild.keys[j] = fullChild.keys[j + B / 2];
      }

      if (fullChild.leaf == 0){
         // Move second half of children to the new child
         for (int j = 0; j < B / 2 + 1; j++){
            halfChild.child[j] = fullChild.child[j + B / 2];
         }
      }

      fullChild.n = B / 2;

      // Move children of parent to make space
      for (int j = parent.n; j > i; j--){
         parent.child[j + 1] = parent.child[j];
      }

      parent.child[i + 1] = halfChild;

      // Move keys in parent to make space
      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++;
   }

   static void insertNonFull(Node node, int key){
      int i = node.n - 1;
      if (node.leaf == 1){
         // Find the right position for the key
         while (i >= 0 && node.keys[i] > key){
            node.keys[i + 1] = node.keys[i];
            i--;
         }
         node.keys[i + 1] = key;
         node.n++;
      }
      else{
         // Find the child to insert into
         while (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);
      }
   }

   static void insert(int key){
      if (root == null){
         root = createNode();
         root.keys[0] = key;
         root.n = 1;
      }
      else{
         if (root.n == B){
            Node newNode = createNode();
            newNode.child[0] = root;
            root = newNode;
            splitChild(root, 0, newNode.child[0]);
         }
         insertNonFull(root, key);
      }
   }

   static void display(Node node){
      if (node != null){
         for (int i = 0; i < node.n; i++){
            if (node.leaf == 0){
               display(node.child[i]);
            }
            System.out.print(node.keys[i] + " ");
         }
         if (node.leaf == 0){
            display(node.child[node.n]);
         }
      }
   }

   static void search(int key){
      for (int i = 0; i < root.n; i++){
         if (root.keys[i] == key){
            System.out.println("Element " + key +" found ");
            return;
         }
      }
      System.out.println("Element " + key + " not found ");
   }

   static void delete(int key){
      for (int i = 0; i < root.n; i++){
         if (root.keys[i] == key){
            for (int j = i; j < root.n - 1; j++){
               root.keys[j] = root.keys[j + 1];
            }
            root.n--;
            System.out.println("Element " + key + " deleted ");
            return;
         }
      }
      System.out.println("Element " + key + " not found ");
   }

   public static void main(String[] args){
      insert(10);
      insert(20);
      insert(30);
      insert(40);

      System.out.print("Tree after insertions: ");
      display(root);
      System.out.println();

      search(20);
      delete(20);
      search(20);

      System.out.print("Tree after deletion: ");
      display(root);
   }
}

Tree after insertions: 10 20 30 40
Element 20 found
Element 20 deleted
Element 20 not found
Tree after deletion: 10 30 40

   # Python Program Search and Delete Elements in Fusion Tree
W = 32
B = 4  # Maximum number of keys in a node (B+1 children)

class Node:
   def __init__(self):
      self.keys = [0] * W
      self.child = [None] * (W + 1)
      self.n = 0
      self.leaf = 1

root = None

def createNode():
   newNode = Node()
   newNode.n = 0
   newNode.leaf = 1
   return newNode

def splitChild(parent, i, fullChild):
   halfChild = createNode()
   halfChild.leaf = fullChild.leaf
   halfChild.n = B // 2
   
   # Move second half of keys to the new child
   for j in range(B // 2):
      halfChild.keys[j] = fullChild.keys[j + B // 2]
   
   if not fullChild.leaf:
      # Move second half of children
      for j in range(B // 2 + 1):
         halfChild.child[j] = fullChild.child[j + B // 2]
   
   fullChild.n = B // 2
   
   # Move children of parent to make space
   for j in range(parent.n, i, -1):
      parent.child[j + 1] = parent.child[j]
   
   parent.child[i + 1] = halfChild
   
   # Move keys in parent to make space
   for j in range(parent.n - 1, i - 1, -1):
      parent.keys[j + 1] = parent.keys[j]
   
   parent.keys[i] = fullChild.keys[B // 2]
   parent.n += 1

def insertNonFull(node, key):
   i = node.n - 1
   if node.leaf:
      # Find the right position for the key
      while i >= 0 and node.keys[i] > key:
         node.keys[i + 1] = node.keys[i]
         i -= 1
      node.keys[i + 1] = key
      node.n += 1
   else:
      # Find the child to insert into
      while i >= 0 and node.keys[i] > key:
         i -= 1
      i += 1
      if node.child[i].n == B:
         splitChild(node, i, node.child[i])
         if node.keys[i] < key:
            i += 1
      insertNonFull(node.child[i], key)

def insert(key):
   global root
   if root is None:
      root = createNode()
      root.keys[0] = key
      root.n = 1
   else:
      if root.n == B:
         newNode = createNode()
         newNode.child[0] = root
         root = newNode
         splitChild(root, 0, newNode.child[0])
      insertNonFull(root, key)

def display(root):
   if root:
      for i in range(root.n):
         if root.leaf == 0:
            display(root.child[i])
         print(root.keys[i], end=" ")
      if root.leaf == 0:
         display(root.child[root.n])

def search(key):
   global root
   # Search the element in the tree
   for i in range(root.n):
      if root.keys[i] == key:
         print("Element", key, "found ")
         return
   print("Element", key, "not found ")

def delete(key):
   global root
   # Delete the element from the tree
   for i in range(root.n):
      if root.keys[i] == key:
         for j in range(i, root.n - 1):
            root.keys[j] = root.keys[j + 1]
         root.n -= 1
         print("Element",key, "deleted " )
         return
   print("Element",key, "not found " )

# Inserting keys
insert(10)
insert(20)
insert(30)
insert(40)

# Display tree
print("Fusion Tree keys: ")
display(root)

# Search and delete operations
search(20)
delete(20)
search(20)

# Display tree after deletion
print("Fusion Tree keys after deletion: ")
display(root)

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(log_Wn)
• Deletion: O(log_Wn)
• Searching: O(log_Wn)

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.