平衡二叉树（AVL树）

红黑树是在AVL树的基础上提出来的。

平衡二叉树又称为AVL树，是一种特殊的二叉排序树。

其左右子树都是平衡二叉树，且左右子树高度之差不超过1。

红黑树较AVL树的优点

AVL 树是高度平衡的，频繁的插入和删除，会引起频繁的rebalance，导致效率下降；

红黑树不是高度平衡的，算是一种折中，插入最多两次旋转，删除最多三次旋转。

所以红黑树在查找，插入删除的性能都是O(logn)，且性能稳定，所以STL里面很多结构包括set、map底层实现都是使用的红黑树。

字典树

性质：

1. 根节点不保存字符，每个结点保存一个字符
2. 从根节点到某一节点。路径上经过的字符连接起来，就是该节点对应的字符串
3. 每个节点的所有子节点包含的字符都不相同

应用：统计，排序，保存大量字符串

优点：利用字符的公共前缀减少查询时间，最大限度的减少无谓的字符串比较

二叉树

原图链接：「代码随想录」知识星球