data_structures: abdba37f67a2 src/rbtree.c

view src/rbtree.c @ 9:abdba37f67a2

Red-black tree in progress. Linked list needs iterators redone, also in progress. Sleepy.

author	Eris Caffee <discordia@eldalin.com>
date	Fri, 28 Sep 2012 03:08:25 -0500
parents
children	68f85ffc6029

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 // Private functions.

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

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

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

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

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

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

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

41 void rbtree_node_free(struct rbtree_node * node);

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

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

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

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

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

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

49 ////////////////////////////////////////////////////////////////////////////////

50 struct rbtree *

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

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

53 {

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

55 return NULL;

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

58 if (NULL == rbtree)

59 return NULL;

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

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

63 rbtree->root = rbtree->nil;

64 rbtree->size = 0;

65 rbtree->le = le;

66 rbtree->eq = eq;

67 return rbtree;

68 }

71 ////////////////////////////////////////////////////////////////////////////////

72 void

73 rbtree_delete(struct rbtree * rbtree)

74 {

75 if (NULL == rbtree) return;

76 if (0 < rbtree->size)

77 {

78 // Walk the tree and delete the nodes.

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

80 // emptied the tree.

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

82 }

83 free(rbtree);

84 }

86 ////////////////////////////////////////////////////////////////////////////////

87 void

88 rbtree_node_free(struct rbtree_node * node)

89 {

90 free(node);

91 }

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

94 void *

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

96 {

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

98 return NULL;

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

101 if (NULL == new)

102 return NULL;

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

104 new->color = RED;

105 new->data = data;

106

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

108 {

109 rbtree->root = new;

110 new->color = BLACK;

111 new->parent = rbtree->nil;

112 rbtree->size = 1;

113 return new->data;

114 }

115

116 struct rbtree_node * p = rbtree->nil;

117 struct rbtree_node * c = rbtree->root;

118

119 while (rbtree->nil != c)

120 {

121 p = c;

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

123 c = c->left;

124 else

125 c = c->right;

126 }

127 new->parent = p;

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

129 p->left = new;

130 else

131 p->right = new;

132

133 rbtree_insert_fixup(rbtree, new);

134

135 rbtree->size++;

136 return new->data;

137 }

138

139

140 ////////////////////////////////////////////////////////////////////////////////

141 void

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

143 {

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

145 return;

146

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

148 {

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

150 {

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

152 if (RED == y->color)

153 {

154 node->parent->color = BLACK;

155 y->color = BLACK;

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

157 node = node->parent->parent;

158 }

159 else

160 {

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

162 {

163 node = node->parent;

164 rbtree_rotate_left(rbtree, node);

165 }

166 node->parent->color = BLACK;

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

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

169 }

170 }

171 else

172 {

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

174 if (RED == y->color)

175 {

176 node->parent->color = BLACK;

177 y->color = BLACK;

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

179 node = node->parent->parent;

180 }

181 else

182 {

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

184 {

185 node = node->parent;

186 rbtree_rotate_right(rbtree, node);

187 }

188 node->parent->color = BLACK;

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

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

191 }

192 }

193 }

194 rbtree->root->color = BLACK;

195 }

196

197 ////////////////////////////////////////////////////////////////////////////////

198 void

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

200 {

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

202 return;

203

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

205 }

206

207 ////////////////////////////////////////////////////////////////////////////////

208 void

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

210 {

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

212 return;

213

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

215 }

216

217 ////////////////////////////////////////////////////////////////////////////////

218 void

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

220 {

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

222 return;

223

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

225 }

226

227 ////////////////////////////////////////////////////////////////////////////////

228 void

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

230 {

231 if (rbtree->nil != node)

232 {

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

234 op(node->data);

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

236 }

237 }

238

239 ////////////////////////////////////////////////////////////////////////////////

240 void

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

242 {

243 if (rbtree->nil != node)

244 {

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

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

247 op(node->data);

248 }

249 }

250

251 ////////////////////////////////////////////////////////////////////////////////

252 void

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

254 {

255 if (rbtree->nil != node)

256 {

257 op(node->data);

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

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

260 }

261 }

262

263 ////////////////////////////////////////////////////////////////////////////////

264 void

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

266 {

267 if (rbtree->nil != node)

268 {

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

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

271 op(node);

272 }

273 }

274

275 ////////////////////////////////////////////////////////////////////////////////

276 void *

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

278 {

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

280 return NULL;

281

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

283 }

284

285 ////////////////////////////////////////////////////////////////////////////////

286 // Recursive

287 void *

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

289 {

290 if (rbtree->nil == node)

291 return NULL;

292

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

294 return node->data;

295

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

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

298 else

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

300 }

301

302 ////////////////////////////////////////////////////////////////////////////////

303 // Iterative

304 void *

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

306 {

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

308 return NULL;

309

310 struct rbtree_node * node = rbtree->root;

311 while (1)

312 {

313 if (rbtree->nil == node)

314 return NULL;

315

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

317 return node->data;

318

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

320 node = node->left;

321 else

322 node = node->right;

323 }

324 }

325

326 ////////////////////////////////////////////////////////////////////////////////

327 void *

328 rbtree_minimum(struct rbtree * rbtree)

329 {

330 if (NULL == rbtree)

331 return NULL;

332

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

334 }

335

336 ////////////////////////////////////////////////////////////////////////////////

337 void *

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

339 {

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

341 node = node->left;

342 if (rbtree->nil == node)

343 return NULL;

344 return node->data;

345 }

346

347 ////////////////////////////////////////////////////////////////////////////////

348 void *

349 rbtree_maximum(struct rbtree * rbtree)

350 {

351 if (NULL == rbtree)

352 return NULL;

353

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

355 }

356

357 ////////////////////////////////////////////////////////////////////////////////

358 void *

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

360 {

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

362 node = node->right;

363 if (rbtree->nil == node)

364 return NULL;

365 return node->data;

366 }

367

368 ////////////////////////////////////////////////////////////////////////////////

369 struct rbtree_iterator *

370 rbtree_begin(struct rbtree * rbtree)

371 {

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

373 return NULL;

374

375 struct rbtree_node * min = rbtree->root;

376 while (min->left)

377 min = min->left;

378

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

380 if (NULL == it)

381 return NULL;

382

383 it->rbtree = rbtree;

384 it->curr = min;

385 return it;

386 }

387

388 ////////////////////////////////////////////////////////////////////////////////

389 struct rbtree_iterator *

390 rbtree_end(struct rbtree * rbtree)

391 {

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

393 return NULL;

394

395 struct rbtree_node * max = rbtree->root;

396 while (max->right)

397 max = max->right;

398

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

400 if (NULL == it)

401 return NULL;

402

403 it->rbtree = rbtree;

404 it->curr = max;

405 return it;

406 }

407

408 ////////////////////////////////////////////////////////////////////////////////

409 struct rbtree_iterator *

410 rbtree_next(struct rbtree_iterator * it)

411 {

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

413 return NULL;

414

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

416 {

417 struct rbtree_node * p = it->curr;

418 it->curr = it->curr->parent;

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

420 {

421 p = it->curr;

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

423 }

424

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

426 return NULL;

427 }

428 else

429 {

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

431 while (min->left)

432 min = min->left;

433 it->curr = min;

434 }

435 return it;

436 }

437

438 ////////////////////////////////////////////////////////////////////////////////

439 struct rbtree_iterator *

440 rbtree_prev(struct rbtree_iterator * it)

441 {

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

443 return NULL;

444

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

446 {

447 struct rbtree_node * p = it->curr;

448 it->curr = it->curr->parent;

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

450 {

451 p = it->curr;

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

453 }

454

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

456 return NULL;

457 }

458 else

459 {

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

461 while (max->right)

462 max = max->right;

463 it->curr = max;

464 }

465 return it;

466 }

467

468 ////////////////////////////////////////////////////////////////////////////////

469 void *

470 rbtree_value(struct rbtree_iterator * it)

471 {

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

473 return NULL;

474

475 return it->curr->data;

476 }

477

478 ////////////////////////////////////////////////////////////////////////////////

479 void *

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

481 {

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

483 return NULL;

484

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

486 }

487

488 ////////////////////////////////////////////////////////////////////////////////

489 // Recursive

490 struct rbtree_node *

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

492 {

493 if (rbtree->nil == node)

494 return NULL;

495

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

497 return node;

498

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

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

501 else

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

503 }

504

505 ////////////////////////////////////////////////////////////////////////////////

506 struct rbtree_node *

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

508 {

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

510 return NULL;

511

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

513 rbtree->root = b;

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

515 a->parent->left = b;

516 else

517 a->parent->right = b;

518

519 b->parent = a->parent;

520

521 return a;

522 }

523

524 ////////////////////////////////////////////////////////////////////////////////

525 void *

526 rbtree_remove(struct rbtree_iterator * it)

527 {

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

529 return NULL;

530

531 // Get predecessor and save it

532 struct rbtree_iterator pred;

533 pred.curr = it->curr;

534 pred.rbtree = it->rbtree;

535 rbtree_prev(&pred);

536

537 struct rbtree_node * x;

538 struct rbtree_node * y = it->curr;

539 enum rbtree_color original_color = y->color;

540

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

542 {

543 x = it->curr->right;

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

545 }

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

547 {

548 x = it->curr->left;

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

550 }

551 else

552 {

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

554 original_color = y->color;

555 x = y->right;

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

557 x->parent = y;

558 else

559 {

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

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

562 y->right->parent = y;

563 }

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

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

566 y->left->parent = y;

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

568 }

569

570 if (BLACK == original_color)

571 rbtree_remove_fixup(it->rbtree, x);

572

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

574 free(it->curr);

575

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

577 rbtree_next(&pred);

578 it->curr = pred.curr;

579

580 return data;

581 }

582

583 ////////////////////////////////////////////////////////////////////////////////

584 void

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

586 {

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

588 {

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

590 {

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

592 if (RED == w->color)

593 {

594 w->color = BLACK;

595 node->parent->color = RED;

596 rbtree_rotate_left(rbtree, node->parent);

597 w = node->parent->right;

598 }

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

600 {

601 w->left->color = RED;

602 node = node->parent;

603 }

604 else

605 {

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

607 {

608 w->left->color = BLACK;

609 w->color = RED;

610 rbtree_rotate_right(rbtree, w);

611 w = node->parent->right;

612 }

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

614 node->parent->color = BLACK;

615 w->right->color = BLACK;

616 rbtree_rotate_left(rbtree, node->parent);

617 node = rbtree->root;

618 }

619 }

620 else

621 {

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

623 if (RED == w->color)

624 {

625 w->color = BLACK;

626 node->parent->color = RED;

627 rbtree_rotate_right(rbtree, node->parent);

628 w = node->parent->left;

629 }

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

631 {

632 w->right->color = RED;

633 node = node->parent;

634 }

635 else

636 {

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

638 {

639 w->right->color = BLACK;

640 w->color = RED;

641 rbtree_rotate_left(rbtree, w);

642 w = node->parent->left;

643 }

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

645 node->parent->color = BLACK;

646 w->left->color = BLACK;

647 rbtree_rotate_right(rbtree, node->parent);

648 node = rbtree->root;

649 }

650 }

651 }

652 node->color = BLACK;

653 }

654

655 ////////////////////////////////////////////////////////////////////////////////

656 void

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

658 {

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

660 return;

661

662 struct rbtree_node * y = node->right;

663

664 node->right = y->left;

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

666 y->left->parent = node;

667

668 y->parent = node->parent;

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

670 rbtree->root = y;

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

672 node->parent->left = y;

673 else

674 node->parent->right = y;

675

676 y->left = node;

677 node->parent = y;

678 }

679

680 ////////////////////////////////////////////////////////////////////////////////

681 void

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

683 {

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

685 return;

686

687 struct rbtree_node * y = node->left;

688

689 node->left = y->right;

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

691 y->right->parent = node;

692

693 y->parent = node->parent;

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

695 rbtree->root = y;

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

697 node->parent->right = y;

698 else

699 node->parent->left = y;

700

701 y->right = node;

702 node->parent = y;

703 }

704

Mercurial > data_structures

view src/rbtree.c @ 9:abdba37f67a2