data_structures: d359966ed8de src/bst.c

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

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_node_dump_preorder(struct bst * bst, struct bst_node * node, void (*print_val)(void *), int depth);

45 ////////////////////////////////////////////////////////////////////////////////

46 struct bst *

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

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

49 {

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

51 return NULL;

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

54 if (NULL == bst)

55 return NULL;

57 bst->root = NULL;

58 bst->size = 0;

59 bst->le = le;

60 bst->eq = eq;

61 return bst;

62 }

65 ////////////////////////////////////////////////////////////////////////////////

66 void

67 bst_delete(struct bst * bst)

68 {

69 if (NULL == bst) return;

70 if (0 < bst->size)

71 {

72 // Walk the tree and delete the nodes.

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

74 // emptied the tree.

75 bst_node_walk_postorder(bst->root, bst_node_free);

76 }

77 free(bst);

78 }

80 ////////////////////////////////////////////////////////////////////////////////

81 void

82 bst_node_free(struct bst_node * node)

83 {

84 free(node);

85 }

87 ////////////////////////////////////////////////////////////////////////////////

88 void *

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

90 {

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

92 return NULL;

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

95 if (NULL == new)

96 return NULL;

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

98 new->data = data;

100 if (NULL == bst->root)

101 {

102 bst->root = new;

103 bst->size = 1;

104 return new->data;

105 }

106

107 struct bst_node * p = NULL;

108 struct bst_node * c = bst->root;

109

110 while (NULL != c)

111 {

112 p = c;

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

114 c = c->left;

115 else

116 c = c->right;

117 }

118 new->parent = p;

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

120 p->left = new;

121 else

122 p->right = new;

123

124 bst->size++;

125 return new->data;

126 }

127

128

129 ////////////////////////////////////////////////////////////////////////////////

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

131 {

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

133 return;

134

135 bst_data_walk_inorder(bst->root, op);

136 }

137

138 ////////////////////////////////////////////////////////////////////////////////

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

140 {

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

142 return;

143

144 bst_data_walk_postorder(bst->root, op);

145 }

146

147 ////////////////////////////////////////////////////////////////////////////////

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

149 {

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

151 return;

152

153 bst_data_walk_preorder(bst->root, op);

154 }

155

156 ////////////////////////////////////////////////////////////////////////////////

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

158 {

159 if (NULL != node)

160 {

161 bst_data_walk_inorder(node->left, op);

162 op(node->data);

163 bst_data_walk_inorder(node->right, op);

164 }

165 }

166

167 ////////////////////////////////////////////////////////////////////////////////

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

169 {

170 if (NULL != node)

171 {

172 bst_data_walk_postorder(node->left, op);

173 bst_data_walk_postorder(node->right, op);

174 op(node->data);

175 }

176 }

177

178 ////////////////////////////////////////////////////////////////////////////////

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

180 {

181 if (NULL != node)

182 {

183 op(node->data);

184 bst_data_walk_preorder(node->left, op);

185 bst_data_walk_preorder(node->right, op);

186 }

187 }

188

189 ////////////////////////////////////////////////////////////////////////////////

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

191 {

192 if (NULL != node)

193 {

194 bst_node_walk_postorder(node->left, op);

195 bst_node_walk_postorder(node->right, op);

196 op(node);

197 }

198 }

199

200 ////////////////////////////////////////////////////////////////////////////////

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

202 {

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

204 return NULL;

205

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

207 }

208

209 ////////////////////////////////////////////////////////////////////////////////

210 // Recursive

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

212 {

213 if (NULL == node)

214 return NULL;

215

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

217 return node->data;

218

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

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

221 else

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

223 }

224

225 ////////////////////////////////////////////////////////////////////////////////

226 // Iterative

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

228 {

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

230 return NULL;

231

232 struct bst_node * node = bst->root;

233 while (1)

234 {

235 if (NULL == node)

236 return NULL;

237

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

239 return node->data;

240

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

242 node = node->left;

243 else

244 node = node->right;

245 }

246 }

247

248 ////////////////////////////////////////////////////////////////////////////////

249 void * bst_minimum(struct bst * bst)

250 {

251 if (NULL == bst)

252 return NULL;

253

254 return bst_node_minimum(bst->root);

255 }

256

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

258 void * bst_node_minimum(struct bst_node * node)

259 {

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

261 node = node->left;

262 if (NULL == node)

263 return NULL;

264 return node->data;

265 }

266

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

268 void * bst_maximum(struct bst * bst)

269 {

270 if (NULL == bst)

271 return NULL;

272

273 return bst_node_maximum(bst->root);

274 }

275

276 ////////////////////////////////////////////////////////////////////////////////

277 void * bst_node_maximum(struct bst_node * node)

278 {

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

280 node = node->right;

281 if (NULL == node)

282 return NULL;

283 return node->data;

284 }

285

286 ////////////////////////////////////////////////////////////////////////////////

287 struct bst_iterator * bst_begin(struct bst * bst)

288 {

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

290 return NULL;

291

292 struct bst_node * min = bst->root;

293 while (min->left)

294 min = min->left;

295

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

297 if (NULL == it)

298 return NULL;

299

300 it->bst = bst;

301 it->curr = min;

302 return it;

303 }

304

305 ////////////////////////////////////////////////////////////////////////////////

306 struct bst_iterator * bst_end(struct bst * bst)

307 {

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

309 return NULL;

310

311 struct bst_node * max = bst->root;

312 while (max->right)

313 max = max->right;

314

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

316 if (NULL == it)

317 return NULL;

318

319 it->bst = bst;

320 it->curr = max;

321 return it;

322 }

323

324 ////////////////////////////////////////////////////////////////////////////////

325 struct bst_iterator * bst_next(struct bst_iterator * it)

326 {

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

328 return NULL;

329

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

331 {

332 struct bst_node * p = it->curr;

333 it->curr = it->curr->parent;

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

335 {

336 p = it->curr;

337 it->curr = it->curr->parent;

338 }

339

340 if (it->curr == NULL)

341 return NULL;

342 }

343 else

344 {

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

346 while (min->left)

347 min = min->left;

348 it->curr = min;

349 }

350 return it;

351 }

352

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

354 struct bst_iterator * bst_prev(struct bst_iterator * it)

355 {

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

357 return NULL;

358

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

360 {

361 struct bst_node * p = it->curr;

362 it->curr = it->curr->parent;

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

364 {

365 p = it->curr;

366 it->curr = it->curr->parent;

367 }

368

369 if (it->curr == NULL)

370 return NULL;

371 }

372 else

373 {

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

375 while (max->right)

376 max = max->right;

377 it->curr = max;

378 }

379 return it;

380 }

381

382 ////////////////////////////////////////////////////////////////////////////////

383 void * bst_value(struct bst_iterator * it)

384 {

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

386 return NULL;

387

388 return it->curr->data;

389 }

390

391 ////////////////////////////////////////////////////////////////////////////////

392 void *

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

394 {

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

396 return NULL;

397

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

399 }

400

401 ////////////////////////////////////////////////////////////////////////////////

402 // Recursive

403 struct bst_node *

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

405 {

406 if (NULL == node)

407 return NULL;

408

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

410 return node;

411

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

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

414 else

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

416 }

417

418 ////////////////////////////////////////////////////////////////////////////////

419 struct bst_node *

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

421 {

422 if (NULL == a)

423 return NULL;

424

425 if (NULL == a->parent)

426 bst->root = b;

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

428 a->parent->left = b;

429 else

430 a->parent->right = b;

431

432 if (NULL != b)

433 b->parent = a->parent;

434

435 return a;

436 }

437

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

439 void *

440 bst_remove(struct bst_iterator * it)

441 {

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

443 return NULL;

444

445 // Get successor and save it

446 struct bst_iterator succ;

447 succ.curr = it->curr;

448 succ.bst = it->bst;

449 bst_next(&succ);

450

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

452 {

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

454 }

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

456 {

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

458 }

459 else

460 {

461 struct bst_node * y = bst_node_minimum(it->curr->right);

462 if (y->parent != it->curr)

463 {

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

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

466 y->right->parent = y;

467 }

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

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

470 y->left->parent = y;

471 }

472

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

474 it->curr->data = NULL;

475 it->curr->left = NULL;

476 it->curr->right = NULL;

477 it->curr->parent = NULL;

478 free(it->curr);

479

480 // Update it to point to saved successor

481 it->curr = succ.curr;

482 it->bst->size--;

483

484 return data;

485 }

486

487 ////////////////////////////////////////////////////////////////////////////////

488 void

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

490 {

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

492 return;

493

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

495 }

496

497 ////////////////////////////////////////////////////////////////////////////////

498 void

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

500 {

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

502 printf("\t");

503 print_val(node->data);

504 printf("\n");

505 if (NULL != node->left)

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

507 if (NULL != node->right)

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

509 }

510

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

512 unsigned int

513 bst_size (struct bst * bst)

514 {

515 if (NULL == bst)

516 return 0;

517 return bst->size;

518 }

519

Mercurial > data_structures

view src/bst.c @ 12:d359966ed8de