算法笔记 #3

2024年1月18日

Q1：搜索二叉树

A：查找，左子树比根几点小，右子树比根大。

? ? ? ? 删除：1）搜索删除的目标节点，记录其父节点；

? ? ? ? ? ? ? ? 2）左右孩子都为空，直接删掉；

? ? ? ? ? ? ? ? 3）左右孩子不全，父节点指针直接指向存在的孩子；删掉

? ? ? ? ? ? ? ? 4）左右孩子都全，左子树的最右节点或右子树最左节点来替换删掉的节点。

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

Q2：何为具有平衡性质的树（有序表）？

A：红黑树、AVL、SB树（size balance）、跳表（skip list）（复杂度相同）

? ? ? ? 平衡搜索二叉树

? ? ? ? 默认搜索二叉树没有重复节点，可以将相同的数据压缩到一个节点上。

? ? ? ? AVL树：任何一个节点的左右子树高度差不大于1；

Q3：平衡搜索二叉树的左旋和右旋

A：

? ? ? ? 左旋和右旋是根节点倒向哪边就是向哪旋。

????????

Q4：AVL树何时检查平衡性？

A：每次加入节点后，都向上检查节点是否有平衡性。

? ? ? ? 删除节点后，从替代被删除节点的那个节点向上的位置开始查是否平衡。

Q5：AVL树怎么检查平衡性，如何处理？

A：破坏平衡性的四种情况。

? ? ? ? 1）LL、RR：左（右）孩子的左（右）子树过长；向相反方向旋转一次

? ? ? ? 2）LR、RL：左（右）孩子的右（左）子树过长；LR（RL）处理，令左（右）孩子的右（左）孩子成为头部。