프로 그래 밍 내공 수련 의 데이터 구조 - BTree (2) BTree 삽입, 조회, 삭제 작업 실현
63460 단어 데이터 구조
1 package edu.algorithms.btree;
2
3 import java.util.ArrayList;
4 import java.util.List;
5
6 /**
7 * BTree
8 *
9 * @author lingfeng
10 *
11 */
12 public class BTree {
13
14 /**BTree
15 t=2 ， 2-3-4 ， 2、3、4 **/
16 private int t = 2;
17
18 /** **/
19 private int minKeys = t-1;
20
21 /** **/
22 private int maxKeys = 2*t - 1;
23
24 /** **/
25 private BTreeNode root;
26
27 /** **/
28 public BTree(){
29 //
30 root = new BTreeNode();
31 root.setLeaf(true);
32 }
33 /** t **/
34 public BTree(int t){
35 this();
36 this.t = t;
37 minKeys = t - 1;
38 maxKeys = 2*t - 1;
39 }
40
41 /**
42 *
43 * 1. ，
44 * 2. ，
45 *
46 * **/
47 public void insertNode(Integer key){
48 if(root.size() == maxKeys){ //
49 //
50 BTreeNode tmpNode = new BTreeNode();
51 tmpNode.setLeaf(false);
52 tmpNode.getChildrens().add(root);
53 btreeSplitChild(tmpNode, 0, root);
54 root = tmpNode;
55 }
56 insertRootNotFull(root, key);
57 }
58
59 public void insertRootNotFull(BTreeNode node, int key){
60
61 //
62 if(node.isLeaf()){
63 //
64 ResultSearch result = divideSearch(node.getKeys(), key);
65 // ：
66 if(result.result == true){
67
68 }else{ // ：
69 node.insertKey(key, result.index);
70 }
71
72 }else{
73 //
74 ResultSearch result = divideSearch(node.getKeys(), key);
75 // ：
76 if(result.result == true){
77
78 }else{ // ：
79 //
80 BTreeNode childNode = node.childAt(result.index);
81 if(node.childAt(result.index).size() == (2*t - 1)){
82 btreeSplitChild(node, result.index, childNode);
83 if(key > node.keyAt(result.index)){ // key
84 childNode = node.childAt(result.index + 1);
85 }
86 }
87 insertRootNotFull(childNode, key);
88 }
89 }
90 }
91 /** (BTree )
92 *
93 * 1.
94 * 2. ， ； ，
95 * 3.
96 *
97 * **/
98 public Integer search(BTreeNode node,Integer key){
99 List<Integer> keys_tmp = node.getKeys();
100 ResultSearch result = divideSearch(keys_tmp, key);
101 if(result.result){
102 return result.index;
103 }else{
104 return search(node.childAt(result.index), key);
105 }
106 }
107 /**
108 * 、
109 *
110 * **/
111 public ResultSearch divideSearch(List<Integer> elements, int key){
112
113 int start = 0; //
114 int end = 0; //
115
116 end = elements.size() - 1;
117
118 int mid = 0;
119 while(start<=end){
120 mid = (start + end)/2;
121 if(elements.get(mid) == key){ //
122 break;
123 }else if(elements.get(mid) > key){ //
124 //
125 end = mid - 1;
126 }else if(elements.get(mid) <= key){
127 //
128 start = mid + 1;
129 }
130 }
131
132 boolean result = false;
133 Integer index = 0;
134
135 if(start<=end){ //
136 result = true;
137 index = mid;
138 }else{ // ，
139 result = false;
140 index = start;
141 }
142
143 return new ResultSearch(result,index);
144 }
145
146 /**
147 *
148 * @param parentNode
149 * @param index index
150 * @param Node
151 */
152 public void btreeSplitChild(BTreeNode parentNode, int index, BTreeNode node){
153
154 // ， [t+1 2t-1]
155 BTreeNode subNode = new BTreeNode();
156 //
157 subNode.setLeaf(node.isLeaf());
158
159 for(int i=1; i<=minKeys ; i++){
160 subNode.getKeys().add(node.keyAt(t + i -1));
161 }
162 // [t]
163 Integer key = node.keyAt(t - 1);
164 // [t 2t-1]
165 for(int i= maxKeys - 1; i>=minKeys; --i){
166 node.getKeys().remove(i);
167 }
168 if(!node.isLeaf()){ // ， ，
169
170 //subNode
171 for(int i=0 ; i<minKeys+1 ; ++i){
172 subNode.getChildrens().add(node.childAt(i+t));
173 }
174 // node
175 for(int i=maxKeys ; i>=minKeys+1; --i){
176 node.getChildrens().remove(i);
177 }
178 }else{
179
180 }
181 // [t]
182 parentNode.insertKey(key, index);
183 // index+1
184 parentNode.insertChild(subNode, index+1);
185 }
186 public void delete(Integer key){
187 delete(root, key);
188 }
189
190 public void delete(BTreeNode node, Integer key){
191 // ， t
192 assert node.size() >=t || node == root;
193
194 //
195 ResultSearch resultSearch = divideSearch(node.getKeys(), key);
196
197 //
198 if(resultSearch.result){
199
200 // ，
201 if(node.isLeaf()){
202 node.getKeys().remove(resultSearch.index.intValue());
203 }else{
204 // ， key
205 BTreeNode leftChildNode = node.childAt(resultSearch.index);
206 if(leftChildNode.size() >= t){
207
208 // leftChildNode
209 //
210 node.getKeys().remove(resultSearch.index.intValue());
211 node.insertKey(leftChildNode.keyAt(leftChildNode.size()-1), resultSearch.index);
212 delete(leftChildNode, leftChildNode.keyAt(leftChildNode.size()-1));
213 }else{
214
215 BTreeNode rightChildNode = node.childAt(resultSearch.index + 1);
216 if(rightChildNode.size() >= t){
217
218 // rightChildNode
219 node.getKeys().remove(resultSearch.index.intValue());
220 node.insertKey(rightChildNode.keyAt(0), resultSearch.index);
221 delete(rightChildNode, rightChildNode.keyAt(0));
222 }else{
223
224 // t-1
225 //
226 //1.
227 node.getKeys().remove(resultSearch.index.intValue());
228 node.getChildrens().remove(resultSearch.index.intValue() + 1);
229 //2.
230 leftChildNode.getKeys().add(key);
231 //3.
232 for(int i=0 ; i<rightChildNode.size() ; i++){
233 leftChildNode.getKeys().add(rightChildNode.getKeys().get(i));
234 }
235 // ，
236 if(!rightChildNode.isLeaf()){
237 for(int k=0 ; k<=rightChildNode.size() ; k++){
238 leftChildNode.getChildrens().add(rightChildNode.childAt(k));
239 }
240 }
241 //
242 delete(leftChildNode, key);
243
244 }
245 }
246
247 }
248
249 }else{ //
250 if(node.isLeaf()){
251 //
252 System.out.println(" ");
253 return ;
254 }
255
256 //
257 BTreeNode childNode = node.childAt(resultSearch.index);
258
259 if(root == node && node.size()==0){
260 root = childNode;
261 }
262
263 if(childNode.size() >= t){ //
264 delete(childNode, key);
265 }else{
266 // size == t
267 //
268
269 BTreeNode subNode = null;
270 int subIndex = 0;
271 //
272 if(resultSearch.index < node.size()){
273 if(node.childAt(resultSearch.index+1).size() >=t){
274 subNode = node.childAt(resultSearch.index+1);
275 subIndex = resultSearch.index + 1;
276 }
277 }
278 //
279 if(subNode == null){
280 if(resultSearch.index > 0){
281 if(node.childAt(resultSearch.index-1).size() >= t){
282 subNode = node.childAt(resultSearch.index-1);
283 subIndex = resultSearch.index - 1;
284 }
285 }
286 }
287 //
288 if(subNode != null){ // t
289 //
290 if(subIndex > resultSearch.index){ //
291
292 //
293 childNode.insertKey(node.keyAt(subIndex - 1), childNode.size());
294 node.getKeys().remove(subIndex - 1);
295 node.insertKey(subNode.keyAt(0), subIndex - 1);
296 subNode.getKeys().remove(0);
297
298 // ，
299 if(!subNode.isLeaf()){
300 childNode.getChildrens().add(subNode.getChildrens().get(0));
301 subNode.getChildrens().remove(0);
302 }
303
304 }else{ //
305
306 //
307 childNode.insertKey(node.keyAt(subIndex), 0);
308 node.getKeys().remove(subIndex);
309 node.insertKey(subNode.keyAt(subNode.size()-1), subIndex);
310 subNode.getKeys().remove(subNode.size()-1);
311
312 //
313 if(!subNode.isLeaf()){
314 childNode.insertChild(subNode.childAt(subNode.size()), 0);
315 subNode.getChildrens().remove(subNode.size()-1);
316 }
317 }
318 delete(childNode, key);
319
320 }else{
321
322 // t-1
323 //
324 if(resultSearch.index < node.size()){ //
325
326 subNode = node.childAt(resultSearch.index + 1);
327
328 //childNode.getKeys().add(node.keyAt(resultSearch.index + 1));
329 childNode.getKeys().add(node.keyAt(resultSearch.index));
330
331 node.getKeys().remove(resultSearch.index.intValue());
332 node.getChildrens().remove(resultSearch.index.intValue());
333
334 for(int i=0 ; i<subNode.size() ; i++){
335 childNode.getKeys().add(subNode.keyAt(i));
336 }
337
338 if(!subNode.isLeaf()){
339 for(int k=0 ; k<=subNode.size(); k++){
340 childNode.getChildrens().add(subNode.childAt(k));
341 }
342 }
343
344 }else{ //
345
346 subNode = node.childAt(resultSearch.index - 1);
347 childNode.insertKey(node.keyAt(resultSearch.index-1), 0);
348 node.getKeys().remove(resultSearch.index - 1);
349 node.getChildrens().remove(resultSearch.index-1);
350
351 for(int i=subNode.size()-1 ; i>=0 ; --i){
352 childNode.insertKey(subNode.keyAt(i), 0);
353 }
354
355 if(!subNode.isLeaf()){
356 for(int k=subNode.size() ; k>=0 ; --k){
357 childNode.insertChild(subNode.childAt(k),0);
358 }
359 }
360
361 }
362 if(root == node && node.size() == 0){
363 root = childNode;
364 }
365 delete(childNode, key);
366 }
367 }
368
369 }
370 }
371
372 }
373 class BTreeNode{
374
375 /** keys **/
376 private List<Integer> keys;
377
378 /** child **/
379 private List<BTreeNode> childrens;
380
381 /** **/
382 private boolean leaf;
383
384 public BTreeNode(){
385 keys = new ArrayList<Integer>();
386 childrens = new ArrayList<BTreeNode>();
387 leaf = true;
388 }
389 /**
390 * set and get methods
391 *
392 * **/
393 public List<Integer> getKeys() {
394 return keys;
395 }
396 public void setKeys(List<Integer> keys) {
397 this.keys = keys;
398 }
399 public List<BTreeNode> getChildrens() {
400 return childrens;
401 }
402 public void setChildrens(List<BTreeNode> childrens) {
403 this.childrens = childrens;
404 }
405 public boolean isLeaf() {
406 return leaf;
407 }
408 public void setLeaf(boolean leaf) {
409 this.leaf = leaf;
410 }
411
412 /**
413 *
414 * @param index
415 * @return
416 */
417 public BTreeNode childAt(int index){
418 return childrens.get(index);
419 }
420 /**
421 *
422 * @param index
423 * @return
424 */
425 public Integer keyAt(int index){
426 return keys.get(index);
427 }
428
429 /**
430 *
431 * @return
432 */
433 public int size(){
434 return keys.size();
435 }
436
437 /**
438 * key index
439 * @param key
440 * @param index
441 */
442 public void insertKey(Integer key, int index){
443 // key
444 //
445 List<Integer> newlist = new ArrayList<Integer>();
446
447 for(int i=0; i<index ; i++){
448 newlist.add(keys.get(i));
449 }
450 //
451 newlist.add(key);
452 //
453 for(int i=index ; i<keys.size() ; i++){
454 newlist.add(keys.get(i));
455 }
456 //
457 keys = newlist;
458 }
459
460 /**
461 * node index
462 * @param node
463 * @param index
464 */
465 public void insertChild(BTreeNode node, int index){
466 // child
467 List<BTreeNode> newlist = new ArrayList<BTreeNode>();
468 for(int i=0 ; i< index ; i++){
469 newlist.add(childrens.get(i));
470 }
471 newlist.add(node);
472 for(int i=index ; i<childrens.size() ; i++){
473 newlist.add(childrens.get(i));
474 }
475 childrens = newlist;
476 }
477 }
478 /**
479 *
480 * result true or false
481 * index
482 *
483 * @author lingfeng
484 */
485 class ResultSearch{
486
487 public Integer index;
488 public boolean result;
489
490 public ResultSearch(boolean rs, Integer i){
491 index = i;
492 result = rs;
493 }
494 }이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
