講解第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

推薦閱讀:

1. 百度搜索引擎的工作原理:抓取，索引和排名

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