fork download
copy 
  1.  
  2. class BTree
  3. {
  4. final int MAX = 4;
  5. final int MIN = 2;
  6. //15 21 35 42 29 11 12 18 20 23 25 27 31 33 36 39 45 47 50 55 B-Tree of order 5
  7. class BTNode
  8. {
  9. int count;
  10. int key[] = new int[MAX+1];
  11. BTNode child[] = new BTNode[MAX+1];
  12. }
  13. BTNode root = new BTNode();
  14. class Ref
  15. { int m;
  16. }
  17. void insertTree( int val )
  18. {
  19. Ref i = new Ref();
  20. BTNode c = new BTNode();
  21. BTNode node = new BTNode();
  22. Boolean pushup;
  23. pushup = pushDown( val, root, i, c );
  24. if ( pushup )
  25. {
  26. node.count = 1;
  27. node.key[1] = i.m;
  28. node.child[0] = root;
  29. node.child[1] = c;
  30. root = node;
  31. }
  32. }
  33. boolean pushDown( int val, BTNode node, Ref p, BTNode c )
  34. {
  35. Ref k = new Ref();
  36. if ( node == null )
  37. {
  38. p.m = val;
  39. c = null;
  40. return true;
  41. }
  42. else {
  43. if ( searchNode( val, node, k ) )
  44. System.out.println("Key already exists.");
  45. if ( pushDown( val, node.child[k.m], p, c ) )
  46. {
  47. if ( node.count < MAX )
  48. {
  49. pushIn( p.m, c, node, k.m );
  50. return false;
  51. }
  52. else
  53. {
  54. split( p.m, c, node, k.m, p, c );
  55. return true;
  56. }
  57. }
  58. return false;
  59. }
  60. }
  61. BTNode searchTree( int val, BTNode root, Ref pos )
  62. {
  63. if ( root == null ) return null ;
  64. else
  65. {
  66. if ( searchNode( val, root, pos ) )
  67. return root;
  68. else
  69. return searchTree( val, root.child[pos.m], pos );
  70. }
  71. }
  72. boolean searchNode( int val, BTNode node, Ref pos )
  73. {
  74. if ( val < node.key[1] )
  75. {
  76. pos.m = 0 ; return false ;
  77. }
  78. else
  79. {
  80. pos.m = node.count ;
  81. while ( ( val < node.key[pos.m] ) && pos.m > 1 )
  82. (pos.m)--;
  83. if ( val == node.key[pos.m] )
  84. return true;
  85. else
  86. return false;
  87. }
  88. }
  89. void pushIn( int val, BTNode c, BTNode node, int k )
  90. {
  91. int i ;
  92. for ( i = node.count; i > k ; i-- )
  93. {
  94. node.key[i + 1] = node.key[i];
  95. node.child[i + 1] = node.child[i];
  96. }
  97. node.key[k + 1] = val ;
  98. node.child[k + 1] = c ;
  99. node.count++ ;
  100. }
  101. void split( int val, BTNode c, BTNode node, int k, Ref y, BTNode newnode )
  102. {
  103. int i, mid;
  104. if ( k <= MIN )
  105. mid = MIN;
  106. else
  107. mid = MIN + 1;
  108. newnode = new BTNode();
  109. for ( i = mid+1; i <= MAX; i++ )
  110. {
  111. newnode.key[i-mid] = node.key[i];
  112. newnode.child[i-mid] = node.child[i];
  113. }
  114. newnode.count = MAX - mid;
  115. node.count = mid;
  116. if ( k <= MIN ) pushIn ( val, c, node, k );
  117. else
  118. pushIn ( val, c, newnode, k-mid ) ;
  119. y.m = node.key[node.count];
  120. newnode.child[0] = node.child[node.count] ;
  121. node.count-- ;
  122. }
  123. void displayTree()
  124. {
  125. display( root );
  126. } 
  127. void display( BTNode root )
  128. {
  129. int i;
  130. if ( root != null ) {
  131. for ( i = 0; i < root.count; i++ )
  132. {
  133. display( root.child[i] );
  134. System.out.print( root.key[i+1] + " " );
  135. }
  136. display( root.child[i] );
  137. }
  138. }
  139. }
  140. class BTreeDemo
  141. {
  142. public static void main( String[] args )
  143. {
  144. BTree bt = new BTree();
  145. int[] arr = { 11, 23, 21, 12, 31, 18, 25, 35, 29, 20, 45, 27, 42, 55, 15, 33, 36, 47, 50, 39 };
  146. for ( int i = 0; i < arr.length; i++ )
  147. bt.insertTree( arr[i] );
  148. System.out.println("B-Tree of order 5:");
  149. bt.displayTree();
  150. }
  151. }
  152.  
Success #stdin #stdout 0.13s 33784KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
B-Tree of order 5:
11 12 15 18 20 21 23 25 27 29 31 33 35 36 39 42 45 47 50 55
https://ideone.com/of5o2H
language:
Java (HotSpot 12)
created:
3 years 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!