Löschen Sie mehrere Knoten aus einem binären Suchbaum
https://stackoverflow.com/questions/1920013
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich habe einen binären Suchbaum in C erstellt. Das Problem ist, dass ich keinen effizienten Weg finden kann, um alle Knoten mit z. B. id> 5 zu löschen.
Wenn ich den Baum durchquere, wird die Rekursion ein Fehler, da die Struktur nicht gleich ist, wenn ich einen Knoten lösche.
Gibt es eine Möglichkeit, anstatt einen helfenden Stack zu verwenden, um die Daten zu behalten, bevor sie sie vom Baum löschen?
Lösung
Hast du postorder versucht?
Löschen Sie den Knoten nach seinen Kindern.
Andere Tipps
Kostas. Sie müssen weitere Informationen geben.
Ein binärer Baum bedeutet nur einen Baum, dessen Knoten (maximal) zwei Kinder haben. Daten können auf vielen Möglichkeiten auf einem solchen Baum bestellt werden:
- Unordentlich: Es gibt keine Beziehung zwischen einem Elternteil und seinen Knoten.
- Heap: Ein Knoten ist größer als alle seine Kinder (oder kleiner als)
- Bestellt: Ein Kind ist ausgewiesen kleiner und der andere größer. Alle Werte, die kleiner als die Wurzel sind, sind auf einer Seite, alle Werte größer zur anderen.
Wenn Sie uns Code geben, können wir möglicherweise mehr helfen.
Ich werde den AVL -Baum für diesen Satuation bevorzugen.
Hier ist der Code, was Sie wollen, was Sie wollen
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;
/* */ }
/* */ }
Dies ist die vollständige Implementierung. Viel Glück.
Können Sie nicht zum Knoten navigieren und seine Kinder mit dem Elternteil des Knotens verknüpfen, damit Sie den Baum nicht brechen? Die Idee ist zu
- Finden Sie den Knoten
- Sparen Sie den Hinweis auf seine Kinder
- Sparen Sie den Hinweis auf seine Eltern
- Verknüpfen Sie Eltern mit den Kindern des Knotens (en)
- Entfernen Sie nur den Knoten (frei)
Wie es besser erklärt wird Wikipedia, Sie müssen vorsichtig sein und feststellen, wie viele Kinder es hat. Danach ist es ziemlich einfach.
Ich würde einen unbestreitigen Spaziergang machen, dies gibt Ihnen eine Auftragsliste aller Elemente. Dann bauen Sie den Baum erneut.
Oder wenn Sie dies oft tun müssen, vielleicht a Avl Baum ist besser.
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
