이진 검색 트리에서 여러 노드 삭제

Question

C에서 생성 된 이진 검색 트리가 있습니다. 예를 들어 id> 5와 같이 모든 노드를 삭제하는 효율적인 방법을 찾을 수 없습니다.

구조를 동일하지 않기 때문에 트리를 탐색 할 때 노드를 삭제하면 재귀가 오류가 발생합니다.

도움말 스택을 사용하여 데이터를 트리에서 삭제하기 전에 보관하는 대신 어떤 방법이 있습니까?

Answer 1

엽서를 사용해 보셨습니까?
자식 노드 다음에 노드를 삭제하십시오.

Answer 2

나는 inorder walk를 할 것이고 이것은 모든 아이템의 주문 목록을 제공한다. 다음 나무를 다시 건설하십시오.

또는 자주 수행해야하는 경우 AVL tree이 더 좋습니다.

Answer 3

코스타스. 더 많은 정보를 제공해야합니다.

이진 트리는 노드가 (최대) 두 명의 자식이있는 트리를 의미합니다. 이러한 트리에서 데이터를 여러 가지 방법으로 정렬 할 수 있습니다.

• 정렬되지 않음 : 상위 노드와 해당 노드 사이에 관계가 없습니다.
• 힙 : 노드는보다 큰 (또는 이하)는 모든 자식은
• 는 순서가 : 어린이 1 작은 다른 큰 지정됩니다. 루트보다 작은 모든 값은 한쪽에 있으며 모든 값은 다른쪽에 커집니다.

코드를 제공하면 더 많은 도움을받을 수 있습니다.

Answer 4

이 포화를 위해 AVL 트리를 선호합니다.

여기 코드는 당신이 완전한 이행

class BSTree 
{ 


/*  */ public static final int INSERT = 1; 

/*  */ public static final int DELETE = -1; 

/*  */ BTNode root; 

/*  */ boolean AVL; 

/*  */ boolean SPL; 

/*  */ boolean RBL; 

/*  */ BTNode lastnode; 

/*  */ int nextside; 
/*  */ 

/*  */ public BSTree(int mode) 
/*  */ { 
/* 18 */  this.root = null; 

/* 19 */  setMode(mode, true); 

/*  */ } 

/*  */ 
/*  */ public void setMode(int mode, boolean state) { 

/* 23 */  switch (mode) 

/*  */  { 

/*  */  case 1: 

/* 26 */  if (state == true) 

/*  */  { 

/* 28 */   this.AVL = true; 

/* 29 */   this.SPL = false; 

/* 30 */   this.RBL = false; 

/*  */ 
/* 26 */   return; 


/*  */  } 

/*  */ 
/* 33 */  this.AVL = false; 

/* 34 */  break; 


/*  */  case 2: 

/* 37 */  if (state == true) 

/*  */  { 

/* 39 */   this.SPL = true; 

/* 40 */   this.AVL = false; 

/* 41 */   this.RBL = false; 

/*  */ 
/* 37 */   return; 

/*  */  } 
/*  */ 

/* 44 */  this.SPL = false; 

/* 45 */  break; 

/*  */  case 3: 

/* 48 */  if (state == true) 

/*  */  { 

/* 50 */   this.RBL = true; 

/* 51 */   this.AVL = false; 

/* 52 */   this.SPL = false; 

/*  */ 
/* 48 */   return; 


/*  */  } 

/*  */ 
/* 55 */  this.RBL = false; 


/* 56 */  break; 

/*  */  default: 


/* 59 */  this.AVL = false; 

/* 60 */  this.SPL = false; 

/* 61 */  this.RBL = false; 

/*  */  } 

/*  */ } 

/*  */ 
/*  */ public boolean isAVL() { 

/* 66 */  return this.AVL; 

/*  */ } 

/*  */ 
/*  */ public boolean isSPL() { 

/* 70 */  return this.SPL; 

/*  */ } 

/*  */ 
/*  */ public boolean isRBL() { 

/* 74 */  return this.RBL; 

/*  */ } 

/*  */ 
/*  */ public BTNode getRoot() 

/*  */ { 

/* 79 */  return this.root; 

/*  */ } 

/*  */ 
/*  */ public void setRoot(BTNode node) { 

/* 83 */  this.root = node; 

/*  */ } 

/*  */ 
/*  */ public boolean isEmpty() { 

/* 87 */  return (this.root == null); 

/*  */ } 

/*  */ 
/*  */ public int getDepth() 

/*  */ { 

/* 92 */  int maxdepth = 0; 

/* 93 */  for (BTNode node = this.root; node != null; node = node.nextPrO()) 

/*  */  { 

/* 95 */  int depth = node.getDepth(this.root); 


/* 96 */  if (depth > maxdepth) 

/* 97 */   maxdepth = depth; 

/*  */  } 

/* 99 */  return maxdepth; 

/*  */ } 

/*  */ 
/*  */ public void destroy(BTNode node) 

/*  */ { 

/* 104 */  node = null; 

/*  */ } 

/*  */ 
/*  */ public BTNode find(BTData data) 

/*  */ { 

/* 113 */  BTNode node = locate(data); 


/* 114 */  if (isSPL()) 



/* 115 */  splay(this.lastnode); 

/* 116 */  return node; 

/*  */ } 

/*  */ 
/*  */ public BTNode insert(BTData data) { 

/* 120 */  if (isSPL()) { 

/* 121 */  return insertSPL(data); 

/*  */  } 

/* 123 */  if (isAVL()) { 

/* 124 */  return insertAVL(data); 

/*  */  } 

/* 126 */  if (isRBL()) { 

/* 127 */  return insertRBL(data); 

/*  */  } 

/* 129 */  return insertBST(data); 

/*  */ } 

/*  */ 
/*  */ public BTNode delete(BTData data, int minmax) { 

/* 133 */  if (isAVL()) { 

/* 134 */  return deleteAVL(data, minmax); 

/*  */  } 

/* 136 */  if (isSPL()) { 

/* 137 */  return deleteSPL(data, minmax); 

/*  */  } 

/* 139 */  if (isRBL()) { 

/* 140 */  return deleteRBL(data, minmax); 

/*  */  } 

/* 142 */  return deleteBST(data, minmax); 

/*  */ } 

/*  */ 
/*  */ public BTNode locate(BTData data) 

/*  */ { 

/* 150 */  BTNode node = this.root; 

/* 151 */  BTNode next = null; 

/* 152 */  int side = 0; 
/*  */ 

/* 154 */  while (node != null) 

/*  */  { 

/* 156 */  side = node.compareSide(data); 

/* 157 */  next = node.getChild(side); 


/* 158 */  if (next == node) break; if (next == null) 
/*  */   break; 


/* 160 */  node = next; 

/*  */  } 

/* 162 */  this.lastnode = node; 

/* 163 */  this.nextside = side; 

/* 164 */  return next; 

/*  */ } 

/*  */ 
/*  */ public BTNode add(BTNode node, int side, BTData data) 

/*  */ { 

/* 170 */  BTNode newnode = new BTNode(data); 

/* 171 */  link(node, side, newnode); 

/* 172 */  return newnode; 

/*  */ } 

/*  */ 
/*  */ public BTNode remove(BTNode node) 

/*  */ { 

/* 181 */  BTNode child = node.getChild(); 

/* 182 */  BTNode parent = node.getParent(); 

/* 183 */  int side = node.getSide(); 

/* 184 */  link(parent, side, child); 

/* 185 */  destroy(node); 

/* 186 */  return parent; 

/*  */ } 

/*  */ 
/*  */ public void link(BTNode parent, int side, BTNode child) 

/*  */ { 

/* 193 */  if (child != null) 

/* 194 */  child.setParent(parent); 

/* 195 */  if (parent != null) 

/* 196 */  parent.setChild(side, child); 

/*  */  else 

/* 198 */  this.root = child; 

/*  */ } 

/*  */ 
/*  */ public BTNode rotate(BTNode node, int side) 


/*  */ { 

/* 206 */  BTNode parent = node.getParent(); 

/* 207 */  BTNode child = node.getChild(-side); 

/* 208 */  BTNode grand = child.getChild(side); 


/*  */ 
/* 210 */  link(node, -side, grand); 

/* 211 */  link(parent, node.getSide(), child); 

/* 212 */  link(child, side, node); 

/* 213 */  return child; 

/*  */ } 

/*  */ 
/*  */ public BTNode swap(BTNode node, int minmax) 

/*  */ { 

/* 222 */  BTNode swap = getSuccessor(node, minmax); 



/* 223 */  BTNode temp = node; 

/* 224 */  swapData(node, swap); 

/* 225 */  node = swap; 

/* 226 */  swap = temp; 

/* 227 */  return node; 

/*  */ } 

/*  */ 
/*  */ public BTNode getSuccessor(BTNode node, int minmax) { 

/* 231 */  return ((minmax == 1) ? node.prevInO() : node.nextInO()); 

/*  */ } 

/*  */ 
/*  */ public void swapData(BTNode node1, BTNode node2) 

/*  */ { 
/* 237 */  BTData data = node1.getData(); 

/* 238 */  node1.setData(node2.getData()); 

/* 239 */  node2.setData(data); 

/*  */ } 

/*  */ 
/*  */ public void deleteAll() 

/*  */ { 

/* 245 */  for (BTNode node = this.root.firstPoO(); node != null;) 

/*  */  { 
/* 247 */  BTNode leaf = node; 

/* 248 */  node = leaf.nextPoO(); 

/* 249 */  destroy(leaf); 

/*  */  } 

/* 251 */  this.root = null; 

/*  */ } 

/*  */ 
/*  */ public BTNode locateBST(BTData data) 

/*  */ { 

/* 260 */  for (BTNode node = this.root; node != null;) 

/*  */  { 
/* 262 */  int side = node.compareSide(data); 


/* 263 */  if (side == 0) 
/*  */   break; 

/* 265 */  node = node.getChild(side); 

/*  */  } 

/* 267 */  return node; 

/*  */ } 
/*  */ 
/*  */ public BTNode insertBST(BTData data) 

/*  */ { 

/* 272 */  if (this.root == null) 

/* 273 */  return add(null, 0, data); 




/* 274 */  BTNode node = locate(data); 



/* 275 */  return ((node != null) ? null : add(this.lastnode, this.nextside, data)); 



/*  */ } 



/*  */ 

/*  */ public BTNode deleteBST(BTData data, int minmax) 


/*  */ { 





/* 280 */  BTNode node = locate(data); 



/* 281 */  if (node == null) 

/* 282 */  return null; 

/* 283 */  if (node.hasTwoChildren()) 

/* 284 */  node = swap(node, minmax); 

/* 285 */  return remove(node); 

/*  */ } 

/*  */ 

/*  */ public BTNode insertAVL(BTData data) 

/*  */ { 

/* 297 */  if (this.root == null) 

/* 298 */  return add(null, 0, data); 

/* 299 */  if (locate(data) != null) 


/* 300 */  return null; 

/* 301 */  BTNode node = add(this.lastnode, this.nextside, data); 

/* 302 */  rebalanceAVL(this.lastnode, this.nextside, 1); 

/* 303 */  return node; 

/*  */ } 

/*  */ 


/*  */ public BTNode deleteAVL(BTData data, int minmax) 

/*  */ { 

/* 315 */  BTNode node = locate(data); 

/* 316 */  if (node == null) { 

/* 317 */  return null; 

/*  */  } 


/* 319 */  if (node.hasTwoChildren()) { 

/* 320 */  node = swap(node, minmax); 


/*  */  } 

/* 322 */  int side = node.getSide(); 

/* 323 */  node = remove(node); 

/* 324 */  rebalanceAVL(node, side, -1); 


/* 325 */  return node; 

/*  */ } 

/*  */ 

/*  */ public void rebalanceAVL(BTNode node, int side, int in) 

/*  */ { 

/* 333 */  for (; node != null; node = node.getParent()) 

/*  */  { 

/* 335 */  if (node.getBalance() != in * side) 

/* 336 */   node.setBalance(node.getBalance() + in * side); 

/*  */  else { 

/* 338 */   node = rotateAVL(node); 

/*  */  } 

/* 340 */  if ((in == 1) && (node.getBalance() == 0)) return; if ((in == -1) && 

(node.getBalance() != 0)) 

/*  */   return; 

/* 342 */  side = node.getSide(); 


/*  */  } 

/*  */ } 


/*  */ 

/*  */ public BTNode rotateAVL(BTNode node) 


/*  */ { 

/* 357 */  int side = node.getBalance(); 

/* 358 */  BTNode child = node.getChild(side); 

/*  */ 

/* 360 */  if (child.getBalance() == -side) 

/*  */  { 

/* 362 */  BTNode grand = child.getChild(-side); 

/* 363 */  if (grand.getBalance() == -side) 

/*  */  { 

/* 365 */   grand.setBalance(0); 

/* 366 */   child.setBalance(side); 

/* 367 */   node.setBalance(0); 

/*  */  } 

/* 369 */  else if (grand.getBalance() == side) 

/*  */  { 

/* 371 */   grand.setBalance(0); 

/* 372 */   child.setBalance(0); 

/* 373 */   node.setBalance(-side); 

/*  */  } 

/*  */  else { 

/* 376 */   node.setBalance(0); 

/* 377 */   child.setBalance(0); 

/*  */  } 

/* 379 */  rotate(child, side); 

/*  */  } 

/* 382 */  else if (child.getBalance() == side) 

/*  */  { 

/* 384 */  node.setBalance(0); 

/* 385 */  child.setBalance(0); 

/*  */  } 

/* 387 */  else if (child.getBalance() == 0) 

/*  */  { 

/* 389 */  node.setBalance(side); 

/* 390 */  child.setBalance(-side); 

/*  */  } 

/* 392 */  node = rotate(node, -side); 

/* 393 */  return node; 

/*  */ } 

/*  */ 

/*  */ public void balanceAVL(BTNode node) 

/*  */ { 

/* 400 */  int side = node.getBalance(); 

/* 401 */  BTNode child = node.getChild(side); 

/* 402 */  if (child.getBalance() == -side) 

/*  */  { 


/* 404 */  BTNode grand = child.getChild(-side); 

/* 405 */  if (grand.getBalance() == -side) 

/*  */  { 

/* 407 */   grand.setBalance(0); 

/* 408 */   child.setBalance(side); 

/* 409 */   node.setBalance(0); 



/*  */  } 

/* 411 */  else if (grand.getBalance() == side) 

/*  */  { 

/* 413 */   grand.setBalance(0); 

/* 414 */   child.setBalance(0); 

/* 415 */   node.setBalance(-side); 

/*  */  } 

/*  */  else { 

/* 418 */   node.setBalance(0); 

/* 419 */   child.setBalance(0); 

/*  */  } 

/*  */ 

/*  */  } 

/* 423 */  else if (child.getBalance() == side) 

/*  */  { 





/* 425 */  child.setBalance(0); 

/* 426 */  node.setBalance(0); 

/*  */  } else { 

/* 428 */  if (child.getBalance() != 0) 

/*  */   return; 

/* 430 */  child.setBalance(-side); 

/*  */  } 

/*  */ } 

/*  */ 

/*  */ public boolean isAVLcompliant(BTNode node) 

/*  */ { 

/* 440 */  boolean balanced = true; 

/*  */ 

/* 442 */  if (node == null) 

/* 443 */  return true; 

/* 444 */  int l = getHeight(node.getChild(-1), 0); 

/* 445 */  int r = getHeight(node.getChild(1), 0); 


/* 446 */  node.setBalance(r - l); 


/* 447 */  if ((r - l > 1) || (r - l < -1)) 


/* 448 */  balanced = false; 


/* 449 */  return ((balanced) && (isAVLcompliant(node.getChild(-1))) && (isAVLcompliant 

(node.getChild(1)))); 

/*  */ } 

/*  */ 

/*  */ public int getHeight(BTNode node, int depth) 

/*  */ { 

/* 454 */  if (node == null) 

/* 455 */  return 0; 

/* 456 */  if (node.isLeaf()) { 

/* 457 */  return (depth + 1); 

/*  */  } 

/*  */ 

/* 460 */  int lmax = getHeight(node.getChild(-1), depth + 1); 

/* 461 */  int rmax = getHeight(node.getChild(1), depth + 1); 

/* 462 */  return ((lmax > rmax) ? lmax : rmax); 

/*  */ } 

/*  */ 

/*  */ public BTNode insertSPL(BTData data) 

/*  */ { 

/* 474 */  if (this.root == null) 

/* 475 */  return add(null, 0, data); 

/* 476 */  BTNode node = locate(data); 


/* 477 */  splay(this.lastnode); 

/* 478 */  return ((node != null) ? null : splitinsert(data)); 

/*  */ } 


/*  */ 

/*  */ public BTNode splitinsert(BTData data) 

/*  */ { 

/* 483 */  BTNode node = new BTNode(data); 

/* 484 */  int side = -this.root.compareSide(data); 

/* 485 */  BTNode child = this.root.getChild(-side); 

/*  */ 

/* 487 */  this.root.setChild(-side, null); 

/* 488 */  link(node, side, this.root); 

/* 489 */  link(node, -side, child); 

/* 490 */  this.root = node; 

/* 491 */  return this.root; 

/*  */ } 

/*  */ 

/*  */ public BTNode deleteSPL(BTData data, int minmax) 

/*  */ { 

/* 498 */  BTNode node = locate(data); 

/* 499 */  splay(this.lastnode); 

/* 500 */  if (node == null) 

/* 501 */  return null; 

/* 502 */  BTNode root = node; 

/* 503 */  node = getSuccessor(root, minmax); 

/* 504 */  if (node != null) 

/* 505 */  splay(node); 

/* 506 */  return remove(root); 

/*  */ } 

/*  */ 

/*  */ public void splay(BTNode node) 

/*  */ { 

/* 516 */  while (node != this.root) 


/*  */  { 

/* 518 */  BTNode parent = node.getParent(); 


/* 519 */  BTNode grandparent = parent.getParent(); 

/* 520 */  int side = node.getSide(); 

/* 521 */  if (grandparent == null) { 

/* 522 */   rotate(parent, -side); 

/*  */  } 

/* 524 */  else if (parent.getSide() == side) 

/*  */  { 

/* 526 */   rotate(grandparent, -side); 

/* 527 */   rotate(parent, -side); 

/*  */  } 

/*  */  else { 

/* 530 */   if (parent.getSide() == side) 

/*  */   continue; 

/* 532 */   rotate(parent, -side); 

/* 533 */   rotate(grandparent, side); 

/*  */  } 

/*  */  } 

/*  */ } 

/*  */ 

/*  */ public boolean isSPLcompliant() 

/*  */ { 



/* 541 */  return true; 

/*  */ } 


/*  */ 

/*  */ public BTNode insertRBL(BTData data) 

/*  */ { 

/* 552 */  if (this.root == null) 

/*  */  { 

/* 554 */  this.root = add(null, 0, data); 

/* 555 */  this.root.setColor(2); 

/* 556 */  return this.root; 

/*  */  } 

/* 558 */  if (locate(data) != null) 

/* 559 */  return null; 

/* 560 */  BTNode node = add(this.lastnode, this.nextside, data); 

/* 561 */  node.setColor(1); 

/* 562 */  fixRBinsert(node); 

/* 563 */  return node; 

/*  */ } 

/*  */ 

/*  */ public void fixRBinsert(BTNode node) 

/*  */ { 

/* 571 */  while (node != this.root) 
/*  */  { 

/* 573 */  BTNode parent = node.getParent(); 

/* 574 */  if (parent.getColor() == 2) 

/*  */   break; 

/* 576 */  BTNode grandparent = parent.getParent(); 

/* 577 */  int side = parent.getSide(); 

/* 578 */  BTNode uncle = grandparent.getChild(-side); 

/* 579 */  if ((uncle != null) && (uncle.getColor() == 1)) 

/*  */  { 

/* 581 */   parent.setColor(2); 

/* 582 */   uncle.setColor(2); 

/* 583 */   grandparent.setColor(1); 

/* 584 */   node = grandparent; 

/*  */  } 

/* 586 */  else if (node.getSide() == -side) 

/*  */  { 

/* 588 */   rotate(parent, side); 

/* 589 */   node = parent; 

/*  */  } else { 

/* 591 */   if (node.getSide() != side) 

/*  */   continue; 

/* 593 */   parent.setColor(2); 

/* 594 */   grandparent.setColor(1); 

/* 595 */   rotate(grandparent, -side); 

/*  */  } 

/*  */  } 

/* 598 */  this.root.setColor(2); 


/*  */ } 

/*  */ 

/*  */ public BTNode deleteRBL(BTData data, int minmax) 

/*  */ { 

/* 606 */  BTNode node = locate(data); 

/* 607 */  if (node == null) { 

/* 608 */  return null; 

/*  */  } 

/* 610 */  if (node.hasTwoChildren()) { 

/* 611 */  node = swap(node, minmax); 

/*  */  } 

/* 613 */  int color = node.getColor(); 

/* 614 */  int side = node.getSide(); 

/* 615 */  node = remove(node); 

/* 616 */  if ((this.root != null) && (side == 0)) { 

/* 617 */  this.root.setColor(2); 

/*  */  } 

/* 619 */  else if ((node != null) && (color == 2)) 

/* 620 */  fixRBdelete(node, side); 

/* 621 */  return node; 

/*  */ } 

/*  */ 

/*  */ public void fixRBdelete(BTNode parent, int side) 

/*  */ { 

/* 629 */  BTNode node = parent.getChild(side); 

/* 630 */  if ((node != null) && (node.getColor() == 1)) 

/*  */  { 


/* 632 */  node.setColor(2); 

/* 633 */  return; 

/*  */  } 

/*  */ 

/*  */  do 

/*  */  { 

/* 638 */  if (node != null) 



/*  */  { 

/* 640 */   parent = node.getParent(); 

/* 641 */   side = node.getSide(); 

/*  */  } 

/* 643 */  BTNode sibling = parent.getChild(-side); 

/* 644 */  BTNode nephew = sibling.getChild(side); 

/* 645 */  BTNode niece = sibling.getChild(-side); 

/*  */ 

/* 647 */  if (sibling.getColor() == 1) 

/*  */  { 

/* 649 */   sibling.setColor(2); 

/* 650 */   parent.setColor(1); 

/* 651 */   rotate(parent, side); 

/*  */  } 

/* 654 */  else if ((isBlack(nephew)) && (isBlack(niece))) 

/*  */  { 

/* 656 */   sibling.setColor(1); 

/* 657 */   node = (node == null) ? parent : node.getParent(); 

/*  */  } 


/* 660 */  else if ((isBlack(niece)) && (isRed(nephew))) 



/*  */  { 

/* 662 */   sibling.setColor(1); 

/* 663 */   nephew.setColor(2); 

/* 664 */   rotate(sibling, -side); 

/*  */  } 

/*  */  else { 

/* 667 */   if (!(isRed(niece))) 

/*  */   continue; 

/* 669 */   sibling.setColor(parent.getColor()); 



/* 670 */   parent.setColor(2) 
; 
/* 671 */   niece.setColor(2); 
/* 672 */ 
     rotate(parent, side); 
/* 673 */ 
     node = this.root; 
/*  */ 
     } 
/*  */ 
    } 
/* 636 */ 
    while ((node != this.root) && (isBlack(node))); 
/*  */ 
/* 676 */  node.setColor(2); 

/*  */ } 

/*  */ 

/*  */ public boolean isRed(BTNode node) 

/*  */ { 



/* 681 */ 


    return ((node != null) && (node.getColor() == 1)); 
/*  */ 
    } 
/*  */ 


/*  */ public boolean isBlack(BTNode node) { 

/* 685 */ 

    return ((node == null) || (node.getColor() == 2)); 
/*  */ 
    } 
/*  */ 

/*  */ public boolean isRBLcompliant(BTNode node) 

/*  */ { 

/* 690 */  return false; 


/*  */ } 

/*  */ } 

입니다 원하는 걸릴. 행운을 빌어 요.

Answer 5

노드를 탐색하여 노드의 부모와 자식을 연결하여 트리를 손상시키지 못합니까? 아이디어는

• 하려면 (노드를 자식 노드의 아이 (들)
• 는 다음 노드를 제거하는 부모를 참조하여 저장
• 링크 부모를 참조 저장
• 을 찾을 수 있습니다 무료)

wikipedia에서 더 잘 설명되어 있으므로주의해야하며 자녀 수를 결정해야합니다. 그 후에는 꽤 간단합니다.