首页 文章

从二叉搜索树中删除多个节点

提问于
浏览
4

我有一个用C创建的二叉搜索树 . 问题是我找不到一种有效的方法来删除所有节点,例如id> 5 .

当我遍历树时,如果删除一个节点,则递归会出错,因为结构不一样 .

有什么办法,而不是使用帮助堆栈来保存数据之前从树中删除它们?

5 回答

  • 1

    你试过邮购吗?
    删除子节点后的节点 .

  • 1

    科斯塔斯 . 您需要提供更多信息 .

    二叉树仅表示其节点具有(最多)两个子节点的树 . 可以在这样的树上以多种方式订购数据:

    • 无序:父节点与其节点之间没有关系 .

    • 堆:节点大于(或小于)其所有子节点

    • 有序:一个孩子被指定为较小而另一个孩子较大 . 小于根的所有值都在一侧,所有值都大于另一侧 .

    如果您给我们代码,我们可能会提供更多帮助 .

  • 0

    我更喜欢这种饱和度的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;
    
    
    /*     */   }
    
    /*     */ }
    

    这是完全实施 . 祝你好运 .

  • 2

    您是否无法导航到节点并将其子节点与节点的父节点链接,以便您不会破坏树?这个想法是为了

    • 找到节点

    • 保存对其子项的引用

    • 保存对其父级的引用

    • 将父节点链接到节点的子节点

    • 只有删除节点(免费)

    正如在wikipedia上更好地解释的那样,你必须小心并确定它有多少个孩子 . 之后,它非常简单 .

  • 1

    我会做一个inorder walk,这会给你一个所有项目的有序列表 . 然后再次构建树 .

    或者如果你需要经常这样做,也许AVL tree更好 .

相关问题