data_structures: 6605a342e8f8 src/bst.c

view src/bst.c @ 8:6605a342e8f8

bst working, but not elegant

author	Eris Caffee <discordia@eldalin.com>
date	Thu, 27 Sep 2012 10:57:41 -0500
parents	b38243d51aea
children	abdba37f67a2

line source

1 #include <stdio.h>

2 #include <stdlib.h>

4 #include "bst.h"

6 // Private functions.

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

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

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

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

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

14 void * bst_node_minimum(struct bst_node * node);

15 void * bst_node_maximum(struct bst_node * node);

16 void bst_node_free(struct bst_node * node);

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

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

22 ////////////////////////////////////////////////////////////////////////////////

23 struct bst *

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

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

26 {

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

28 return NULL;

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

31 if (NULL == bst)

32 return NULL;

34 bst->root = NULL;

35 bst->size = 0;

36 bst->le = le;

37 bst->eq = eq;

38 return bst;

39 }

42 ////////////////////////////////////////////////////////////////////////////////

43 void

44 bst_delete(struct bst * bst)

45 {

46 if (NULL == bst) return;

47 if (0 < bst->size)

48 {

49 // Walk the tree and delete the nodes.

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

51 // emptied the tree.

52 bst_node_walk_postorder(bst->root, bst_node_free);

53 }

54 free(bst);

55 }

57 ////////////////////////////////////////////////////////////////////////////////

58 void

59 bst_node_free(struct bst_node * node)

60 {

61 free(node);

62 }

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

65 void *

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

67 {

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

69 return NULL;

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

72 if (NULL == new)

73 return NULL;

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

75 new->data = data;

77 if (NULL == bst->root)

78 {

79 bst->root = new;

80 return new->data;

81 }

83 struct bst_node * p = NULL;

84 struct bst_node * c = bst->root;

86 while (NULL != c)

87 {

88 p = c;

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

90 c = c->left;

91 else

92 c = c->right;

93 }

94 new->parent = p;

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

96 p->left = new;

97 else

98 p->right = new;

100 bst->size++;

101 return new->data;

102 }

103

104

105 ////////////////////////////////////////////////////////////////////////////////

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

107 {

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

109 return;

110

111 bst_data_walk_inorder(bst->root, op);

112 }

113

114 ////////////////////////////////////////////////////////////////////////////////

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

116 {

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

118 return;

119

120 bst_data_walk_postorder(bst->root, op);

121 }

122

123 ////////////////////////////////////////////////////////////////////////////////

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

125 {

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

127 return;

128

129 bst_data_walk_preorder(bst->root, op);

130 }

131

132 ////////////////////////////////////////////////////////////////////////////////

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

134 {

135 if (NULL != node)

136 {

137 bst_data_walk_inorder(node->left, op);

138 op(node->data);

139 bst_data_walk_inorder(node->right, op);

140 }

141 }

142

143 ////////////////////////////////////////////////////////////////////////////////

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

145 {

146 if (NULL != node)

147 {

148 bst_data_walk_postorder(node->left, op);

149 bst_data_walk_postorder(node->right, op);

150 op(node->data);

151 }

152 }

153

154 ////////////////////////////////////////////////////////////////////////////////

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

156 {

157 if (NULL != node)

158 {

159 op(node->data);

160 bst_data_walk_preorder(node->left, op);

161 bst_data_walk_preorder(node->right, op);

162 }

163 }

164

165 ////////////////////////////////////////////////////////////////////////////////

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

167 {

168 if (NULL != node)

169 {

170 bst_node_walk_postorder(node->left, op);

171 bst_node_walk_postorder(node->right, op);

172 op(node);

173 }

174 }

175

176 ////////////////////////////////////////////////////////////////////////////////

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

178 {

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

180 return NULL;

181

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

183 }

184

185 ////////////////////////////////////////////////////////////////////////////////

186 // Recursive

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

188 {

189 if (NULL == node)

190 return NULL;

191

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

193 return node->data;

194

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

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

197 else

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

199 }

200

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

202 // Iterative

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

204 {

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

206 return NULL;

207

208 struct bst_node * node = bst->root;

209 while (1)

210 {

211 if (NULL == node)

212 return NULL;

213

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

215 return node->data;

216

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

218 node = node->left;

219 else

220 node = node->right;

221 }

222 }

223

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

225 void * bst_minimum(struct bst * bst)

226 {

227 if (NULL == bst)

228 return NULL;

229

230 return bst_node_minimum(bst->root);

231 }

232

233 ////////////////////////////////////////////////////////////////////////////////

234 void * bst_node_minimum(struct bst_node * node)

235 {

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

237 node = node->left;

238 if (NULL == node)

239 return NULL;

240 return node->data;

241 }

242

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

244 void * bst_maximum(struct bst * bst)

245 {

246 if (NULL == bst)

247 return NULL;

248

249 return bst_node_maximum(bst->root);

250 }

251

252 ////////////////////////////////////////////////////////////////////////////////

253 void * bst_node_maximum(struct bst_node * node)

254 {

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

256 node = node->right;

257 if (NULL == node)

258 return NULL;

259 return node->data;

260 }

261

262 ////////////////////////////////////////////////////////////////////////////////

263 struct bst_iterator * bst_begin(struct bst * bst)

264 {

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

266 return NULL;

267

268 struct bst_node * min = bst->root;

269 while (min->left)

270 min = min->left;

271

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

273 if (NULL == it)

274 return NULL;

275

276 it->bst = bst;

277 it->curr = min;

278 return it;

279 }

280

281 ////////////////////////////////////////////////////////////////////////////////

282 struct bst_iterator * bst_end(struct bst * bst)

283 {

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

285 return NULL;

286

287 struct bst_node * max = bst->root;

288 while (max->right)

289 max = max->right;

290

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

292 if (NULL == it)

293 return NULL;

294

295 it->bst = bst;

296 it->curr = max;

297 return it;

298 }

299

300 ////////////////////////////////////////////////////////////////////////////////

301 struct bst_iterator * bst_next(struct bst_iterator * it)

302 {

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

304 return NULL;

305

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

307 {

308 struct bst_node * p = it->curr;

309 it->curr = it->curr->parent;

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

311 {

312 p = it->curr;

313 it->curr = it->curr->parent;

314 }

315

316 if (it->curr == NULL)

317 return NULL;

318 }

319 else

320 {

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

322 while (min->left)

323 min = min->left;

324 it->curr = min;

325 }

326 return it;

327 }

328

329 ////////////////////////////////////////////////////////////////////////////////

330 struct bst_iterator * bst_prev(struct bst_iterator * it)

331 {

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

333 return NULL;

334

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

336 {

337 struct bst_node * p = it->curr;

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

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

340 {

341 p = it->curr;

342 it->curr = it->curr->parent;

343 }

344

345 if (it->curr == NULL)

346 return NULL;

347 }

348 else

349 {

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

351 while (max->right)

352 max = max->right;

353 it->curr = max;

354 }

355 return it;

356 }

357

358 ////////////////////////////////////////////////////////////////////////////////

359 void * bst_value(struct bst_iterator * it)

360 {

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

362 return NULL;

363

364 return it->curr->data;

365 }

366

367 ////////////////////////////////////////////////////////////////////////////////

368 void *

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

370 {

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

372 return NULL;

373

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

375 }

376

377 ////////////////////////////////////////////////////////////////////////////////

378 // Recursive

379 struct bst_node *

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

381 {

382 if (NULL == node)

383 return NULL;

384

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

386 return node;

387

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

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

390 else

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

392 }

393

394 ////////////////////////////////////////////////////////////////////////////////

395 struct bst_node *

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

397 {

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

399 return NULL;

400

401 if (NULL == a->parent)

402 bst->root = b;

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

404 a->parent->left = b;

405 else

406 a->parent->right = b;

407

408 if (NULL != b)

409 b->parent = a->parent;

410

411 return a;

412 }

413

414 ////////////////////////////////////////////////////////////////////////////////

415 void *

416 bst_remove(struct bst_iterator * it)

417 {

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

419 return NULL;

420

421 struct bst_node * y;

422

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

424 {

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

426 y = it->curr->right;

427 }

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

429 {

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

431 y = it->curr->left;

432 }

433 else

434 {

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

436 if (NULL != y->parent)

437 {

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

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

440 y->right->parent = y;

441 }

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

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

444 y->left->parent = y;

445 }

446

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

448 free(it->curr);

449 it->curr = y;

450 return data;

451 }

452

Mercurial > data_structures

view src/bst.c @ 8:6605a342e8f8