data_structures: 68f85ffc6029 src/bst.c

view src/bst.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 "bst.h"

6 struct bst_node

7 {

8 struct bst_node * parent;

9 struct bst_node * left;

10 struct bst_node * right;

11 void * data;

12 };

14 struct bst

15 {

16 struct bst_node * root;

17 size_t size;

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

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

20 };

22 struct bst_iterator

23 {

24 struct bst * bst;

25 struct bst_node * curr;

26 };

28 void bst_data_walk_inorder(struct bst_node * node, void (*op)(void * data));

29 void bst_data_walk_preorder(struct bst_node * node, void (*op)(void * data));

30 void bst_data_walk_postorder(struct bst_node * node, void (*op)(void * data));

32 void bst_node_walk_postorder(struct bst_node * node, void (*op)(struct bst_node * n));

34 void * bst_data_search(struct bst * bst, struct bst_node * node, void * data);

35 void * bst_node_minimum(struct bst_node * node);

36 void * bst_node_maximum(struct bst_node * node);

38 void bst_node_free(struct bst_node * node);

40 struct bst_node * bst_node_search(struct bst * bst, struct bst_node * node, void * data);

41 struct bst_node * bst_transplant(struct bst * bst, struct bst_node * a, struct bst_node * b);

43 void bst_dump(struct bst * bst, void (*print_val)(void *) );

44 void bst_node_dump_preorder(struct bst * bst, struct bst_node * node, void (*print_val)(void *), int depth);

46 ////////////////////////////////////////////////////////////////////////////////

47 struct bst *

48 bst_new(bool (*le)(void * a, void * b),

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

50 {

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

52 return NULL;

54 struct bst * bst = malloc(sizeof(struct bst));

55 if (NULL == bst)

56 return NULL;

58 bst->root = NULL;

59 bst->size = 0;

60 bst->le = le;

61 bst->eq = eq;

62 return bst;

63 }

66 ////////////////////////////////////////////////////////////////////////////////

67 void

68 bst_delete(struct bst * bst)

69 {

70 if (NULL == bst) return;

71 if (0 < bst->size)

72 {

73 // Walk the tree and delete the nodes.

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

75 // emptied the tree.

76 bst_node_walk_postorder(bst->root, bst_node_free);

77 }

78 free(bst);

79 }

81 ////////////////////////////////////////////////////////////////////////////////

82 void

83 bst_node_free(struct bst_node * node)

84 {

85 free(node);

86 }

88 ////////////////////////////////////////////////////////////////////////////////

89 void *

90 bst_insert(struct bst * bst, void * data)

91 {

92 if ( (NULL == bst) || (NULL == data) )

93 return NULL;

95 struct bst_node * new = malloc(sizeof(struct bst_node));

96 if (NULL == new)

97 return NULL;

98 new->left = new->right = new->parent = NULL;

99 new->data = data;

100

101 if (NULL == bst->root)

102 {

103 bst->root = new;

104 bst->size = 1;

105 return new->data;

106 }

107

108 struct bst_node * p = NULL;

109 struct bst_node * c = bst->root;

110

111 while (NULL != c)

112 {

113 p = c;

114 if (bst->le(new->data, c->data))

115 c = c->left;

116 else

117 c = c->right;

118 }

119 new->parent = p;

120 if (bst->le(new->data, p->data))

121 p->left = new;

122 else

123 p->right = new;

124

125 bst->size++;

126 return new->data;

127 }

128

129

130 ////////////////////////////////////////////////////////////////////////////////

131 void bst_walk_inorder(struct bst * bst, void (*op)(void * data))

132 {

133 if ( (NULL == bst) || (NULL == bst->root) || (NULL == op) )

134 return;

135

136 bst_data_walk_inorder(bst->root, op);

137 }

138

139 ////////////////////////////////////////////////////////////////////////////////

140 void bst_walk_postorder(struct bst * bst, void (*op)(void * data))

141 {

142 if ( (NULL == bst) || (NULL == bst->root) || (NULL == op) )

143 return;

144

145 bst_data_walk_postorder(bst->root, op);

146 }

147

148 ////////////////////////////////////////////////////////////////////////////////

149 void bst_walk_preorder(struct bst * bst, void (*op)(void * data))

150 {

151 if ( (NULL == bst) || (NULL == bst->root) || (NULL == op) )

152 return;

153

154 bst_data_walk_preorder(bst->root, op);

155 }

156

157 ////////////////////////////////////////////////////////////////////////////////

158 void bst_data_walk_inorder(struct bst_node * node, void (*op)(void * data))

159 {

160 if (NULL != node)

161 {

162 bst_data_walk_inorder(node->left, op);

163 op(node->data);

164 bst_data_walk_inorder(node->right, op);

165 }

166 }

167

168 ////////////////////////////////////////////////////////////////////////////////

169 void bst_data_walk_postorder(struct bst_node * node, void (*op)(void * data))

170 {

171 if (NULL != node)

172 {

173 bst_data_walk_postorder(node->left, op);

174 bst_data_walk_postorder(node->right, op);

175 op(node->data);

176 }

177 }

178

179 ////////////////////////////////////////////////////////////////////////////////

180 void bst_data_walk_preorder(struct bst_node * node, void (*op)(void * data))

181 {

182 if (NULL != node)

183 {

184 op(node->data);

185 bst_data_walk_preorder(node->left, op);

186 bst_data_walk_preorder(node->right, op);

187 }

188 }

189

190 ////////////////////////////////////////////////////////////////////////////////

191 void bst_node_walk_postorder(struct bst_node * node, void (*op)(struct bst_node * n))

192 {

193 if (NULL != node)

194 {

195 bst_node_walk_postorder(node->left, op);

196 bst_node_walk_postorder(node->right, op);

197 op(node);

198 }

199 }

200

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

202 void * bst_search(struct bst * bst, void * data)

203 {

204 if ( (NULL == bst) || (NULL == bst->root) || (NULL == data) )

205 return NULL;

206

207 return bst_data_search(bst, bst->root, data);

208 }

209

210 ////////////////////////////////////////////////////////////////////////////////

211 // Recursive

212 void * bst_data_search(struct bst * bst, struct bst_node * node, void * data)

213 {

214 if (NULL == node)

215 return NULL;

216

217 if (bst->eq(data, node->data))

218 return node->data;

219

220 if (bst->le(data, node->data))

221 return bst_data_search(bst, node->left, data);

222 else

223 return bst_data_search(bst, node->right, data);

224 }

225

226 ////////////////////////////////////////////////////////////////////////////////

227 // Iterative

228 void * bst_search_iterative(struct bst * bst, void * data)

229 {

230 if ( (NULL == bst) || (NULL == bst->root) || (NULL == data) )

231 return NULL;

232

233 struct bst_node * node = bst->root;

234 while (1)

235 {

236 if (NULL == node)

237 return NULL;

238

239 if (bst->eq(data, node->data))

240 return node->data;

241

242 if (bst->le(data, node->data))

243 node = node->left;

244 else

245 node = node->right;

246 }

247 }

248

249 ////////////////////////////////////////////////////////////////////////////////

250 void * bst_minimum(struct bst * bst)

251 {

252 if (NULL == bst)

253 return NULL;

254

255 return bst_node_minimum(bst->root);

256 }

257

258 ////////////////////////////////////////////////////////////////////////////////

259 void * bst_node_minimum(struct bst_node * node)

260 {

261 while ( (NULL != node) && (NULL != node->left) )

262 node = node->left;

263 if (NULL == node)

264 return NULL;

265 return node->data;

266 }

267

268 ////////////////////////////////////////////////////////////////////////////////

269 void * bst_maximum(struct bst * bst)

270 {

271 if (NULL == bst)

272 return NULL;

273

274 return bst_node_maximum(bst->root);

275 }

276

277 ////////////////////////////////////////////////////////////////////////////////

278 void * bst_node_maximum(struct bst_node * node)

279 {

280 while ( (NULL != node) && (NULL != node->right) )

281 node = node->right;

282 if (NULL == node)

283 return NULL;

284 return node->data;

285 }

286

287 ////////////////////////////////////////////////////////////////////////////////

288 struct bst_iterator * bst_begin(struct bst * bst)

289 {

290 if ( (NULL == bst) || (NULL == bst->root) )

291 return NULL;

292

293 struct bst_node * min = bst->root;

294 while (min->left)

295 min = min->left;

296

297 struct bst_iterator * it = malloc(sizeof(struct bst_iterator));

298 if (NULL == it)

299 return NULL;

300

301 it->bst = bst;

302 it->curr = min;

303 return it;

304 }

305

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

307 struct bst_iterator * bst_end(struct bst * bst)

308 {

309 if ( (NULL == bst) || (NULL == bst->root) )

310 return NULL;

311

312 struct bst_node * max = bst->root;

313 while (max->right)

314 max = max->right;

315

316 struct bst_iterator * it = malloc(sizeof(struct bst_iterator));

317 if (NULL == it)

318 return NULL;

319

320 it->bst = bst;

321 it->curr = max;

322 return it;

323 }

324

325 ////////////////////////////////////////////////////////////////////////////////

326 struct bst_iterator * bst_next(struct bst_iterator * it)

327 {

328 if ( (NULL == it) || (NULL == it->bst) || (NULL == it->curr) )

329 return NULL;

330

331 if (NULL == it->curr->right)

332 {

333 struct bst_node * p = it->curr;

334 it->curr = it->curr->parent;

335 while ( (NULL != it->curr) && (p == it->curr->right) )

336 {

337 p = it->curr;

338 it->curr = it->curr->parent;

339 }

340

341 if (it->curr == NULL)

342 return NULL;

343 }

344 else

345 {

346 struct bst_node * min = it->curr->right;

347 while (min->left)

348 min = min->left;

349 it->curr = min;

350 }

351 return it;

352 }

353

354 ////////////////////////////////////////////////////////////////////////////////

355 struct bst_iterator * bst_prev(struct bst_iterator * it)

356 {

357 if ( (NULL == it) || (NULL == it->bst) || (NULL == it->curr) )

358 return NULL;

359

360 if (NULL == it->curr->left)

361 {

362 struct bst_node * p = it->curr;

363 it->curr = it->curr->parent;

364 while ( (NULL != it->curr) && (p == it->curr->left) )

365 {

366 p = it->curr;

367 it->curr = it->curr->parent;

368 }

369

370 if (it->curr == NULL)

371 return NULL;

372 }

373 else

374 {

375 struct bst_node * max = it->curr->left;

376 while (max->right)

377 max = max->right;

378 it->curr = max;

379 }

380 return it;

381 }

382

383 ////////////////////////////////////////////////////////////////////////////////

384 void * bst_value(struct bst_iterator * it)

385 {

386 if ( (NULL == it) || (NULL == it->bst) || (NULL == it->curr) )

387 return NULL;

388

389 return it->curr->data;

390 }

391

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

393 void *

394 bst_find(struct bst_iterator * it, void * data)

395 {

396 if ( (NULL == it) || (NULL == it->bst) || (NULL == it->bst->root) || (NULL == data) )

397 return NULL;

398

399 return bst_node_search(it->bst, it->bst->root, data);

400 }

401

402 ////////////////////////////////////////////////////////////////////////////////

403 // Recursive

404 struct bst_node *

405 bst_node_search(struct bst * bst, struct bst_node * node, void * data)

406 {

407 if (NULL == node)

408 return NULL;

409

410 if (bst->eq(data, node->data))

411 return node;

412

413 if (bst->le(data, node->data))

414 return bst_node_search(bst, node->left, data);

415 else

416 return bst_node_search(bst, node->right, data);

417 }

418

419 ////////////////////////////////////////////////////////////////////////////////

420 struct bst_node *

421 bst_transplant(struct bst * bst, struct bst_node * a, struct bst_node * b)

422 {

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

424 return NULL;

425

426 if (NULL == a->parent)

427 bst->root = b;

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

429 a->parent->left = b;

430 else

431 a->parent->right = b;

432

433 if (NULL != b)

434 b->parent = a->parent;

435

436 return a;

437 }

438

439 ////////////////////////////////////////////////////////////////////////////////

440 void *

441 bst_remove(struct bst_iterator * it)

442 {

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

444 return NULL;

445

446 struct bst_node * y;

447

448 if (NULL == it->curr->left)

449 {

450 bst_transplant(it->bst, it->curr, it->curr->right);

451 y = it->curr->right;

452 }

453 else if (NULL == it->curr->right)

454 {

455 bst_transplant(it->bst, it->curr, it->curr->left);

456 y = it->curr->left;

457 }

458 else

459 {

460 y = bst_node_minimum(it->curr->right);

461 if (NULL != y->parent)

462 {

463 bst_transplant(it->bst, y, y->right);

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

465 y->right->parent = y;

466 }

467 bst_transplant(it->bst, it->curr, y);

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

469 y->left->parent = y;

470 }

471

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

473 free(it->curr);

474 it->curr = y;

475 return data;

476 }

477

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

479 void

480 bst_dump(struct bst * bst, void (*print_val)(void *) )

481 {

482 bst_node_dump_preorder(bst, bst->root, print_val, 0);

483 }

484

485 ////////////////////////////////////////////////////////////////////////////////

486 void

487 bst_node_dump_preorder(struct bst * bst, struct bst_node * node, void (*print_val)(void *), int depth)

488 {

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

490 printf("\t");

491 print_val(node->data);

492 printf("\n");

493 if (NULL != node->left)

494 bst_node_dump_preorder(bst, node->left, print_val, depth+1);

495 if (NULL != node->right)

496 bst_node_dump_preorder(bst, node->right, print_val, depth+1);

497 }

Mercurial > data_structures

view src/bst.c @ 10:68f85ffc6029