講解第7章的內(nèi)容 220-235頁(yè)

重點(diǎn)理解:

1、線性表、散列表、樹表的各種查找技術(shù)

2、折半查找判定樹

3、平衡二叉樹的調(diào)整方法

重點(diǎn): 二叉排序樹、折半查找算法

難點(diǎn): 平衡二叉樹

師說:

本周講述的查找二叉樹是不少企業(yè)面試題的熱點(diǎn)，而平衡二叉樹是第七章的重點(diǎn)和難點(diǎn)，這里提供幾個(gè)題目、講解視頻給各位進(jìn)行了解和復(fù)習(xí)所用。

查找二叉樹的幾道面試題

1、判斷一個(gè)單詞是否拼寫正確；

直接將所有單詞入搜索二叉樹，判斷單詞是否正確時(shí)只需搜索二叉樹中是否存在該單詞即可。

2、請(qǐng)模擬實(shí)現(xiàn)一個(gè)簡(jiǎn)單的中英互譯的字典；

本題利用搜索二叉樹的key、value模式。如果是英譯漢時(shí)，key存放英文，value存放中文，再根據(jù)英文找到結(jié)點(diǎn)所在，查找結(jié)點(diǎn)的value即可得到中文；英譯漢時(shí)，key存放中文，value存放英文，再根據(jù)中文找到結(jié)點(diǎn)所在,查找結(jié)點(diǎn)的value即可得到中文。

3、log文件中有許多異常重復(fù)的IP地址，請(qǐng)統(tǒng)計(jì)出每個(gè)異常IP出現(xiàn)了多少次。

也是利用搜索二叉樹的key、value模式。key存放異常IP，而value為int計(jì)數(shù)，每找到一個(gè)將該IP所在的結(jié)點(diǎn)的value加1，最后遍歷每個(gè)結(jié)點(diǎn)的value即可得到每個(gè)異常IP出現(xiàn)的次數(shù)。

1、平衡二叉樹的概念

http://v.youku.com/v_show/id_XMTg1MTkyOTI4MA==.html?spm=a2hzp.8244740.0.0

2、平衡二叉樹的調(diào)整

http://v.youku.com/v_show/id_XMTg1MDc0MTM5Mg==.html?spm=a2hzp.8244740.0.0

3、平衡二叉樹的練習(xí)

http://v.youku.com/v_show/id_XMTg1MDc0NDI4OA==.html?spm=a2hzp.8244740.0.0

推薦閱讀:

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

https://www.simcf.cc/1721.html/

2.實(shí)時(shí)搜索的現(xiàn)實(shí)需求與發(fā)展應(yīng)用問題淺析

https://tech.qq.com/a/20100910/000203.htm

3.漫畫:什么是二分查找

https://www.360kuai.com/pc/9ebfa191b338854f5?cota=4&kuai_so=1