19-数据结构与算法面试题-重点.docx
7 浏览量
2023-08-22
22:39:59
上传
评论
收藏 324KB DOCX 举报
（1） 红黑树的了解（平衡树，二叉搜索树），使用
场景
把数据结构上几种树集中的讨论一下：
1.
AVLtree
定义：最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最
大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况
下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个
树。
节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有
平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是
不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从
可能存储在节点中的子树高度计算出来。
一般我们所看见的都是排序平衡二叉树。
AVLtree使用场景：AVL树适合用于插入删除次数比较少，但查找多的情况。插
入删除导致很多的旋转，旋转是非常耗时的。AVL 在linux内核的vm area中使
用。
2.
二叉搜索树
二叉搜索树也是一种树，适用与一般二叉树的全部操作，但二叉搜索树能够实现
数据的快速查找。
二叉搜索树满足的条件：
1.非空左子树的所有键值小于其根节点的键值
2.非空右子树的所有键值大于其根节点的键值
3.左右子树都是二叉搜索树
二叉搜索树的应用场景：如果是没有退化称为链表的二叉树，查找效率就是
lgn，效率不错，但是一旦退换称为链表了，要么使用平衡二叉树，或者之后的
RB树，因为链表就是线性的查找效率。
3.
红黑树的定义
剩余15页未读，继续阅读
资源评论
