平衡树
平衡树是什么?
简单说,就是一颗二叉搜索树,并且它的深度保持相对稳定,也就是不会退化成链的树.
平衡树有什么用?
平衡树可以说是区间操作的数据结构中最好用的一种了吧,它最大的用处自然是维护区间了.
平衡树都有哪些呢?
平衡树的种类也是多种多样,因为有些在竞赛中可能实现起来比较麻烦 (请问您说的红黑树很难实现是什么意思?) ,这里就只介绍几个在竞赛中较为常用的了.
当然除了这些还有很多,比如AVL树,替罪羊树,SBT树等等,但是因为 (我也不会) 毕竟不需要懂这么多种的树,只需要学好splay或是无旋treap就能做的了绝大部分的区间维护的题目了,所以就不多赘述了.