各种树的平均查找效率

BST:二叉搜索树
查找最好时间复杂度为O(lgn),最坏为O(n);
删除和插入的时间复杂度与查找差不多

AVL:二叉平衡树
查找时间复杂度为O(lgn)
插入的时候做多需要一次旋转,时间复杂度为O(lgn)
删除的时候需要的时间复杂度为O(2lgn)

红黑树:
查找时间复杂度为2O(lg(n+1))
删除和插入的时间复杂度为O(lgn)

B树:
从叶节点插入心的节点,
从磁盘读写效率上讲,查找、删除和插入的时间复杂度要小于任何二叉树

B+树
非叶节点只是为了索引第一个节点
之后叶节点之间可以相互索引,大型数据库采用的结构

Jerky Lu wechat
欢迎加入微信公众号