fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. // A node in 2-3-4 tree
  5. struct Node {
  6.     int keys[3];        // Maximum of 3 keys
  7.     Node* children[4];   // Maximum of 4 children
  8.     int nKeys;          // Number of keys in the node
  9.     bool isLeaf;        // Leaf indicator
  10.  
  11.     Node(bool leaf) {
  12.         isLeaf = leaf;
  13.         nKeys = 0;
  14.         for (int i = 0; i < 4; i++)
  15.             children[i] = nullptr;
  16.     }
  17. };
  18.  
  19. // Search a key in a 2-3-4 tree
  20. bool search(Node* root, int key) {
  21.     if (!root) return false;
  22.  
  23.     int i = 0;
  24.     while (i < root->nKeys && key > root->keys[i])
  25.         i++;
  26.  
  27.     if (i < root->nKeys && root->keys[i] == key)
  28.         return true;
  29.  
  30.     return (root->isLeaf) ? false : search(root->children[i], key);
  31. }
  32.  
  33. // Insert non-full helper
  34. void insertNonFull(Node* node, int key) {
  35.     int i = node->nKeys - 1;
  36.  
  37.     if (node->isLeaf) {
  38.         while (i >= 0 && node->keys[i] > key) {
  39.             node->keys[i + 1] = node->keys[i];
  40.             i--;
  41.         }
  42.         node->keys[i + 1] = key;
  43.         node->nKeys++;
  44.     } else {
  45.         while (i >= 0 && node->keys[i] > key)
  46.             i--;
  47.         i++;
  48.  
  49.         if (node->children[i]->nKeys == 3) {
  50.             int mid = node->children[i]->keys[1];
  51.             Node* leftChild = new Node(node->children[i]->isLeaf);
  52.             Node* rightChild = new Node(node->children[i]->isLeaf);
  53.  
  54.             leftChild->keys[0] = node->children[i]->keys[0];
  55.             leftChild->nKeys = 1;
  56.  
  57.             rightChild->keys[0] = node->children[i]->keys[2];
  58.             rightChild->nKeys = 1;
  59.  
  60.             for (int j = node->nKeys; j > i; j--) {
  61.                 node->keys[j] = node->keys[j - 1];
  62.                 node->children[j + 1] = node->children[j];
  63.             }
  64.  
  65.             node->keys[i] = mid;
  66.             node->children[i] = leftChild;
  67.             node->children[i + 1] = rightChild;
  68.             node->nKeys++;
  69.  
  70.             if (key < node->keys[i])
  71.                 insertNonFull(leftChild, key);
  72.             else
  73.                 insertNonFull(rightChild, key);
  74.         } else {
  75.             insertNonFull(node->children[i], key);
  76.         }
  77.     }
  78. }
  79.  
  80. // Main insert function
  81. void insert(Node*& root, int key) {
  82.     if (!root) {
  83.         root = new Node(true);
  84.         root->keys[0] = key;
  85.         root->nKeys = 1;
  86.     } else {
  87.         if (root->nKeys == 3) {
  88.             Node* newRoot = new Node(false);
  89.             newRoot->children[0] = root;
  90.  
  91.             insertNonFull(newRoot, key);
  92.             root = newRoot;
  93.         } else {
  94.             insertNonFull(root, key);
  95.         }
  96.     }
  97. }
  98.  
  99. // Inorder traversal (sorted output)
  100. void traverse(Node* root) {
  101.     if (!root) return;
  102.  
  103.     int i;
  104.     for (i = 0; i < root->nKeys; i++) {
  105.         traverse(root->children[i]);
  106.         cout << root->keys[i] << " ";
  107.     }
  108.     traverse(root->children[i]);
  109. }
  110.  
  111. int main() {
  112.     Node* root = nullptr;
  113.  
  114.     int keys[] = {10, 20, 30, 40, 50, 60};
  115.     for (int key : keys)
  116.         insert(root, key);
  117.  
  118.     cout << "Inorder traversal: ";
  119.     traverse(root);
  120.     cout << endl;
  121.  
  122.     cout << "Search 30: " << (search(root, 30) ? "Found" : "Not Found") << endl;
  123.  
  124.     return 0;
  125. }
  126.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Inorder traversal: 10 20 30 40 50 60 
Search 30: Found
https://ideone.com/v2ZHDv
language:
C++ (gcc 8.3)
created:
9 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!