第四课《长歪的大树——BST退化危机》故事开始魔法图书馆出大事了1、经过前三课。魔法图书馆已经越来越厉害了同学们已经学会BST搜索BST插入BST遍历大家都觉得“BST天下无敌”2、可是有一天……图书管理员爷爷突然哭了“搜索变慢了”3、同学们很震惊“不可能呀”BST不是很快吗4、爷爷说“以前找书只要几秒。”“现在找一本书要跑半个图书馆”5、到底发生了什么今天。我们就来揭开⚔️BST最大的危机⚔️树退化Degenerate第一部分正常的BST长什么样1、先看一棵健康的BST8 / \ 3 10 / \ \ 1 6 142、为什么它快因为每次比较。都能排除一大片3、例如找148 → 10 → 14只走3步4、这棵树像什么像一棵自然生长张开的大树左右都比较均匀。第二部分危险的插入顺序1、有一天。来了几本新书1 2 3 4 5注意它们是按顺序来的2、图书管理员开始插入。插入11插入2因为2 1所以1 \ 2插入33 1 3 2继续右边。结果1 \ 2 \ 3插入4继续右边。1 \ 2 \ 3 \ 4插入5最后1 \ 2 \ 3 \ 4 \ 53、大事不好了树长歪了第三部分什么叫“退化”1、原来的BST8 / \ 3 10像真正的大树2、现在的BST1 \ 2 \ 3像电线杆3、这就叫BST退化4、退化是什么意思原本树慢慢变成链表5、结果会怎样搜索速度大大变慢第四部分为什么会变慢原来找51、正常BST可能8 → 6 → 5很快。2、退化后必须1 → 2 → 3 → 4 → 5一个一个走3、这不就和顺序查找一样了吗4、BST的魔法消失了因为无法“排除一大片”第五部分为什么会退化1、原因其实很简单插入顺序太特殊2、例如1 2 3 4 5每次都往右。3、或者5 4 3 2 1每次都往左。4、树就会越长越歪第六部分平衡思想登场算法国王召开紧急会议1、算法科学家发现真正重要的不只是BST而是“树要平衡”2、什么叫平衡例如4 / \ 2 6 / \ / \ 1 3 5 7左右高度差不多。这就叫平衡树3、为什么平衡很重要因为搜索时每次都能快速缩小范围第七部分生活中的例子例子1图书馆书架1、如果所有书全堆一排。找书很慢。2、但如果分成左边中间右边会快很多例子2猜数字1、如果每次都猜中间会很快。2、如果每次都只猜旁边就会很慢。3、BST也是一样第八部分算法世界的升级后来。算法科学家发明了1、AVL树会自动保持平衡。2、红黑树更强大的平衡树。3、很多生活中的程序地图导航数据库游戏系统都在用第九部分观察实验现场演示。实验1好树插入4 2 6 1 3 5 7形成4 / \ 2 6很平衡。实验2坏树插入1 2 3 4 5 6 7形成1 \ 2 \ 3长歪。然后比较搜索次数第十部分程序演示1、构建退化BST#include iostream using namespace std; struct Node { int val; Node* left; Node* right; Node(int x) { val x; left NULL; right NULL; } }; Node* insert(Node* root, int x) { if(root NULL) { return new Node(x); } if(x root-val) { root-left insert(root-left, x); } else if(x root-val) { root-right insert(root-right, x); } return root; } // 中序遍历 void inorder(Node* root) { if(root NULL) { return; } inorder(root-left); cout root-val ; inorder(root-right); } int main() { Node* root NULL; // 按顺序插入 for(int i 1; i 7; i) { root insert(root, i); } cout 中序遍历 endl; inorder(root); return 0; }2、程序虽然没错输出1 2 3 4 5 6 73、但树已经严重退化第十一部分课堂互动小游戏游戏1谁是健康树老师画两棵树。让孩子判断哪棵平衡哪棵退化游戏2真人长树孩子们按顺序站队1 2 3 4 5会形成“电线杆”。再换顺序4 2 6 1 3 5 7会形成平衡树。孩子会特别直观第十二部分今天重要的思想BST算法也会“变笨”BST不是永远都快。数据的排列方式会影响效率这是需要理解的算法思想。第十三部分本课总结今天学会了什么1、BST可能退化变成“电线杆”2、为什么会退化插入顺序太特殊。3、退化后会怎样搜索变慢。4、重要思想树要平衡5、记住一句重要的话算法不是永远无敌。好的结构才能有好的效率。
