【数据结构】—— chapter 05 树与二叉树的应用 (part4)
文章目录
5.5 树与二叉树的应用
5.5.1 二叉排序树(BST)
1. 定义
2. 查找操作
3. 插入操作
4. 构造
5. 删除操作
先搜索目标结点,可能会遇到三种情况,如下:
Case 1:
Case 2:
Case 3:
6. 查询效率分析
7. 小结
5.5.2 平衡二叉树(AVL)
1. 定义
2. 插入操作
3. 插入新结点后如何调整"不平衡"问题
(1)LL型:
(2)RR型:
(3)代码思路:
(4)LR型:
(5)RL型:
(6)小结:
(7)练习: