data_structures: abdba37f67a2 src/bst.c

view src/bst.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	6605a342e8f8
children	68f85ffc6029

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

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

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

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

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

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

36 void * bst_node_minimum(struct bst_node * node);

37 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);

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

44 ////////////////////////////////////////////////////////////////////////////////

45 struct bst *

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

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

48 {

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

50 return NULL;

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

53 if (NULL == bst)

54 return NULL;

56 bst->root = NULL;

57 bst->size = 0;

58 bst->le = le;

59 bst->eq = eq;

60 return bst;

61 }

64 ////////////////////////////////////////////////////////////////////////////////

65 void

66 bst_delete(struct bst * bst)

67 {

68 if (NULL == bst) return;

69 if (0 < bst->size)

70 {

71 // Walk the tree and delete the nodes.

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

73 // emptied the tree.

74 bst_node_walk_postorder(bst->root, bst_node_free);

75 }

76 free(bst);

77 }

79 ////////////////////////////////////////////////////////////////////////////////

80 void

81 bst_node_free(struct bst_node * node)

82 {

83 free(node);

84 }

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

87 void *

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

89 {

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

91 return NULL;

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

94 if (NULL == new)

95 return NULL;

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

97 new->data = data;

99 if (NULL == bst->root)

100 {

101 bst->root = new;

102 bst->size = 1;

103 return new->data;

104 }

105

106 struct bst_node * p = NULL;

107 struct bst_node * c = bst->root;

108

109 while (NULL != c)

110 {

111 p = c;

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

113 c = c->left;

114 else

115 c = c->right;

116 }

117 new->parent = p;

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

119 p->left = new;

120 else

121 p->right = new;

122

123 bst->size++;

124 return new->data;

125 }

126

127

128 ////////////////////////////////////////////////////////////////////////////////

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

130 {

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

132 return;

133

134 bst_data_walk_inorder(bst->root, op);

135 }

136

137 ////////////////////////////////////////////////////////////////////////////////

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

139 {

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

141 return;

142

143 bst_data_walk_postorder(bst->root, op);

144 }

145

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

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

148 {

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

150 return;

151

152 bst_data_walk_preorder(bst->root, op);

153 }

154

155 ////////////////////////////////////////////////////////////////////////////////

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

157 {

158 if (NULL != node)

159 {

160 bst_data_walk_inorder(node->left, op);

161 op(node->data);

162 bst_data_walk_inorder(node->right, op);

163 }

164 }

165

166 ////////////////////////////////////////////////////////////////////////////////

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

168 {

169 if (NULL != node)

170 {

171 bst_data_walk_postorder(node->left, op);

172 bst_data_walk_postorder(node->right, op);

173 op(node->data);

174 }

175 }

176

177 ////////////////////////////////////////////////////////////////////////////////

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

179 {

180 if (NULL != node)

181 {

182 op(node->data);

183 bst_data_walk_preorder(node->left, op);

184 bst_data_walk_preorder(node->right, op);

185 }

186 }

187

188 ////////////////////////////////////////////////////////////////////////////////

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

190 {

191 if (NULL != node)

192 {

193 bst_node_walk_postorder(node->left, op);

194 bst_node_walk_postorder(node->right, op);

195 op(node);

196 }

197 }

198

199 ////////////////////////////////////////////////////////////////////////////////

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

201 {

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

203 return NULL;

204

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

206 }

207

208 ////////////////////////////////////////////////////////////////////////////////

209 // Recursive

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

211 {

212 if (NULL == node)

213 return NULL;

214

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

216 return node->data;

217

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

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

220 else

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

222 }

223

224 ////////////////////////////////////////////////////////////////////////////////

225 // Iterative

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

227 {

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

229 return NULL;

230

231 struct bst_node * node = bst->root;

232 while (1)

233 {

234 if (NULL == node)

235 return NULL;

236

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

238 return node->data;

239

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

241 node = node->left;

242 else

243 node = node->right;

244 }

245 }

246

247 ////////////////////////////////////////////////////////////////////////////////

248 void * bst_minimum(struct bst * bst)

249 {

250 if (NULL == bst)

251 return NULL;

252

253 return bst_node_minimum(bst->root);

254 }

255

256 ////////////////////////////////////////////////////////////////////////////////

257 void * bst_node_minimum(struct bst_node * node)

258 {

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

260 node = node->left;

261 if (NULL == node)

262 return NULL;

263 return node->data;

264 }

265

266 ////////////////////////////////////////////////////////////////////////////////

267 void * bst_maximum(struct bst * bst)

268 {

269 if (NULL == bst)

270 return NULL;

271

272 return bst_node_maximum(bst->root);

273 }

274

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

276 void * bst_node_maximum(struct bst_node * node)

277 {

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

279 node = node->right;

280 if (NULL == node)

281 return NULL;

282 return node->data;

283 }

284

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

286 struct bst_iterator * bst_begin(struct bst * bst)

287 {

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

289 return NULL;

290

291 struct bst_node * min = bst->root;

292 while (min->left)

293 min = min->left;

294

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

296 if (NULL == it)

297 return NULL;

298

299 it->bst = bst;

300 it->curr = min;

301 return it;

302 }

303

304 ////////////////////////////////////////////////////////////////////////////////

305 struct bst_iterator * bst_end(struct bst * bst)

306 {

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

308 return NULL;

309

310 struct bst_node * max = bst->root;

311 while (max->right)

312 max = max->right;

313

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

315 if (NULL == it)

316 return NULL;

317

318 it->bst = bst;

319 it->curr = max;

320 return it;

321 }

322

323 ////////////////////////////////////////////////////////////////////////////////

324 struct bst_iterator * bst_next(struct bst_iterator * it)

325 {

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

327 return NULL;

328

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

330 {

331 struct bst_node * p = it->curr;

332 it->curr = it->curr->parent;

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

334 {

335 p = it->curr;

336 it->curr = it->curr->parent;

337 }

338

339 if (it->curr == NULL)

340 return NULL;

341 }

342 else

343 {

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

345 while (min->left)

346 min = min->left;

347 it->curr = min;

348 }

349 return it;

350 }

351

352 ////////////////////////////////////////////////////////////////////////////////

353 struct bst_iterator * bst_prev(struct bst_iterator * it)

354 {

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

356 return NULL;

357

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

359 {

360 struct bst_node * p = it->curr;

361 it->curr = it->curr->parent;

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

363 {

364 p = it->curr;

365 it->curr = it->curr->parent;

366 }

367

368 if (it->curr == NULL)

369 return NULL;

370 }

371 else

372 {

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

374 while (max->right)

375 max = max->right;

376 it->curr = max;

377 }

378 return it;

379 }

380

381 ////////////////////////////////////////////////////////////////////////////////

382 void * bst_value(struct bst_iterator * it)

383 {

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

385 return NULL;

386

387 return it->curr->data;

388 }

389

390 ////////////////////////////////////////////////////////////////////////////////

391 void *

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

393 {

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

395 return NULL;

396

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

398 }

399

400 ////////////////////////////////////////////////////////////////////////////////

401 // Recursive

402 struct bst_node *

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

404 {

405 if (NULL == node)

406 return NULL;

407

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

409 return node;

410

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

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

413 else

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

415 }

416

417 ////////////////////////////////////////////////////////////////////////////////

418 struct bst_node *

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

420 {

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

422 return NULL;

423

424 if (NULL == a->parent)

425 bst->root = b;

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

427 a->parent->left = b;

428 else

429 a->parent->right = b;

430

431 if (NULL != b)

432 b->parent = a->parent;

433

434 return a;

435 }

436

437 ////////////////////////////////////////////////////////////////////////////////

438 void *

439 bst_remove(struct bst_iterator * it)

440 {

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

442 return NULL;

443

444 struct bst_node * y;

445

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

447 {

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

449 y = it->curr->right;

450 }

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

452 {

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

454 y = it->curr->left;

455 }

456 else

457 {

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

459 if (NULL != y->parent)

460 {

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

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

463 y->right->parent = y;

464 }

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

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

467 y->left->parent = y;

468 }

469

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

471 free(it->curr);

472 it->curr = y;

473 return data;

474 }

475

Mercurial > data_structures

view src/bst.c @ 9:abdba37f67a2