data_structures: d359966ed8de src/rbtree.c

view src/rbtree.c @ 12:d359966ed8de

Added trie

author	Eris Caffee <discordia@eldalin.com>
date	Mon, 01 Oct 2012 15:50:30 -0500
parents	68f85ffc6029
children

line source

1 #include <stdio.h>

2 #include <stdlib.h>

3 #include <math.h>

5 #include "rbtree.h"

6 #include "queue.h"

8 enum rbtree_color { RED, BLACK };

10 struct rbtree_node

11 {

12 enum rbtree_color color;

13 struct rbtree_node * parent;

14 struct rbtree_node * left;

15 struct rbtree_node * right;

16 void * data;

17 };

19 struct rbtree

20 {

21 struct rbtree_node nil_node;

22 struct rbtree_node * nil;

23 struct rbtree_node * root;

24 size_t size;

25 bool (*le)(void * a, void * b);

26 bool (*eq)(void * a, void * b);

27 };

29 struct rbtree_iterator

30 {

31 struct rbtree * rbtree;

32 struct rbtree_node * curr;

33 };

35 void * rbtree_data_search (struct rbtree * rbtree, struct rbtree_node * node, void * data);

36 void * rbtree_node_minimum (struct rbtree * rbtree, struct rbtree_node * node);

37 void * rbtree_node_maximum (struct rbtree * rbtree, struct rbtree_node * node);

39 void rbtree_data_walk_inorder (struct rbtree * rbtree, struct rbtree_node * node, void (*op)(void * data));

40 void rbtree_data_walk_preorder (struct rbtree * rbtree, struct rbtree_node * node, void (*op)(void * data));

41 void rbtree_data_walk_postorder (struct rbtree * rbtree, struct rbtree_node * node, void (*op)(void * data));

42 void rbtree_node_walk_postorder (struct rbtree * rbtree, struct rbtree_node * node, void (*op)(struct rbtree_node * n));

44 void rbtree_node_free (struct rbtree_node * node);

46 struct rbtree_node * rbtree_node_search (struct rbtree * rbtree, struct rbtree_node * node, void * data);

48 struct rbtree_node * rbtree_transplant (struct rbtree * rbtree, struct rbtree_node * a, struct rbtree_node * b);

49 void rbtree_rotate_left (struct rbtree * rbtree, struct rbtree_node * node);

50 void rbtree_rotate_right (struct rbtree * rbtree, struct rbtree_node * node);

51 void rbtree_insert_fixup (struct rbtree * rbtree, struct rbtree_node * node);

52 void rbtree_remove_fixup (struct rbtree * rbtree, struct rbtree_node * node);

54 void rbtree_node_dump_preorder(struct rbtree * rbtree, struct rbtree_node * node, void (*print_val)(void *), int depth);

56 ////////////////////////////////////////////////////////////////////////////////

57 struct rbtree *

58 rbtree_new(bool (*le)(void * a, void * b),

59 bool (*eq)(void * a, void * b))

60 {

61 if ( (NULL == le) || (NULL == eq) )

62 return NULL;

64 struct rbtree * rbtree = malloc(sizeof(struct rbtree));

65 if (NULL == rbtree)

66 return NULL;

68 rbtree->nil_node = (struct rbtree_node) { BLACK, &rbtree->nil_node, &rbtree->nil_node, &rbtree->nil_node, NULL };

69 rbtree->nil = &(rbtree->nil_node);

70 rbtree->root = rbtree->nil;

71 rbtree->size = 0;

72 rbtree->le = le;

73 rbtree->eq = eq;

74 return rbtree;

75 }

78 ////////////////////////////////////////////////////////////////////////////////

79 void

80 rbtree_delete(struct rbtree * rbtree)

81 {

82 if (NULL == rbtree) return;

83 if (0 < rbtree->size)

84 {

85 // Walk the tree and delete the nodes.

86 // This may cause memory leaks, so hopefully the user has already

87 // emptied the tree.

88 rbtree_node_walk_postorder(rbtree, rbtree->root, rbtree_node_free);

89 }

90 free(rbtree);

91 }

93 ////////////////////////////////////////////////////////////////////////////////

94 void

95 rbtree_node_free(struct rbtree_node * node)

96 {

97 free(node);

98 }

100 ////////////////////////////////////////////////////////////////////////////////

101 void *

102 rbtree_insert(struct rbtree * rbtree, void * data)

103 {

104 if ( (NULL == rbtree) || (NULL == data) )

105 return NULL;

106

107 struct rbtree_node * new = malloc(sizeof(struct rbtree_node));

108 if (NULL == new)

109 return NULL;

110 new->left = new->right = new->parent = rbtree->nil;

111 new->color = RED;

112 new->data = data;

113

114 if (rbtree->nil == rbtree->root)

115 {

116 rbtree->root = new;

117 new->color = BLACK;

118 new->parent = rbtree->nil;

119 rbtree->size = 1;

120 return new->data;

121 }

122

123 struct rbtree_node * p = rbtree->nil;

124 struct rbtree_node * c = rbtree->root;

125

126 while (rbtree->nil != c)

127 {

128 p = c;

129 if (rbtree->le(new->data, c->data))

130 c = c->left;

131 else

132 c = c->right;

133 }

134 new->parent = p;

135 if (rbtree->le(new->data, p->data))

136 p->left = new;

137 else

138 p->right = new;

139

140 rbtree_insert_fixup(rbtree, new);

141

142 rbtree->size++;

143 return new->data;

144 }

145

146 ////////////////////////////////////////////////////////////////////////////////

147 void

148 rbtree_insert_fixup(struct rbtree * rbtree, struct rbtree_node * node)

149 {

150 if ( (NULL == rbtree) || (NULL == node) )

151 return;

152

153 while (RED == node->parent->color)

154 {

155 if (node->parent == node->parent->parent->left)

156 {

157 struct rbtree_node * y = node->parent->parent->right;

158 if (RED == y->color)

159 {

160 node->parent->color = BLACK;

161 y->color = BLACK;

162 node->parent->parent->color = RED;

163 node = node->parent->parent;

164 }

165 else

166 {

167 if (node == node->parent->right)

168 {

169 node = node->parent;

170 rbtree_rotate_left(rbtree, node);

171 }

172 node->parent->color = BLACK;

173 node->parent->parent->color = RED;

174 rbtree_rotate_right(rbtree, node->parent->parent);

175 }

176 }

177 else

178 {

179 struct rbtree_node * y = node->parent->parent->left;

180 if (RED == y->color)

181 {

182 node->parent->color = BLACK;

183 y->color = BLACK;

184 node->parent->parent->color = RED;

185 node = node->parent->parent;

186 }

187 else

188 {

189 if (node == node->parent->left)

190 {

191 node = node->parent;

192 rbtree_rotate_right(rbtree, node);

193 }

194 node->parent->color = BLACK;

195 node->parent->parent->color = RED;

196 rbtree_rotate_left(rbtree, node->parent->parent);

197 }

198 }

199 }

200 rbtree->root->color = BLACK;

201 }

202

203 ////////////////////////////////////////////////////////////////////////////////

204 void

205 rbtree_walk_inorder(struct rbtree * rbtree, void (*op)(void * data))

206 {

207 if ( (NULL == rbtree) || (rbtree->nil == rbtree->root) || (NULL == op) )

208 return;

209

210 rbtree_data_walk_inorder(rbtree, rbtree->root, op);

211 }

212

213 ////////////////////////////////////////////////////////////////////////////////

214 void

215 rbtree_walk_postorder(struct rbtree * rbtree, void (*op)(void * data))

216 {

217 if ( (NULL == rbtree) || (rbtree->nil == rbtree->root) || (NULL == op) )

218 return;

219

220 rbtree_data_walk_postorder(rbtree, rbtree->root, op);

221 }

222

223 ////////////////////////////////////////////////////////////////////////////////

224 void

225 rbtree_walk_preorder(struct rbtree * rbtree, void (*op)(void * data))

226 {

227 if ( (NULL == rbtree) || (rbtree->nil == rbtree->root) || (NULL == op) )

228 return;

229

230 rbtree_data_walk_preorder(rbtree, rbtree->root, op);

231 }

232

233 ////////////////////////////////////////////////////////////////////////////////

234 void

235 rbtree_data_walk_inorder(struct rbtree * rbtree, struct rbtree_node * node, void (*op)(void * data))

236 {

237 if (rbtree->nil != node)

238 {

239 rbtree_data_walk_inorder(rbtree, node->left, op);

240 op(node->data);

241 rbtree_data_walk_inorder(rbtree, node->right, op);

242 }

243 }

244

245 ////////////////////////////////////////////////////////////////////////////////

246 void

247 rbtree_data_walk_postorder(struct rbtree * rbtree, struct rbtree_node * node, void (*op)(void * data))

248 {

249 if (rbtree->nil != node)

250 {

251 rbtree_data_walk_postorder(rbtree, node->left, op);

252 rbtree_data_walk_postorder(rbtree, node->right, op);

253 op(node->data);

254 }

255 }

256

257 ////////////////////////////////////////////////////////////////////////////////

258 void

259 rbtree_data_walk_preorder(struct rbtree * rbtree, struct rbtree_node * node, void (*op)(void * data))

260 {

261 if (rbtree->nil != node)

262 {

263 op(node->data);

264 rbtree_data_walk_preorder(rbtree, node->left, op);

265 rbtree_data_walk_preorder(rbtree, node->right, op);

266 }

267 }

268

269 ////////////////////////////////////////////////////////////////////////////////

270 void

271 rbtree_node_walk_postorder(struct rbtree * rbtree, struct rbtree_node * node, void (*op)(struct rbtree_node * n))

272 {

273 if (rbtree->nil != node)

274 {

275 rbtree_node_walk_postorder(rbtree, node->left, op);

276 rbtree_node_walk_postorder(rbtree, node->right, op);

277 op(node);

278 }

279 }

280

281 ////////////////////////////////////////////////////////////////////////////////

282 void *

283 rbtree_search(struct rbtree * rbtree, void * data)

284 {

285 if ( (NULL == rbtree) || (rbtree->nil == rbtree->root) || (NULL == data) )

286 return NULL;

287

288 return rbtree_data_search(rbtree, rbtree->root, data);

289 }

290

291 ////////////////////////////////////////////////////////////////////////////////

292 // Recursive

293 void *

294 rbtree_data_search(struct rbtree * rbtree, struct rbtree_node * node, void * data)

295 {

296 if (rbtree->nil == node)

297 return NULL;

298

299 if (rbtree->eq(data, node->data))

300 return node->data;

301

302 if (rbtree->le(data, node->data))

303 return rbtree_data_search(rbtree, node->left, data);

304 else

305 return rbtree_data_search(rbtree, node->right, data);

306 }

307

308 ////////////////////////////////////////////////////////////////////////////////

309 // Iterative

310 void *

311 rbtree_search_iterative(struct rbtree * rbtree, void * data)

312 {

313 if ( (NULL == rbtree) || (rbtree->nil == rbtree->root) || (NULL == data) )

314 return NULL;

315

316 struct rbtree_node * node = rbtree->root;

317 while (1)

318 {

319 if (rbtree->nil == node)

320 return NULL;

321

322 if (rbtree->eq(data, node->data))

323 return node->data;

324

325 if (rbtree->le(data, node->data))

326 node = node->left;

327 else

328 node = node->right;

329 }

330 }

331

332 ////////////////////////////////////////////////////////////////////////////////

333 void *

334 rbtree_minimum(struct rbtree * rbtree)

335 {

336 if (NULL == rbtree)

337 return NULL;

338

339 return rbtree_node_minimum(rbtree, rbtree->root);

340 }

341

342 ////////////////////////////////////////////////////////////////////////////////

343 void *

344 rbtree_node_minimum(struct rbtree * rbtree, struct rbtree_node * node)

345 {

346 while ( (rbtree->nil != node) && (rbtree->nil != node->left) )

347 node = node->left;

348 if (rbtree->nil == node)

349 return NULL;

350 return node->data;

351 }

352

353 ////////////////////////////////////////////////////////////////////////////////

354 void *

355 rbtree_maximum(struct rbtree * rbtree)

356 {

357 if (NULL == rbtree)

358 return NULL;

359

360 return rbtree_node_maximum(rbtree, rbtree->root);

361 }

362

363 ////////////////////////////////////////////////////////////////////////////////

364 void *

365 rbtree_node_maximum(struct rbtree * rbtree, struct rbtree_node * node)

366 {

367 while ( (rbtree->nil != node) && (rbtree->nil != node->right) )

368 node = node->right;

369 if (rbtree->nil == node)

370 return NULL;

371 return node->data;

372 }

373

374 ////////////////////////////////////////////////////////////////////////////////

375 struct rbtree_iterator *

376 rbtree_begin(struct rbtree * rbtree)

377 {

378 if ( (NULL == rbtree) || (rbtree->nil == rbtree->root) )

379 return NULL;

380

381 struct rbtree_node * min = rbtree->root;

382 while (rbtree->nil != min->left)

383 min = min->left;

384

385 struct rbtree_iterator * it = malloc(sizeof(struct rbtree_iterator));

386 if (NULL == it)

387 return NULL;

388

389 it->rbtree = rbtree;

390 it->curr = min;

391 return it;

392 }

393

394 ////////////////////////////////////////////////////////////////////////////////

395 struct rbtree_iterator *

396 rbtree_end(struct rbtree * rbtree)

397 {

398 if ( (NULL == rbtree) || (rbtree->nil == rbtree->root) )

399 return NULL;

400

401 struct rbtree_node * max = rbtree->root;

402 while (rbtree->nil != max->right)

403 max = max->right;

404

405 struct rbtree_iterator * it = malloc(sizeof(struct rbtree_iterator));

406 if (NULL == it)

407 return NULL;

408

409 it->rbtree = rbtree;

410 it->curr = max;

411 return it;

412 }

413

414 ////////////////////////////////////////////////////////////////////////////////

415 struct rbtree_iterator *

416 rbtree_next(struct rbtree_iterator * it)

417 {

418 if ( (NULL == it) || (NULL == it->rbtree) || (it->rbtree->nil == it->curr) )

419 return NULL;

420

421 if (it->rbtree->nil == it->curr->right)

422 {

423 struct rbtree_node * p = it->curr;

424 it->curr = it->curr->parent;

425 while ( (it->rbtree->nil != it->curr) && (p == it->curr->right) )

426 {

427 p = it->curr;

428 it->curr = it->curr->parent;

429 }

430

431 if (it->curr == it->rbtree->nil)

432 return NULL;

433 }

434 else

435 {

436 struct rbtree_node * min = it->curr->right;

437 while (it->rbtree->nil != min->left)

438 min = min->left;

439 it->curr = min;

440 }

441 return it;

442 }

443

444 ////////////////////////////////////////////////////////////////////////////////

445 struct rbtree_iterator *

446 rbtree_prev(struct rbtree_iterator * it)

447 {

448 if ( (NULL == it) || (NULL == it->rbtree) || (it->rbtree->nil == it->curr) )

449 return NULL;

450

451 if (it->rbtree->nil == it->curr->left)

452 {

453 struct rbtree_node * p = it->curr;

454 it->curr = it->curr->parent;

455 while ( (it->rbtree->nil != it->curr) && (p == it->curr->left) )

456 {

457 p = it->curr;

458 it->curr = it->curr->parent;

459 }

460

461 if (it->curr == it->rbtree->nil)

462 return NULL;

463 }

464 else

465 {

466 struct rbtree_node * max = it->curr->left;

467 while (it->rbtree->nil != max->right)

468 max = max->right;

469 it->curr = max;

470 }

471 return it;

472 }

473

474 ////////////////////////////////////////////////////////////////////////////////

475 void *

476 rbtree_value(struct rbtree_iterator * it)

477 {

478 if ( (NULL == it) || (NULL == it->rbtree) || (it->rbtree->nil == it->curr) )

479 return NULL;

480

481 return it->curr->data;

482 }

483

484 ////////////////////////////////////////////////////////////////////////////////

485 void *

486 rbtree_find(struct rbtree_iterator * it, void * data)

487 {

488 if ( (NULL == it) || (NULL == it->rbtree) || (it->rbtree->nil == it->rbtree->root) || (NULL == data) )

489 return NULL;

490

491 return rbtree_node_search(it->rbtree, it->rbtree->root, data);

492 }

493

494 ////////////////////////////////////////////////////////////////////////////////

495 // Recursive

496 struct rbtree_node *

497 rbtree_node_search(struct rbtree * rbtree, struct rbtree_node * node, void * data)

498 {

499 if (rbtree->nil == node)

500 return NULL;

501

502 if (rbtree->eq(data, node->data))

503 return node;

504

505 if (rbtree->le(data, node->data))

506 return rbtree_node_search(rbtree, node->left, data);

507 else

508 return rbtree_node_search(rbtree, node->right, data);

509 }

510

511 ////////////////////////////////////////////////////////////////////////////////

512 struct rbtree_node *

513 rbtree_transplant(struct rbtree * rbtree, struct rbtree_node * a, struct rbtree_node * b)

514 {

515 if ( (NULL == a) || (NULL == b) )

516 return NULL;

517

518 if (rbtree->nil == a->parent)

519 rbtree->root = b;

520 else if (a == a->parent->left)

521 a->parent->left = b;

522 else

523 a->parent->right = b;

524

525 b->parent = a->parent;

526

527 return a;

528 }

529

530 ////////////////////////////////////////////////////////////////////////////////

531 void *

532 rbtree_remove(struct rbtree_iterator * it)

533 {

534 if ( (NULL == it) || (NULL == it->rbtree) || (it->rbtree->nil == it->curr) )

535 return NULL;

536

537 // Get successor and save it

538 struct rbtree_iterator succ;

539 succ.curr = it->curr;

540 succ.rbtree = it->rbtree;

541 rbtree_next(&succ);

542

543 struct rbtree_node * x;

544 struct rbtree_node * y = it->curr;

545 enum rbtree_color original_color = y->color;

546

547 if (it->rbtree->nil == it->curr->left)

548 {

549 x = it->curr->right;

550 rbtree_transplant(it->rbtree, it->curr, it->curr->right);

551 }

552 else if (it->rbtree->nil == it->curr->right)

553 {

554 x = it->curr->left;

555 rbtree_transplant(it->rbtree, it->curr, it->curr->left);

556 }

557 else

558 {

559 y = rbtree_node_minimum(it->rbtree, it->curr->right);

560 original_color = y->color;

561 x = y->right;

562 if (it->curr == y->parent)

563 x->parent = y;

564 else

565 {

566 rbtree_transplant(it->rbtree, y, y->right);

567 y->right = it->curr->right;

568 y->right->parent = y;

569 }

570 rbtree_transplant(it->rbtree, it->curr, y);

571 y->left = it->curr->left;

572 y->left->parent = y;

573 y->color = it->curr->color;

574 }

575

576 if (BLACK == original_color)

577 rbtree_remove_fixup(it->rbtree, x);

578

579 void * data = it->curr->data;

580 free(it->curr);

581

582 // Update it to point to saved successor

583 it->curr = succ.curr;

584 it->rbtree->size--;

585

586 return data;

587 }

588

589 ////////////////////////////////////////////////////////////////////////////////

590 void

591 rbtree_remove_fixup(struct rbtree * rbtree, struct rbtree_node * node)

592 {

593 while ( (rbtree->root != node) && (BLACK == node->color) )

594 {

595 if (node == node->parent->left)

596 {

597 struct rbtree_node * w = node->parent->right;

598 if (RED == w->color)

599 {

600 w->color = BLACK;

601 node->parent->color = RED;

602 rbtree_rotate_left(rbtree, node->parent);

603 w = node->parent->right;

604 }

605 if ( (BLACK == w->left->color) && (BLACK == w->right->color) )

606 {

607 w->left->color = RED;

608 node = node->parent;

609 }

610 else

611 {

612 if (BLACK == w->right->color)

613 {

614 w->left->color = BLACK;

615 w->color = RED;

616 rbtree_rotate_right(rbtree, w);

617 w = node->parent->right;

618 }

619 w->color = node->parent->color;

620 node->parent->color = BLACK;

621 w->right->color = BLACK;

622 rbtree_rotate_left(rbtree, node->parent);

623 node = rbtree->root;

624 }

625 }

626 else

627 {

628 struct rbtree_node * w = node->parent->left;

629 if (RED == w->color)

630 {

631 w->color = BLACK;

632 node->parent->color = RED;

633 rbtree_rotate_right(rbtree, node->parent);

634 w = node->parent->left;

635 }

636 if ( (BLACK == w->right->color) && (BLACK == w->left->color) )

637 {

638 w->right->color = RED;

639 node = node->parent;

640 }

641 else

642 {

643 if (BLACK == w->left->color)

644 {

645 w->right->color = BLACK;

646 w->color = RED;

647 rbtree_rotate_left(rbtree, w);

648 w = node->parent->left;

649 }

650 w->color = node->parent->color;

651 node->parent->color = BLACK;

652 w->left->color = BLACK;

653 rbtree_rotate_right(rbtree, node->parent);

654 node = rbtree->root;

655 }

656 }

657 }

658 node->color = BLACK;

659 }

660

661 ////////////////////////////////////////////////////////////////////////////////

662 void

663 rbtree_rotate_left(struct rbtree * rbtree, struct rbtree_node * node)

664 {

665 if ( (NULL == rbtree) || (rbtree->nil == node) || (rbtree->nil == node->right) )

666 return;

667

668 struct rbtree_node * y = node->right;

669

670 node->right = y->left;

671 if (rbtree->nil != y->left)

672 y->left->parent = node;

673

674 y->parent = node->parent;

675 if (rbtree->nil == node->parent)

676 rbtree->root = y;

677 else if (node == node->parent->left)

678 node->parent->left = y;

679 else

680 node->parent->right = y;

681

682 y->left = node;

683 node->parent = y;

684 }

685

686 ////////////////////////////////////////////////////////////////////////////////

687 void

688 rbtree_rotate_right(struct rbtree * rbtree, struct rbtree_node * node)

689 {

690 if ( (NULL == rbtree) || (rbtree->nil == node) || (rbtree->nil == node->left) )

691 return;

692

693 struct rbtree_node * y = node->left;

694

695 node->left = y->right;

696 if (rbtree->nil != y->right)

697 y->right->parent = node;

698

699 y->parent = node->parent;

700 if (rbtree->nil == node->parent)

701 rbtree->root = y;

702 else if (node == node->parent->right)

703 node->parent->right = y;

704 else

705 node->parent->left = y;

706

707 y->right = node;

708 node->parent = y;

709 }

710

711 ////////////////////////////////////////////////////////////////////////////////

712 unsigned int rbtree_black_depth(struct rbtree * rbtree)

713 {

714 if ( (NULL == rbtree) || (NULL == rbtree->root) )

715 return 0;

716

717 struct rbtree_node * node = rbtree->root;

718 unsigned int black_depth = 0;

719

720 while (rbtree->nil != node)

721 {

722 if (BLACK == node->color)

723 black_depth++;

724 node = node->left;

725 }

726

727 return black_depth;

728 }

729

730 ////////////////////////////////////////////////////////////////////////////////

731 void

732 rbtree_dump(struct rbtree * rbtree, void (*print_val)(void *) )

733 {

734 if ( (NULL == rbtree) || (rbtree->nil == rbtree->root) )

735 return;

736

737 rbtree_node_dump_preorder(rbtree, rbtree->root, print_val, 0);

738 }

739

740 ////////////////////////////////////////////////////////////////////////////////

741 void

742 rbtree_node_dump_preorder(struct rbtree * rbtree, struct rbtree_node * node, void (*print_val)(void *), int depth)

743 {

744 for (int i=0; i < depth; i++)

745 printf("\t");

746 printf("%-8s", (BLACK == node->color ? "black" : "red"));

747 print_val(node->data);

748 printf("\n");

749 if (rbtree->nil != node->left)

750 rbtree_node_dump_preorder(rbtree, node->left, print_val, depth+1);

751 if (rbtree->nil != node->right)

752 rbtree_node_dump_preorder(rbtree, node->right, print_val, depth+1);

753 }

754

755 ////////////////////////////////////////////////////////////////////////////////

756 unsigned int

757 rbtree_size (struct rbtree * rbtree)

758 {

759 if (NULL == rbtree)

760 return 0;

761 return rbtree->size;

762 }

763

764 ////////////////////////////////////////////////////////////////////////////////

765 void

766 rbtree_walk_breadth_first (struct rbtree * rbtree, void (*op)(void * data))

767 {

768 if ( (NULL == rbtree) || (NULL == op) )

769 return;

770

771 if (0 == rbtree->size)

772 return;

773

774 // Should really use a dynamically sized queue here.

775 struct queue * q = queue_new(rbtree->size);

776 if (NULL == q)

777 return;

778

779 queue_push(q, rbtree->root);

780

781 struct rbtree_node * node;

782

783 while (node = queue_pop(q))

784 {

785 if (rbtree->nil != node->left)

786 queue_push(q, node->left);

787 if (rbtree->nil != node->right)

788 queue_push(q, node->right);

789 op(node->data);

790 }

791

792 queue_delete(q);

793 }

794

Mercurial > data_structures

view src/rbtree.c @ 12:d359966ed8de