目录
1. AVL树
2.伸展树
3.红黑树
4.二叉查找树
5.替罪羊树
AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)。
伸展树(Splay Tree)，也叫分裂树，是一种二叉排序树，它能在O(log n)内完成插入、查找和删除操作。伸展树支持所有的二叉树操作。伸展树不保证最坏情况下的时间复杂度为O(logN)。伸展树的时间复杂度边界是均摊的。
红黑树(Red Black Tree) 是一种自平衡二叉查找树，它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除，这里的 是树中元素的数目。
二叉查找树中查询元素的最优时间复杂度是O(logN)即在满二叉树的情况下,最坏时间复杂度是O(n)即除叶子节点外每个节点只有一个子节点
替罪羊树是计算机科学中，一种基于部分重建的自平衡二叉搜索树。在替罪羊树上，插入或删除节点的平摊最坏时间复杂度是O(log n)，搜索节点的最坏时间复杂度是O(log n)。
人工智能博士 认证博客专家 985AI博士 AI专家 博客专家 王博Kings，985AI博士在读，博客专家，华为云专家，是《机器学习手推笔记》、《深度学习手推笔记》等作者，我的微信：Kingsplusa，欢迎交流学习；在人工智能、计算机视觉、无人驾驶等具有丰富的经验。