「二叉樹可以解決什麼問題」?

電子信息專業應屆生,苦逼找工作中。

面試被問到「二叉樹可以解決什麼問題」,一時語塞,後來想想確實學演算法的時候沒有聯繫實際深入思考,只局限於明白邏輯,甚至連實現過程都只是看了看書上的偽代碼,現在想趁畢業前補補。問題來了,1二叉樹可以解決什麼問題?2應該用什麼姿勢學演算法?


很明顯,題主沒有學的比較好。

或者沒參加過acm的相關訓練。只是一個平時跟著學做些課後題然後混畢業的。

二叉樹,本質上,是對鏈表和數組的一個折中。。

比如,我有一個任務,需要輸入

10萬個數據(32位整數),然後有兩個操作:

1.添加(刪除)一個整數。

2.詢問第x大的數據。

比如,我給你 1, 8, 13, 10(等等一堆數據).......

然後我詢問第3大的數據,

然後我插入 18

然後我詢問第4大的數據

我再插入 9

我再詢問第2大的數據

不停的重複1,2

重複10萬次。。

應該如何實現。

你會發現,用有序鏈表,不行,查找(包括1需要找到對應位置,以及2查找)成本大O(N),但具體這個插入操作成本小O(1)。

用有序數組,查找(2的查找)成本小O(1)。但1的插入操作成本很大O(N)。

所以,我們折中使用排序二叉樹(二叉樹僅僅作為排序二叉樹的基礎),查找(包括1需要找到對應位置,以及2查找)成本挺小O(logN)。具體這個插入操作成本也挺小O(logN)。

具體的應用就是由排序二叉樹(由於普通排序二叉樹可能會有不平衡的情況)引申出來的紅黑樹(linux中ext3文件系統管理),avl樹「windows對進程地址空間的管理」。

回答不出來也不怪你。畢竟這些知識絕對是超綱了。

這是一個口子小但可以扯的很多的題目,你能大概講個二叉樹的遍歷也就算可以了。只是和某些acm的選手來說,你會很吃虧。因為acm選手是知道並且用過紅黑樹之類的東西的。

應該用什麼姿勢學演算法?

演算法在具體工作中用的真的不多,就剩半年,你也不可能學到acm選手的程度。。所以建議,去實習吧,關於演算法,把你們以前的那本演算法教材給撿起來複習複習,每一個具體的演算法例子都給用代碼敲一遍,跑一跑,大學也就基本結束了。。。。。不要太多留戀了,半年很快的。 實習工作找不到?總能找到的,只是可能待遇不好。轉正的工資不怎麼樣而已。

演算法學的好又能怎麼樣。

比如我,吃著火鍋,裝著b,結果還不是混的很慘。匿名了。

最後謝邀。

============================4月2日修改==============================

感謝諸位大神捧場。

點贊挺多了,我就對「二叉樹,本質上,是對鏈表和數組的一個折中」 補充幾個腦洞:

建立在如下推論上:假定把數組看成N叉樹,那麼鏈表就是1叉樹,由於數組只有1層,二叉樹有logN層,而鏈表有N層,"logN對1" 以及 "N對logN" 都是 無限大的關係。。。相當於我們在1 ~ N之間找了一個logN作為兩者的折中。。。。。。

進一步的腦洞是,如果我們是a叉樹,那麼結果就是log(a)N = frac{log(2)N}{log(2)a} 層,但

考慮分母部分。

  • a = 1時,log(2)1 = 0

  • a = 2時,log(2)2 = 1
  • a = N時,log(2)N = N

恰好構成了 0, 1, N的三個經典數字。。。。

查找和插入一共所需的次數可以簡化為:每層數量+總層數 = a + frac{log(2)N}{log(2)a} 當a是大於等於1的整數時,a取2是最划算的。。。所以綜合以上推斷,個人得出,"二叉樹,本質上,是對鏈表和數組的一個折中"。 這對於查找和插入是類似1:1(同一數量級)的需求,用二叉樹(排序二叉樹等)是很划算的。如果不是同一數量級可以考慮,增大a或者減少a,具體問題具體分析,這是個工程問題。得考慮編碼難度,演算法常數,可維護性等多方面需求。不再一一分析。

以上僅僅是個人奉獻的腦洞,沒有任何成熟的理論支撐。感謝看到這裡。


昨天在玩仙劍5前傳,走到蚩尤冢的時候遇到了一個拼圖小遊戲(爪機答,晚上換電腦上圖),我一看這不是八數碼嗎,於是開心的玩了半個小時沒解出來。所以我打開everything,找到四年前擼oi的時候寫的A*,編譯運行輸入數據,照著輸出的路徑玩過了小遊戲。這和二叉樹什麼關係呢,我用Treap實現的集合(set),用Heap實現的優先隊列(priority_queue)

(逃

------------上圖的分割線----------

就是這貨

目標狀態

-----------講道理八數碼確實只用廣搜就夠了,畢竟狀態少(9!種) @江雪兒,這是我高中學A*時順便寫的

講道理A*就是個改變搜索順序並且保證最優的優先隊列BFS(逃

講道理15數碼用A*會爆內存,某OJ的標準解法是IDA*


講道理 什麼線段樹啊 搜索樹啊 排序樹啊 博弈樹啊 紅黑樹啊 都是以二叉樹為基礎的 至於學演算法 各大oj刷一刷就好


堆排序,大根堆,小根堆。

哈夫曼樹,用於壓縮。

檢索樹,保持先根序遞增的。

另外其他樹,可以用左兒子又兄弟表示成二叉樹形式。

二叉樹,是接觸樹這個數據結構的第一種樹,便於理解,也讓你對其他樹有個認識,比如紅黑樹,B+樹,還有進程樹,語法樹,熟悉二叉樹,對於深入學習樹這一結構是有很大好處的。


二叉樹主要應用在以二叉樹為基礎的各種數據結構上。首先,二叉搜索樹(BST)和堆這兩種相當常用的數據結構就是基於二叉樹。BST是Treeset和Treemap的基礎,可以幫助構建有序的集合。Heap是優先隊列的基礎,可以幫助排序。其他高級數據結構如二叉索引樹(BIT)和線段樹(Segment tree)也是以二叉樹為基礎。機器學習中的決策樹,在二元決策問題的時候也可以通過二叉樹來實現。個人覺得二叉樹主要應用還是在有序集合或數列上的應用。


涉及到樹的話、大部分都是為了方便插入刪除和查找吧= =

我水平太渣T T。這個東西除了能幹上面的事以及折磨我們這些acm炮灰之外、我貌似想不出什麼其他用途了。


堆排序不就是依靠二叉樹嘛 題主傻了


推薦閱讀:

數據結構公開課學伯克利的CS 61B好還是清華鄧俊輝的mooc公開課好呢?
如何處理十萬級別的數據信息?
一個程序員會遇到多少關於數據結構與演算法的需求?
有沒有一種數據結構,查找、刪除和插入效率都比較高呢?
如何在程序中將中綴表達式轉換為後綴表達式?

TAG:學習能力 | 演算法與數據結構 | 二叉樹 |