API tools faq
paste
Advertisement
Guest User

dsdsdsds

a guest
Apr 23rd, 2019
87
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 9.40 KB | None | 0 0
raw download clone embed print report
  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.Collections;
  4.  
  5. class Node {
  6. boolean leaf=true;
  7. Node parent=null;
  8. ArrayList<Integer> keys = new ArrayList<>();
  9. ArrayList<Node> sons = new ArrayList<>();
  10. public Node() {
  11.  
  12. }
  13. public Node(int key) {
  14. keys.add(key);
  15. }
  16. }
  17.  
  18.  
  19. class bTree {
  20. Node root;
  21. public int stopien;
  22. public bTree(int value,int stopien) {
  23. this.stopien = stopien;
  24. this.root = new Node(value);
  25. }
  26. public void addValue(int value){
  27. addCurr(value,root);
  28. }
  29.  
  30. public void print(){
  31. printR(root);
  32.  
  33. }
  34. public void printR(Node curr){
  35. System.out.print( curr + " klucze: ");
  36. for(int i=0;i<curr.keys.size();i++){
  37. System.out.print(curr.keys.get(i) + " ");
  38. }
  39. System.out.print(" parent= " + curr.parent + " dzieci: ");
  40. for(int i=0;i<curr.sons.size();i++){
  41. System.out.print(curr.sons.get(i) + " ");
  42. }
  43. System.out.println(" ");
  44. for(int i=0; i< curr.sons.size();i++){
  45. printR(curr.sons.get(i));
  46. }
  47. }
  48. private void fixTree(int value,Node curr){
  49. if(curr.sons.size() >0){
  50. curr.leaf = false;
  51. }
  52. if(curr.keys.size() > 2*stopien-1){
  53. if(curr.parent != null){
  54. curr.parent.keys.add(curr.keys.get(stopien-1));
  55. Node left = new Node();
  56.  
  57. curr.parent.sons.remove(curr);
  58. curr.parent.sons.add(left);
  59. left.parent = curr.parent;
  60. Node right = new Node();
  61. left.parent = curr.parent;
  62. curr.parent.sons.add(right);
  63. right.parent = curr.parent;
  64. for(int i=0;i<curr.keys.size();i++){
  65. if(i < stopien-1){
  66. left.keys.add(curr.keys.get(i));
  67. } else if (i > stopien-1){
  68. right.keys.add(curr.keys.get(i));
  69. }
  70. }
  71. for(int i=0;i<curr.sons.size();i++){
  72. if(curr.sons.get(i).keys.get(0) <= curr.keys.get(stopien-1)){
  73. left.sons.add(curr.sons.get(i));
  74. curr.sons.get(i).parent = left;
  75. }
  76. else {
  77. right.sons.add(curr.sons.get(i));
  78. curr.sons.get(i).parent = right;
  79. }
  80. }
  81. if(value <= curr.keys.get(stopien-1)){
  82. left.keys.add(value);
  83. }else{
  84. right.keys.add(value);
  85.  
  86. }
  87.  
  88.  
  89. Collections.sort(curr.parent.keys);
  90. Collections.sort(left.keys);
  91. Collections.sort(right.keys);
  92. fixTree(value,root);
  93.  
  94. } else{
  95. curr.parent = new Node(curr.keys.get(stopien-1));
  96. curr.parent.leaf = false;
  97. System.out.println("reeee");
  98. root = curr.parent;
  99. Node left = new Node();
  100. curr.parent.sons.add(left);
  101. left.parent = curr.parent;
  102. Node right = new Node();
  103. left.parent = curr.parent;
  104. curr.parent.sons.add(right);
  105. right.parent = curr.parent;
  106. for(int i=0;i<curr.keys.size();i++){
  107. if(i < stopien-1){
  108. left.keys.add(curr.keys.get(i));
  109. } else if (i > stopien-1){
  110. right.keys.add(curr.keys.get(i));
  111. }
  112. }
  113. for(int i=0;i<curr.sons.size();i++){
  114. if(curr.sons.get(i).keys.get(0) <= curr.keys.get(stopien-1)){
  115. left.sons.add(curr.sons.get(i));
  116. curr.sons.get(i).parent = left;
  117. }
  118. else {
  119. right.sons.add(curr.sons.get(i));
  120. curr.sons.get(i).parent = right;
  121. }
  122. }
  123.  
  124. Collections.sort(curr.parent.keys);
  125. Collections.sort(left.keys);
  126. Collections.sort(right.keys);
  127. fixTree(value,root);
  128. }
  129. }
  130.  
  131. else{
  132. for(int i=0;i<curr.sons.size();i++){
  133. fixTree(value,curr.sons.get(i));
  134. }
  135. }
  136. }
  137. private void addCurr(int value, Node curr){
  138. if(curr.sons.size() >0){
  139. curr.leaf = false;
  140. }
  141. if(curr.leaf){
  142. if(curr.keys.size() <= 2*stopien-2) {
  143. curr.keys.add(value);
  144. Collections.sort(curr.keys);
  145. return;
  146. } else {
  147. if(curr.keys.size() > 2*stopien-2){
  148. if(curr.parent != null){
  149. curr.parent.keys.add(curr.keys.get(stopien-1));
  150. Node left = new Node();
  151.  
  152. curr.parent.sons.remove(curr);
  153. curr.parent.sons.add(left);
  154. left.parent = curr.parent;
  155. Node right = new Node();
  156. left.parent = curr.parent;
  157. curr.parent.sons.add(right);
  158. right.parent = curr.parent;
  159. for(int i=0;i<curr.keys.size();i++){
  160. if(i < stopien-1){
  161. left.keys.add(curr.keys.get(i));
  162. } else if (i > stopien-1){
  163. right.keys.add(curr.keys.get(i));
  164. }
  165. }
  166. for(int i=0;i<curr.sons.size();i++){
  167. if(curr.sons.get(i).keys.get(0) <= curr.keys.get(stopien-1)){
  168. left.sons.add(curr.sons.get(i));
  169. curr.sons.get(i).parent = left;
  170. }
  171. else {
  172. right.sons.add(curr.sons.get(i));
  173. curr.sons.get(i).parent = right;
  174. }
  175. }
  176.  
  177. if(value <= curr.keys.get(stopien-1)){
  178. left.keys.add(value);
  179. }else{
  180. right.keys.add(value);
  181.  
  182. }
  183.  
  184.  
  185. Collections.sort(curr.parent.keys);
  186. Collections.sort(left.keys);
  187. Collections.sort(right.keys);
  188. fixTree(value,root);
  189.  
  190. } else{
  191. curr.parent = new Node(curr.keys.get(stopien-1));
  192. curr.parent.leaf = false;
  193. System.out.println("reeee");
  194. root = curr.parent;
  195. Node left = new Node();
  196. curr.parent.sons.add(left);
  197. left.parent = curr.parent;
  198. Node right = new Node();
  199. left.parent = curr.parent;
  200. curr.parent.sons.add(right);
  201. right.parent = curr.parent;
  202. for(int i=0;i<curr.keys.size();i++){
  203. if(i < stopien-1){
  204. left.keys.add(curr.keys.get(i));
  205. } else if (i > stopien-1){
  206. right.keys.add(curr.keys.get(i));
  207. }
  208. }
  209. for(int i=0;i<curr.sons.size();i++){
  210. if(curr.sons.get(i).keys.get(0) <= curr.keys.get(stopien-1)){
  211. left.sons.add(curr.sons.get(i));
  212. curr.sons.get(i).parent = left;
  213. }
  214. else {
  215. right.sons.add(curr.sons.get(i));
  216. curr.sons.get(i).parent = right;
  217. }
  218. }
  219. if(value <= curr.keys.get(stopien-1)){
  220. left.keys.add(value);
  221. }else{
  222. right.keys.add(value);
  223.  
  224. }
  225.  
  226. Collections.sort(curr.parent.keys);
  227. Collections.sort(left.keys);
  228. Collections.sort(right.keys);
  229. fixTree(value,root);
  230. }
  231. }
  232.  
  233. }
  234. }else {
  235. for(int i=0;i<curr.keys.size();i++){
  236. if(value <= curr.keys.get(i)){
  237. addCurr(value, curr.sons.get(i));
  238. break;
  239. }
  240. }
  241. addCurr(value,curr.sons.get(curr.sons.size()-1));
  242. }
  243. }}
  244.  
  245. public class Main {
  246.  
  247. public static void main(String[] args) {
  248. bTree xd = new bTree(15,4);
  249. xd.addValue(16);xd.addValue(17);xd.addValue(18);xd.addValue(19);xd.addValue(20);xd.addValue(21);xd.addValue(22);xd.addValue(23);
  250. xd.addValue(24);xd.addValue(25);xd.addValue(26);
  251.  
  252. // xd.addValue(7);
  253.  
  254.  
  255. xd.print();
  256.  
  257. }
  258. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!