stl::map的实现机制？
stl::map内部应该由有序平衡二叉树实现，只知道查找的时间复杂度是logN，不知插入、删除的时间复杂度怎样？
学校里学的东西全还给老师了，网上找了半天也没找到答案，望各位帮忙
问题点数：100、回复次数：1Top
1 楼plainsong（短歌)(）回复于 2003-10-03 18:49:37 得分 100
增、删、查都是O(log(N))。
不过一般现在流行的STL中都不使用平衡二叉树，而是使用红黑树，是一种不完全平衡的二分查找树。增删查也都是O(log(N))，不过增删操作比平衡二叉树要快得多，但查找稍慢（因为不完全平衡）。
关于红黑树的原理，我在这个贴子中谈到了一些：http://expert.csdn.net/Expert/TopicView1.asp?id=2317254
Top
