二叉搜索树：所有左孩子都比节点自身小(或相等), 右孩子都比节点自身大,
平衡二叉树（AVL树）：自平衡二叉查找树。除了有二叉搜索树的特点外，任一节点对应的两棵子树的最大高度差为1。
红黑树：除了对二叉搜索树施加的要求之外，红黑树还必须满足以下要求：

每个节点都是红色或黑色。

根是黑色的。有时会省略此规则。由于根始终可以从红色变为黑色，但不一定相反，因此该规则对分析几乎没有影响。

所有叶子（NIL）都是黑色的。

如果节点为红色，则其子节点均为黑色。

从给定节点到其任何后代NIL节点的每条路径都包含相同数量的黑色节点。

这些约束强制执行红黑树的关键属性：从根到最远叶子的路径不超过从根到最近叶子的路径的两倍。结果是树大致高度平衡。由于诸如插入，删除和查找值之类的操作需要与树的高度成比例的最坏情况时间，因此高度的理论上限允许红黑树在最坏的情况下是有效的，这与普通的二叉搜索树不同。

常用数据结构及算法复杂度

AVL树和红黑树

https://pub.dev/packages/dart_tree
在线演示：https://lbxjixiangniao.github.io/build/web/#/

伸展树 _SplayTree

https://zh.wikipedia.org/wiki/%E4%BC%B8%E5%B1%95%E6%A0%91

伸展树（英语：Splay Tree）是一种能够自我平衡的二叉查找树，它能在O(log n)内完成插入、查找和删除操作。

在伸展树上的一般操作都基于伸展操作：假设想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法，在每次查找之后对树进行调整，把被查找的条目搬移到离树根近一些的地方。伸展树应运而生。伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。

_SplayTree的插入和删除都会将相应节点搬移到树根去。如新插入的点就是根节点；删除操作前先将要删除的节点搬移到树根去，然后再删除。

SplayTreeMap

class SplayTreeMap<K, V> extends _SplayTree<K, _SplayTreeMapNode<K, V>> with MapMixin<K, V>
用key来进行排序比较

SplayTreeSet

class SplayTreeSet<E> extends _SplayTree<E, _SplayTreeNode<E>> with IterableMixin<E>, SetMixin<E>
直接用值来进行排序比较
拓展: OrderedSet

flutter 的游戏框架flame使用OrderedSet来存储游戏中渲染的组件。
与SplayTreeSet 的区别是可以存储compare相等的元素。SplayTreeSet中不能存compare相等的元素。

哈希表 HashTable

https://en.wikipedia.org/wiki/Hash_table

算法最差情况出现在所有key通过hash function计算后得到同样的结果
dart中的基于HashTable实现的Set和Map如下
Map：HashMap、LinkedHashMap（Map的默认实现）
Set：HashSet、LinkedHashSet（Set的默认实现）
LinkedHashMap、LinkedHashSet会跟踪元素的插入顺序，并按插入顺序进行遍历。

hash_table.png

数组 List

数组如果在最后面增删，其算法时间复杂度为O(1)，因为在最后面增删不用移动或者拷贝数组内其他元素

数据排序算法

此处只讨论List的排序方法void sort([int compare(E a, E b)]);List使用的排序算法为双轴快速排序。双轴快速排序的时间复杂度和单轴的时间复杂度表达式一样，只是常数因子要小一些
https://github.com/dart-lang/sdk/blob/da0363172adaa266ef2d44cf87e09b61a185e79d/sdk/lib/internal/sort.dart

单轴快速排序：

快速排序的基本思想就是从一个数组中任意挑选一个元素（通常来说会选择最左边的元素）作为中轴元素，将剩下的元素以中轴元素作为比较的标准，将小于等于中轴元素的放到中轴元素的左边，将大于中轴元素的放到中轴元素的右边，然后以当前中轴元素的位置为界，将左半部分子数组和右半部分子数组看成两个新的数组，重复上述操作，直到子数组的元素个数小于等于1（因为一个元素的数组必定是有序的）。

双轴快速排序：

双枢轴快速排序的想法是采用两个枢轴，一个在阵列的左端，第二个在阵列的右端。左枢轴必须小于或等于右枢轴，因此如有必要，我们将其交换。
然后，我们开始将数组划分为三个部分：在第一部分中，所有元素都将小于左枢轴，在第二部分中，所有元素都将大于或等于左枢轴，并且还将小于或等于右枢轴，在第三部分中，所有元素都将大于右枢轴。然后，我们将两个枢轴移动到其合适的位置，如下图所示，然后，我们开始使用此方法对这三个部分进行递归快速排序。

双链表 LinkedList

队列 Queue<E>

Queue<E>两端都可以进行增删操作

查找算法

collection提供了有序数组的二分查找算法
参考：https://www.cnblogs.com/shine-lee/p/11913229.html
https://www.bigocheatsheet.com/

总结

数组：数组对比其他数据结构主要优点是下标索引查找快，时间复杂度为O(1)
哈希表：增删改查都很快，但是浪费空间
链表：优点是增删时间复杂度为O(1)
AVL树：对比红黑树的优点是查找快
红黑树：对比AVL树的优点是增删更快

flutter 数据结构及算法复杂度