淘宝网站用什么语言做的,看网站用什么软件,深圳商城网站建设报价,无锡网站建设公司排名二叉树#xff1a;
满二叉树#xff1a;每一层的节点都达到最大值#xff0c;如果树高h#xff0c;节点总数有2^h-1。 完全二叉树#xff1a;树高为h#xff0c;前h-1层节点都是最大值#xff0c;最后一层h不满且从左到右连续。
存储方式#xff1a;顺序存储#xf…二叉树
满二叉树每一层的节点都达到最大值如果树高h节点总数有2^h-1。 完全二叉树树高为h前h-1层节点都是最大值最后一层h不满且从左到右连续。
存储方式顺序存储数组和链式存储链表。
二叉搜索树
特点左节点值跟节点的值右节点值跟节点的值左右子树都是二叉搜索树中序遍历是升序。
增删改查效率因为增删改前都需要查询节点值所以查询的时间复杂度就是增删改的时间复杂度最好时间复杂度是Ologn最坏时间复杂度是On是因为退化成链表了。
删除操作ps删除情况多较重要而增删改都是递归操作
删除根节点特判一下是根节点然后找寻左子树的最大节点或者右子树的最小节点进行替换删除。删除孩子节点该孩子节点的父节点指向nullptr即可。删除中间节点托孤该中间节点的父亲领养一个或两个孙子。
平衡二叉树AVL
特点首先平衡二叉树的前提是二叉搜索树中序遍历有序说明是二叉搜索树且每个节点的左右子树的高度差绝对值平衡因子不超过1。
优点时间复杂度为O(logN)解决了二叉搜索树成为链表的缺点因为平衡因子使节点均匀分布降低了树的高度提高查询效率。
缺点如果对AVL树做一些结构修改插入删除等操作性能是十分低下的因为保证平衡因子需要多次旋转最差的情况是可能一直要旋转持续到根的位置。
ps旋转分四种情况左旋右旋、左右双旋、右左双旋。
红黑树
是一个自平衡的二叉搜索树在插入和删除后能够通过左旋和右旋以及重新着色保持树的平衡增删查的时间复杂度是Ologn
特点
每个节点都有颜色黑色或者红色。跟节点和叶子节点都为黑色。红色节点的左右孩子节点都为黑色。跟节点到叶子节点上黑色节点的个数一致。
红黑树和平衡二叉树的比较
查询选平衡二叉树
插删选红黑树
平衡二叉树的平衡规则相比于红黑树要严格所以红黑树的高度会略高于平衡二叉树所以平衡二叉树查询的时间复杂度要快一些。当插入和删除操作进行时平衡二叉树需要多次旋转达到严格的平衡规则而红黑树的平衡规则不算严格所以最多需要两次旋转就可以达到平衡状态所以黑红树插入和删除的时间复杂度要快一些。
前缀树
特点
除了根节点外每个节点都包含一个字符每个节点的所有子节点包含的字符不同从根节点到某节点字符连接起来可以形成该节点的字符串
应用利用字符串的公共前缀来减少查询时间减少无所谓的字符比较从而提高查询效率
B树
B树是一个平衡多叉树为什么不采用AVL树存储MySQL的索引文件呢是因为随着索引文件增多AVL树的树高会逐渐变高那么根据索引读取数据的速度取决于磁盘IO次数也就是树的高度一次磁盘IO读取一个节点采用B树也就是平衡多叉树可以降低树的高度减少磁盘IO的次数提高效率。
特点
叶子节点和非叶子节点都存储着索引键值key和数据data。
B树的范围查询是中序遍历没B树好。
B树
B树是MySQL关系型数据库innodb存储引擎下的存储索引文件的数据结构。首先它也是一个平衡多叉树那为什么选择它呢因为B只有叶子节点存储索引键值key和数据data非叶子节点存储的都是键值key所以B树的高度要比B树还要矮磁盘IO次数更少查询效率更高。
特点
叶子节点存储键值和数据非叶子节点只存储键值。
B树的范围查询依靠叶子节点之间形成的双向链表。
ps
所以B树的范围查询比B树的中序遍历效率高太多B树用于MySQL的innodb存储引擎而B树可以考虑单个索引的查询用于nosql的MongoDB存储引擎。
