|
|
教学公告
讲解第7章的内容 220-235页
重点理解:
1、线性表、散列表、树表的各种查找技术
2、折半查找判定树
3、平衡二叉树的调整方法
重点: 二叉排序树、折半查找算法
难点: 平衡二叉树
师说:
本周讲述的查找二叉树是不少企业面试题的热点,而平衡二叉树是第七章的重点和难点,这里提供几个题目、讲解视频给各位进行了解和复习所用。
查找二叉树的几道面试题
1、判断一个单词是否拼写正确;
直接将所有单词入搜索二叉树,判断单词是否正确时只需搜索二叉树中是否存在该单词即可。
2、请模拟实现一个简单的中英互译的字典;
本题利用搜索二叉树的key、value模式。如果是英译汉时,key存放英文,value存放中文,再根据英文找到结点所在,查找结点的value即可得到中文;英译汉时,key存放中文,value存放英文,再根据中文找到结点所在,查找结点的value即可得到中文。
3、log文件中有许多异常重复的IP地址,请统计出每个异常IP出现了多少次。
也是利用搜索二叉树的key、value模式。key存放异常IP,而value为int计数,每找到一个将该IP所在的结点的value加1,最后遍历每个结点的value即可得到每个异常IP出现的次数。
1、平衡二叉树的概念
http://v.youku.com/v_show/id_XMTg1MTkyOTI4MA==.html?spm=a2hzp.8244740.0.0
2、平衡二叉树的调整
http://v.youku.com/v_show/id_XMTg1MDc0MTM5Mg==.html?spm=a2hzp.8244740.0.0
3、平衡二叉树的练习
http://v.youku.com/v_show/id_XMTg1MDc0NDI4OA==.html?spm=a2hzp.8244740.0.0
推荐阅读:
https://www.simcf.cc/1721.html/
2.实时搜索的现实需求与发展应用问题浅析
https://tech.qq.com/a/20100910/000203.htm
3.漫画:什么是二分查找
https://www.360kuai.com/pc/9ebfa191b338854f5?cota=4&kuai_so=1