data_structures: 68f85ffc6029 src/rbtree.c

view src/rbtree.c @ 10:68f85ffc6029

Finished rbtree. Reworked the iterators in list. Minor tweaks to others.

author	Eris Caffee <discordia@eldalin.com>
date	Fri, 28 Sep 2012 18:24:53 -0500
parents	abdba37f67a2
children	d359966ed8de

line source

1 #include <stdio.h>

2 #include <stdlib.h>

4 #include "rbtree.h"

6 enum rbtree_color { RED, BLACK };

8 struct rbtree_node

9 {

10 enum rbtree_color color;

11 struct rbtree_node * parent;

12 struct rbtree_node * left;

13 struct rbtree_node * right;

14 void * data;

15 };

17 struct rbtree

18 {

19 struct rbtree_node nil_node;

20 struct rbtree_node * nil;

21 struct rbtree_node * root;

22 size_t size;

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

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

25 };

27 struct rbtree_iterator

28 {

29 struct rbtree * rbtree;

30 struct rbtree_node * curr;

31 };

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

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

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

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

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

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

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

42 void rbtree_node_free (struct rbtree_node * node);

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

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

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

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

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

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

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

54 ////////////////////////////////////////////////////////////////////////////////

55 struct rbtree *

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

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

58 {

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

60 return NULL;

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

63 if (NULL == rbtree)

64 return NULL;

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

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

68 rbtree->root = rbtree->nil;

69 rbtree->size = 0;

70 rbtree->le = le;

71 rbtree->eq = eq;

72 return rbtree;

73 }

76 ////////////////////////////////////////////////////////////////////////////////

77 void

78 rbtree_delete(struct rbtree * rbtree)

79 {

80 if (NULL == rbtree) return;

81 if (0 < rbtree->size)

82 {

83 // Walk the tree and delete the nodes.

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

85 // emptied the tree.

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

87 }

88 free(rbtree);

89 }

91 ////////////////////////////////////////////////////////////////////////////////

92 void

93 rbtree_node_free(struct rbtree_node * node)

94 {

95 free(node);

96 }

98 ////////////////////////////////////////////////////////////////////////////////

99 void *

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

101 {

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

103 return NULL;

104

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

106 if (NULL == new)

107 return NULL;

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

109 new->color = RED;

110 new->data = data;

111

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

113 {

114 rbtree->root = new;

115 new->color = BLACK;

116 new->parent = rbtree->nil;

117 rbtree->size = 1;

118 return new->data;

119 }

120

121 struct rbtree_node * p = rbtree->nil;

122 struct rbtree_node * c = rbtree->root;

123

124 while (rbtree->nil != c)

125 {

126 p = c;

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

128 c = c->left;

129 else

130 c = c->right;

131 }

132 new->parent = p;

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

134 p->left = new;

135 else

136 p->right = new;

137

138 rbtree_insert_fixup(rbtree, new);

139

140 rbtree->size++;

141 return new->data;

142 }

143

144 ////////////////////////////////////////////////////////////////////////////////

145 void

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

147 {

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

149 return;

150

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

152 {

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

154 {

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

156 if (RED == y->color)

157 {

158 node->parent->color = BLACK;

159 y->color = BLACK;

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

161 node = node->parent->parent;

162 }

163 else

164 {

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

166 {

167 node = node->parent;

168 rbtree_rotate_left(rbtree, node);

169 }

170 node->parent->color = BLACK;

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

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

173 }

174 }

175 else

176 {

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

178 if (RED == y->color)

179 {

180 node->parent->color = BLACK;

181 y->color = BLACK;

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

183 node = node->parent->parent;

184 }

185 else

186 {

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

188 {

189 node = node->parent;

190 rbtree_rotate_right(rbtree, node);

191 }

192 node->parent->color = BLACK;

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

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

195 }

196 }

197 }

198 rbtree->root->color = BLACK;

199 }

200

201 ////////////////////////////////////////////////////////////////////////////////

202 void

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

204 {

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

206 return;

207

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

209 }

210

211 ////////////////////////////////////////////////////////////////////////////////

212 void

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

214 {

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

216 return;

217

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

219 }

220

221 ////////////////////////////////////////////////////////////////////////////////

222 void

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

224 {

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

226 return;

227

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

229 }

230

231 ////////////////////////////////////////////////////////////////////////////////

232 void

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

234 {

235 if (rbtree->nil != node)

236 {

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

238 op(node->data);

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

240 }

241 }

242

243 ////////////////////////////////////////////////////////////////////////////////

244 void

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

246 {

247 if (rbtree->nil != node)

248 {

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

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

251 op(node->data);

252 }

253 }

254

255 ////////////////////////////////////////////////////////////////////////////////

256 void

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

258 {

259 if (rbtree->nil != node)

260 {

261 op(node->data);

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

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

264 }

265 }

266

267 ////////////////////////////////////////////////////////////////////////////////

268 void

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

270 {

271 if (rbtree->nil != node)

272 {

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

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

275 op(node);

276 }

277 }

278

279 ////////////////////////////////////////////////////////////////////////////////

280 void *

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

282 {

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

284 return NULL;

285

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

287 }

288

289 ////////////////////////////////////////////////////////////////////////////////

290 // Recursive

291 void *

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

293 {

294 if (rbtree->nil == node)

295 return NULL;

296

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

298 return node->data;

299

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

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

302 else

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

304 }

305

306 ////////////////////////////////////////////////////////////////////////////////

307 // Iterative

308 void *

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

310 {

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

312 return NULL;

313

314 struct rbtree_node * node = rbtree->root;

315 while (1)

316 {

317 if (rbtree->nil == node)

318 return NULL;

319

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

321 return node->data;

322

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

324 node = node->left;

325 else

326 node = node->right;

327 }

328 }

329

330 ////////////////////////////////////////////////////////////////////////////////

331 void *

332 rbtree_minimum(struct rbtree * rbtree)

333 {

334 if (NULL == rbtree)

335 return NULL;

336

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

338 }

339

340 ////////////////////////////////////////////////////////////////////////////////

341 void *

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

343 {

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

345 node = node->left;

346 if (rbtree->nil == node)

347 return NULL;

348 return node->data;

349 }

350

351 ////////////////////////////////////////////////////////////////////////////////

352 void *

353 rbtree_maximum(struct rbtree * rbtree)

354 {

355 if (NULL == rbtree)

356 return NULL;

357

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

359 }

360

361 ////////////////////////////////////////////////////////////////////////////////

362 void *

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

364 {

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

366 node = node->right;

367 if (rbtree->nil == node)

368 return NULL;

369 return node->data;

370 }

371

372 ////////////////////////////////////////////////////////////////////////////////

373 struct rbtree_iterator *

374 rbtree_begin(struct rbtree * rbtree)

375 {

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

377 return NULL;

378

379 struct rbtree_node * min = rbtree->root;

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

381 min = min->left;

382

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

384 if (NULL == it)

385 return NULL;

386

387 it->rbtree = rbtree;

388 it->curr = min;

389 return it;

390 }

391

392 ////////////////////////////////////////////////////////////////////////////////

393 struct rbtree_iterator *

394 rbtree_end(struct rbtree * rbtree)

395 {

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

397 return NULL;

398

399 struct rbtree_node * max = rbtree->root;

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

401 max = max->right;

402

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

404 if (NULL == it)

405 return NULL;

406

407 it->rbtree = rbtree;

408 it->curr = max;

409 return it;

410 }

411

412 ////////////////////////////////////////////////////////////////////////////////

413 struct rbtree_iterator *

414 rbtree_next(struct rbtree_iterator * it)

415 {

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

417 return NULL;

418

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

420 {

421 struct rbtree_node * p = it->curr;

422 it->curr = it->curr->parent;

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

424 {

425 p = it->curr;

426 it->curr = it->curr->parent;

427 }

428

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

430 return NULL;

431 }

432 else

433 {

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

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

436 min = min->left;

437 it->curr = min;

438 }

439 return it;

440 }

441

442 ////////////////////////////////////////////////////////////////////////////////

443 struct rbtree_iterator *

444 rbtree_prev(struct rbtree_iterator * it)

445 {

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

447 return NULL;

448

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

450 {

451 struct rbtree_node * p = it->curr;

452 it->curr = it->curr->parent;

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

454 {

455 p = it->curr;

456 it->curr = it->curr->parent;

457 }

458

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

460 return NULL;

461 }

462 else

463 {

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

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

466 max = max->right;

467 it->curr = max;

468 }

469 return it;

470 }

471

472 ////////////////////////////////////////////////////////////////////////////////

473 void *

474 rbtree_value(struct rbtree_iterator * it)

475 {

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

477 return NULL;

478

479 return it->curr->data;

480 }

481

482 ////////////////////////////////////////////////////////////////////////////////

483 void *

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

485 {

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

487 return NULL;

488

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

490 }

491

492 ////////////////////////////////////////////////////////////////////////////////

493 // Recursive

494 struct rbtree_node *

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

496 {

497 if (rbtree->nil == node)

498 return NULL;

499

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

501 return node;

502

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

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

505 else

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

507 }

508

509 ////////////////////////////////////////////////////////////////////////////////

510 struct rbtree_node *

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

512 {

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

514 return NULL;

515

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

517 rbtree->root = b;

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

519 a->parent->left = b;

520 else

521 a->parent->right = b;

522

523 b->parent = a->parent;

524

525 return a;

526 }

527

528 ////////////////////////////////////////////////////////////////////////////////

529 void *

530 rbtree_remove(struct rbtree_iterator * it)

531 {

532 if ( (NULL == it) || (NULL == it->curr) )

533 return NULL;

534

535 // Get predecessor and save it

536 struct rbtree_iterator pred;

537 pred.curr = it->curr;

538 pred.rbtree = it->rbtree;

539 rbtree_prev(&pred);

540

541 struct rbtree_node * x;

542 struct rbtree_node * y = it->curr;

543 enum rbtree_color original_color = y->color;

544

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

546 {

547 x = it->curr->right;

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

549 }

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

551 {

552 x = it->curr->left;

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

554 }

555 else

556 {

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

558 original_color = y->color;

559 x = y->right;

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

561 x->parent = y;

562 else

563 {

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

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

566 y->right->parent = y;

567 }

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

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

570 y->left->parent = y;

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

572 }

573

574 if (BLACK == original_color)

575 rbtree_remove_fixup(it->rbtree, x);

576

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

578 free(it->curr);

579

580 // Update it to point to pred's successor

581 rbtree_next(&pred);

582 it->curr = pred.curr;

583

584 return data;

585 }

586

587 ////////////////////////////////////////////////////////////////////////////////

588 void

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

590 {

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

592 {

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

594 {

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

596 if (RED == w->color)

597 {

598 w->color = BLACK;

599 node->parent->color = RED;

600 rbtree_rotate_left(rbtree, node->parent);

601 w = node->parent->right;

602 }

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

604 {

605 w->left->color = RED;

606 node = node->parent;

607 }

608 else

609 {

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

611 {

612 w->left->color = BLACK;

613 w->color = RED;

614 rbtree_rotate_right(rbtree, w);

615 w = node->parent->right;

616 }

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

618 node->parent->color = BLACK;

619 w->right->color = BLACK;

620 rbtree_rotate_left(rbtree, node->parent);

621 node = rbtree->root;

622 }

623 }

624 else

625 {

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

627 if (RED == w->color)

628 {

629 w->color = BLACK;

630 node->parent->color = RED;

631 rbtree_rotate_right(rbtree, node->parent);

632 w = node->parent->left;

633 }

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

635 {

636 w->right->color = RED;

637 node = node->parent;

638 }

639 else

640 {

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

642 {

643 w->right->color = BLACK;

644 w->color = RED;

645 rbtree_rotate_left(rbtree, w);

646 w = node->parent->left;

647 }

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

649 node->parent->color = BLACK;

650 w->left->color = BLACK;

651 rbtree_rotate_right(rbtree, node->parent);

652 node = rbtree->root;

653 }

654 }

655 }

656 node->color = BLACK;

657 }

658

659 ////////////////////////////////////////////////////////////////////////////////

660 void

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

662 {

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

664 return;

665

666 struct rbtree_node * y = node->right;

667

668 node->right = y->left;

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

670 y->left->parent = node;

671

672 y->parent = node->parent;

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

674 rbtree->root = y;

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

676 node->parent->left = y;

677 else

678 node->parent->right = y;

679

680 y->left = node;

681 node->parent = y;

682 }

683

684 ////////////////////////////////////////////////////////////////////////////////

685 void

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

687 {

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

689 return;

690

691 struct rbtree_node * y = node->left;

692

693 node->left = y->right;

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

695 y->right->parent = node;

696

697 y->parent = node->parent;

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

699 rbtree->root = y;

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

701 node->parent->right = y;

702 else

703 node->parent->left = y;

704

705 y->right = node;

706 node->parent = y;

707 }

708

709 ////////////////////////////////////////////////////////////////////////////////

710 unsigned int rbtree_black_depth(struct rbtree * rbtree)

711 {

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

713 return 0;

714

715 struct rbtree_node * node = rbtree->root;

716 unsigned int black_depth = 0;

717

718 while (rbtree->nil != node)

719 {

720 if (BLACK == node->color)

721 black_depth++;

722 node = node->left;

723 }

724

725 return black_depth;

726 }

727

728 ////////////////////////////////////////////////////////////////////////////////

729 void

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

731 {

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

733 }

734

735 ////////////////////////////////////////////////////////////////////////////////

736 void

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

738 {

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

740 printf("\t");

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

742 print_val(node->data);

743 printf("\n");

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

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

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

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

748 }

Mercurial > data_structures

view src/rbtree.c @ 10:68f85ffc6029