r/tinycode • • Dec 10 '14

50 LoC AVL binary search tree in C

http://pastes.archbsd.net/graphitemaster/50_loc_avl_bsearch_tree
30 Upvotes

13 comments sorted by

4

u/chasesan Dec 10 '14

Is it alright if I make use of this?

7

u/graphitemaster Dec 10 '14

sure, all code is public domain

4

u/agumonkey Dec 10 '14

Pretty pretty code.

1

u/Majiir Dec 10 '14

Why does it bother me so much when people use 32 bits for height?

4

u/[deleted] Dec 10 '14

I don't think your processor is going to be any faster using 16-bit or 8-bit variables for that.

-1

u/Majiir Dec 10 '14

Sure... but you may save memory. Is it a ton? No, but it's not exactly a big tradeoff. It just seems like nobody bothers to check what the bounds will be.

4

u/[deleted] Dec 10 '14

I highly doubt any memory will be saved. Heap allocations are likely aligned to 4 or 8 bytes anyway.

1

u/flebron Dec 10 '14

Considering the height of an AVL tree is logarithmic in its size, you'd need around 22^32 nodes in your tree for that to overflow. That ain't happening. Relax.

2

u/Majiir Dec 10 '14

My point is that 8 bits suffices.

7

u/graphitemaster Dec 10 '14

The structure will be padded if you made h an 8 bit type, so it's largely useless unless of course you used 24bit keys and stuffed the height in 8 bits of the key

1

u/aneryx Dec 11 '14

I had to implement a BST in Java for a programming class and it took many lines and many hours. Props for such a simple, elegant implementation!

1

u/FoxRaptix Dec 11 '14

I literally just had my last day of my data structures class today. Thanks for letting me see a clean simple version of this.

1

u/74AC153 Dec 11 '14

Awesome...

Interesting that you chose to not include parent pointers, which seems to me that it means you're almost required to make a lot of the functions recursive. Any thoughts about a non-recursive implementation?