Where to find balanced tree implementation?

I was wondering whether anyone knows of somewhere on the Internet where I can copy-and-paste (for learning purposes) an implementation of a binary search tree that implements both balancing and an algorithm to ask how many nodes are less than a particular value. I want to be able to query this data structure and ask "How many nodes are < x in this data structure?" The whole purpose is to answer this latter type of query, but the balancing is important too because I want to be able to handle large unbalanced sequences of entries.

I prefer implementations in Python, 开发者_如何学编程C, C++, or Java, but others are welcome.

---

If it's still relevant, you could maintain in each node the size of the subtree, like in

http://www.codeproject.com/script/Articles/ViewDownloads.aspx?aid=12347&zep=HeightBalancedTree.h&rzp=%2fKB%2farchitecture%2favl_cpp%2f%2favl_cpp.zip

Notice the FindComparable function. If the object is found, it returns its index (the number of nodes that are smaller than the searched object).

In case the searched object is not in the tree, you want to get the index of the minimal node that is larger than the searched object.

Notice what happens to the index when the object is not found. The last Node::GetSize(Node::GetRight(node))) or Node::GetSize(Node::GetLeft(node))) will be evaluated to 0, so you have 2 cases:

• If the last turn was right (cmp > 0) you will get the index of the maximal node that is smaller than the searched object plus one - which is exactly the value that you want.
• If the last turn was left (cmp < 0) you will get the index of the minimal node that is larger than the searched object minus one.

Therefore, instead of returning Size() when the object was not found, you could return:

index + (cmp < 0)?1:0;