Base Binary Tree implementation

Heyooo, I'm currently working on implementing a few sets of binary trees, and I was thinking that perhaps the simple binary tree, shouldn't be the default implementation (I'll be implementing threaded and non-threaded varients of AVL Tree's and Red Black tree's so far...). So the question them comes -- what should I use for my base implementation? I'm currently debating between (threaded and non-threaded varients including) AVL tree's and Red-Black tree's. However, any other thoughts are welcome as well. Comments, Questions? -Sterling Ps: I have a C btree implementation lying around -- does anyone think I should put this into the extension, a btree seems overkill for PHP, but I'm always up to suggestions...