b樹演算法導論

㈠ B樹演算法難么

感覺挺難。

B樹的定義
假設B樹的度為t（t>=2），則B樹滿足如下要求：（參考演算法導論）
（1） 每個非根節點至少包含t-1個關鍵字，t個指向子節點的指針；至多包含2t-1個關鍵字，2t個指向子女的指針（葉子節點的子女為空）。
（2） 節點的所有key按非降序存放，假設節點的關鍵字分別為K[1], K[2] … K[n], 指向子女的指針分別為P[1], P[2]…P[n+1]，其中n為節點關鍵字的個數。則有：
P[1] <= K[1] <= P[2] <= K[2] …..<= K[n] <=P[n+1] // 這里P[n]也指其指向的關鍵字
（3） 若根節點非空，則根節點至少包含兩個子女；
（4） 所有的葉子節點都在同一層。
B樹的搜索，search（root, target）
從root出發，對每個節點，找到大於或等於target關鍵字中最小的K[i]，如果K[i]與target相等，則查找成功；否則在P[i]中遞歸搜索target，直到到達葉子節點，如仍未找到則說明關鍵字不在B樹中，查找失敗。
B樹的插入，insert(root,target)
B樹的插入需要沿著搜索的路徑從root一直到葉節點，根據B樹的規則，每個節點的關鍵字個數在[t-1, 2t-1]之間，故當target要加入到某個葉子時，如果該葉子節點已經有2t-1個關鍵字，則再加入target就違反了B樹的定義，這時就需要對該葉子節點進行分裂，將葉子以中間節點為界，分成兩個包含t-1個關鍵字的子節點，同時把中間節點提升到該葉子的父節點中，如果這樣使得父節點的關鍵字個數超過2t-1，則要繼續向上分裂，直到根節點，根節點的分裂會使得樹加高一層。
上面的過程需要回溯，那麼能否從根下降到葉節點後不回溯就能完成節點的插入呢？答案是肯定的，核心思想就是未雨綢繆，在下降的過程中，一旦遇到已滿的節點（關鍵字個數為2t-1），就就對該節點進行分裂，這樣就保證在葉子節點需要分裂時，其父節點一定是非滿的，從而不需要再向上回溯。
B樹的刪除，delete(root,target)
在刪除B樹節點時，為了避免回溯，當遇到需要合並的節點時就立即執行合並，B樹的刪除演算法如下：從root向葉子節點按照search規律遍歷：
（1） 如果target在葉節點x中，則直接從x中刪除target，情況（2）和（3）會保證當再葉子節點找到target時，肯定能借節點或合並成功而不會引起父節點的關鍵字個數少於t-1。
（2） 如果target在分支節點x中：
（a） 如果x的左分支節點y至少包含t個關鍵字，則找出y的最右的關鍵字prev，並替換target，並在y中遞歸刪除prev。
（b） 如果x的右分支節點z至少包含t個關鍵字，則找出z的最左的關鍵字next，並替換target，並在z中遞歸刪除next。
（c） 否則，如果y和z都只有t-1個關鍵字，則將targe與z合並到y中，使得y有2t-1個關鍵字，再從y中遞歸刪除target。
（3） 如果關鍵字不在分支節點x中，則必然在x的某個分支節點p[i]中，如果p[i]節點只有t-1個關鍵字。
（a） 如果p[i-1]擁有至少t個關鍵字，則將x的某個關鍵字降至p[i]中，將p[i-1]的最大節點上升至x中。
（b） 如果p[i+1]擁有至少t個關鍵字，則將x個某個關鍵字降至p[i]中，將p[i+1]的最小關鍵字上升至x個。
（c） 如果p[i-1]與p[i+1]都擁有t-1個關鍵字，則將p[i]與其中一個兄弟合並，將x的一個關鍵字降至合並的節點中，成為中間關鍵字。

㈡ 關於演算法導論

概念：

紅黑樹是一種自平衡二叉查找樹，是在計算機科學中用到的一種數據結構，典型的用途是實現關聯數組。它是在1972年由Rudolf Bayer發明的，他稱之為"對稱二叉B樹"，它現代的名字是在 Leo J. Guibas 和 Robert Sedgewick 於1978年寫的一篇論文中獲得的。它是復雜的，但它的操作有著良好的最壞情況運行時間，並且在實踐中是高效的: 它可以在O(log n)時間內做查找，插入和刪除，這里的n 是樹中元素的數目。

紅黑樹是一種很有意思的平衡檢索樹。它的統計性能要好於平衡二叉樹(有些書籍根據作者姓名，Adelson-Velskii和Landis，將其稱為AVL-樹)，因此，紅黑樹在很多地方都有應用。在C++ STL中，很多部分(目前包括set, multiset, map, multimap)應用了紅黑樹的變體(SGI STL中的紅黑樹有一些變化，這些修改提供了更好的性能，以及對set操作的支持)。

背景和術語：
紅黑樹是一種特定類型的二叉樹，它是在計算機科學中用來組織數據比如數字的塊的一種結構。所有數據塊都存儲在節點中。這些節點中的某一個節點總是擔當啟始位置的功能，它不是任何節點的兒子；我們稱之為根節點或根。它有最多兩個"兒子"，都是它連接到的其他節點。所有這些兒子都可以有自己的兒子，以此類推。這樣根節點就有了把它連接到在樹中任何其他節點的路徑。

如果一個節點沒有兒子，我們稱之為葉子節點，因為在直覺上它是在樹的邊緣上。子樹是從特定節點可以延伸到的樹的某一部分，其自身被當作一個樹。在紅黑樹中，葉子被假定為 null 或空。

由於紅黑樹也是二叉查找樹，它們當中每一個節點都的比較值都必須大於或等於在它的左子樹中的所有節點，並且小於或等於在它的右子樹中的所有節點。這確保紅黑樹運作時能夠快速的在樹中查找給定的值。
用途和好處：
紅黑樹和AVL樹一樣都對插入時間、刪除時間和查找時間提供了最好可能的最壞情況擔保。這不只是使它們在時間敏感的應用如即時應用(real time application)中有價值，而且使它們有在提供最壞情況擔保的其他數據結構中作為建造板塊的價值；例如，在計算幾何中使用的很多數據結構都可以基於紅黑樹。

紅黑樹在函數式編程中也特別有用，在這里它們是最常用的持久數據結構之一，它們用來構造關聯數組和集合，在突變之後它們能保持為以前的版本。除了O(log n)的時間之外，紅黑樹的持久版本對每次插入或刪除需要O(log n)的空間。

紅黑樹是 2-3-4樹的一種等同。換句話說，對於每個 2-3-4 樹，都存在至少一個數據元素是同樣次序的紅黑樹。在 2-3-4 樹上的插入和刪除操作也等同於在紅黑樹中顏色翻轉和旋轉。這使得 2-3-4 樹成為理解紅黑樹背後的邏輯的重要工具，這也是很多介紹演算法的教科書在紅黑樹之前介紹 2-3-4 樹的原因，盡管 2-3-4 樹在實踐中不經常使用。
屬性：
紅黑樹是每個節點都有顏色特性的二叉查找樹，顏色的值是紅色或黑色之一。除了二叉查找樹帶有的一般要求，我們對任何有效的紅黑樹加以如下增補要求:

1.節點是紅色或黑色。

2.根是黑色。

3.每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)

4.從每個葉子到根的所有路徑都包含相同數目的黑色節點。

這些約束強制了紅黑樹的關鍵屬性: 從根到葉子的最長的可能路徑不大於最短的可能路徑的兩倍長。結果是這個樹大致上是平衡的。因為操作比如插入、刪除和查找某個值都要求與樹的高度成比例的最壞情況時間，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同於普通的二叉查找樹。

在很多樹數據結構的表示中，一個節點有可能只有一個兒子，而葉子節點包含數據。用這種範例表示紅黑樹是可能的，但是這會改變一些屬性並使演算法復雜。為此，本文中我們使用 "null 葉子" 或"空(null)葉子"，如上圖所示，它不包含數據而只充當樹在此結束的指示。這些節點在繪圖中經常被省略，導致了這些樹好像同上述原則相矛盾，而實際上不是這樣。與此有關的結論是所有節點都有兩個兒子，盡管其中的一個或兩個可能是空葉子。

操作：
在紅黑樹上只讀操作不需要對用於二叉查找樹的操作做出修改，因為它也二叉查找樹。但是，在插入和刪除之後，紅黑屬性可能變得違規。恢復紅黑屬性需要少量(O(log n))的顏色變更(這在實踐中是非常快速的)並且不超過三次樹旋轉(對於插入是兩次)。這允許插入和刪除保持為 O(log n) 次，但是它導致了非常復雜的操作。

㈢ 如何准備互聯網公司面試（演算法相關）

書籍： 《演算法導論》 這本是大部頭，很多人都看不完。我本人也並沒有看完，它跟了我這么多年，完全是屬於常看常新的牛書。每一次看，都發現會有新的收獲。比如，以前並不知道求K位數或者中位數有平均為O(n)復雜度的演算法。看到了別的地方的參考資料，才知道，原來《算導》上專門有一小節講這個內容。我基本上是本科比較集中的看了一遍，研一的時候又集中的看了一遍，才算是粗略的看完。但是其實，很多理論性的，以及圖論一部分依然還是沒有看完。個人推薦，先從簡單的開始，挑選比較熟悉的一些偏重與數據結構方面的知識作為起點。這本書的習題非常重要，要是有時間，能夠全部做完，那絕對是能夠神功在手了。其實，集中把，第二部分（排序），第三部分（數據結構），第四部分（高級設計，我基本主要看動態規劃和貪心），第五部分（高級數據結構，B樹和二項堆，並差集），第六部分（圖演算法，最大流部分較難，自己可以看情況掌握）。這些部分可以先從演算法本身開始，偽代碼全部看懂。因為演算法導論講的很詳細，而且有來龍去脈，基本不會有太大難度。數學證明，推薦大家掌握，但是，突擊或者第一次，可以選擇性的看看。我自己是重復看，才把證明看掉的。第一次看的時候，基本都跳過了。不過，證明和習題是精髓！希望如果有時間，一定要補回來。 《編程之美》《挑戰編程》 這本書絕對是將全中國企業，或者說是一部分懶惰的企業面試題庫提升了一個檔次的一本神書。網路面我師兄的時候，我師兄直接把有一道題的最優解答出來了。但是，那個面試官顯然是不知道最優解，一直在引導我師兄答出，這本書裡面的第四個解。呵呵。書很不錯。全部看一遍並不難。說個不好聽的，可以背下來，而且相信我，基本上絕對有用！比如說，n!後面有多少個0。我相信，你們今年面試或者筆試，一定會碰到這道題。《挑戰編程》大家可以自行考慮一下吧，這個完全是針對acm競賽的，不過，看看題也不錯。 《編程珠璣》 業界神書嘛。習題全部做完就是了。其實都是些小東西，但是，基本上一步步考察你的解決問題的能力。個人覺得，最常用的就是bit map做排序或者去重，拓展一下就是bloom filter，我當時都是在這本書裡面看到的。 《演算法技術手冊》 這本書貌似出鏡不多。書很薄，代碼寫的非常好，其實基本上全部都是基礎演算法和數據結構的實現。但是，它牛逼就在於，代碼寫的太好了，基本上，看一遍，絕對能背下來。面試基礎很重要。基本上每個筆試或者面試，都會考一個100行以內的小程序。比如，給定一棵樹，以及其中一個節點x，要求出這棵樹的中序遍歷序列中，x的後續節點，非遞歸實現。這種題非常簡單，但是，真正寫對的，其實並不多。《STL源碼剖析》《C標准庫》 都不厚。挑著看一遍非常舒服。特別是，看看STL每個數據結構迭代器類型啊，紅黑書如何實現啊。C標准庫，最常見的，比如strcpy()和memcpy()有什麼區別啊。特別是，STL，看過之後，對泛型還是能有一定了解的。《C專家編程》《Effective c++》《深度探索C++對象模型》 第一本比較簡單，可以當八卦書看。後兩本其實也沒啥好說的，其實都是些業界公認的牛書。我再重復一遍也沒什麼意義。但是，的確，考察基本上也就都是這么幾本書上面的東西。基本上後兩本主要側重看c++對象方面的一些指示，特別是多態相關的。 《具體數學》《組合數學》 這兩本其實可以看作修身養性的書。我當時是時間比較充裕的時候看完的。純突擊，大家就可以跳過了。但是，看完真的很有用。比如說，你們就可以跟面試官扯約瑟夫環的構造解了（這道題我覺得80%會遇到），直接推推公式，就不用寫模擬代碼了。《組合數學》也是，很多筆試一般會有些小智力題。不過，其實一般的題目，不看這本書也可以搞定。所以，這兩本僅供參考。大家有興趣的時候，可以翻翻。《Linux內核源碼剖析》《Linux環境高級編程》…… 要是有機會，能看看最好。因為很多公司都會考察Linux相關的知識。最少要會點腳本，一些簡單的Linux命令，以及正則表達式什麼的。要是能聊聊內核源碼或者驅動開發什麼的東西，面試官肯定更加喜歡了。 知識： c & c++ 首先要知道c和c++的區別。常考的有const的用法，一些生僻關鍵字比如extern，static的用法。 結構體與類的差別。類裡面的字對齊問題，也就是說一個類到底有多大。以及一個空的類有多大。 虛函數以及多態相關的顯然是重點。比如析構函數什麼時候需要寫成虛函數，構造函數是否可以是虛函數。 int a[10]; a 和 &a的區別。 java java我並不熟。但是基本上肯定會考一些虛擬機相關的，以及GC等知識。然後，一般招聘的java程序員都會問到很多多線程編程的東西，以及hadoop！這個絕對是重點，淘寶絕對就是問這個的。 操作系統 這個看工作崗位的實際要求。基本的進程線程區別==肯定是會問到的。要是要求高一些，就會問很多多線程編程的問題。一些競爭死鎖等基礎知識，一些進程調度的演算法，最近的kernel好像用的是CFS調度演算法。shell編程，如何讀取程序堆棧，寫一些core mp的讀取程序等等的。 數據結構 基本上所有的排序都要會寫。與樹有關的操作都要會些非遞歸版本。圖一般考的不多。Flood-Fill演算法等等。查找中位數。B樹和紅黑書最好要掌握，不用會寫，能扯扯基本就行。KMP，這個很有可能考！而且的確真的不好懂。要是實在不行，背下來吧。哈哈。 網路 這個其實比較基礎了。我個人網路方面的知識並不好。但是各種協議的基礎，幾次握手啊，一些操作系統的api實現到底是單工還是雙工用的是TCP還是UDP。我個人網路純粹靠拼RP。 資料庫 資料庫非常重要。基本的SQL肯定是要會的。最常見有一道題，inner join和out join的區別。MySQL是重點，基本上很多企業都是問這個。然後，網路扯多了會跟你扯MySQL引擎 的一些東西。這些我就不太懂了。要是能准備的話，或者說的確是做這方面的，就可以著重多准備下。 大規模數據處理這一塊絕對是重點！而且本身不是一個系統的學科分支。但是，基本上幾家大公司都會問這方面的。推薦先讀讀google那幾篇論文。Page Rank那一篇，然後Map Rece好像有幾篇吧。Big Table什麼的。推薦一個網址。這篇貌似是轉載的，我以前找到的源地址現在找不到了。處理這一類問題基本上思路都是，哈希，map rece以及bit map等等的。對了，推薦看一下外排序以及相關的敗者樹。這些都是大規模數據處理的一些典型問題。掌握了這些其實也就夠了。這塊有點屠龍之技的感覺，特別是對於學生，基本沒有誰能有機會把這些代碼實現出來。但是，沒辦法，這些公司就是喜歡考。看完那篇博客的，然後再自行查找一些資料，基本就夠了。萬變不離其中，而且，這些東西，沒辦法考那麼難的。 推薦一個博客吧，作者收集了100+道面試題，並且全部給出了代碼。把這個全部看完，基本上很多面試筆試，都是這些原題。 推薦Top Language裡面的今天我們思考系列，好幾年前的了。看大牛的思考過程，非常有幫助。希望自己能多想想再看答案。注意，google group好像有時被牆。 我把發芽網的題庫版塊也掃了一遍。 還有好多一時想不起來了。

㈣ 演算法導論 習題

將集合排序，復雜度O(nlogn)。
從小到大遍歷整個數組的每個數i，計算出X-i是否存在，復雜度O(n)。
於是就是復雜度O(nlogn) + O(n) = O(nlogn)

㈤ B樹演算法難么

感覺挺難。
B樹的定義
假設B樹的度為t（t>=2），則B樹滿足如下要求：（參考演算法導論）
（1）
每個非根節點至少包含t-1個關鍵字，t個指向子節點的指針；至多包含2t-1個關鍵字，2t個指向子女的指針（葉子節點的子女為空）。
（2）
節點的所有key按非降序存放，假設節點的關鍵字分別為K[1],
K[2]
…
K[n],
指向子女的指針分別為P[1],
P[2]…P[n+1]，其中n為節點關鍵字的個數。則有：
P[1]
<=
K[1]
<=
P[2]
<=
K[2]
…..<=
K[n]
<=P[n+1]
//
這里P[n]也指其指向的關鍵字
（3）
若根節點非空，則根節點至少包含兩個子女；
（4）
所有的葉子節點都在同一層。
B樹的搜索，search（root,
target）
從root出發，對每個節點，找到大於或等於target關鍵字中最小的K[i]，如果K[i]與target相等，則查找成功；否則在P[i]中遞歸搜索target，直到到達葉子節點，如仍未找到則說明關鍵字不在B樹中，查找失敗。
B樹的插入，insert(root,target)
B樹的插入需要沿著搜索的路徑從root一直到葉節點，根據B樹的規則，每個節點的關鍵字個數在[t-1,
2t-1]之間，故當target要加入到某個葉子時，如果該葉子節點已經有2t-1個關鍵字，則再加入target就違反了B樹的定義，這時就需要對該葉子節點進行分裂，將葉子以中間節點為界，分成兩個包含t-1個關鍵字的子節點，同時把中間節點提升到該葉子的父節點中，如果這樣使得父節點的關鍵字個數超過2t-1，則要繼續向上分裂，直到根節點，根節點的分裂會使得樹加高一層。
上面的過程需要回溯，那麼能否從根下降到葉節點後不回溯就能完成節點的插入呢？答案是肯定的，核心思想就是未雨綢繆，在下降的過程中，一旦遇到已滿的節點（關鍵字個數為2t-1），就就對該節點進行分裂，這樣就保證在葉子節點需要分裂時，其父節點一定是非滿的，從而不需要再向上回溯。
B樹的刪除，delete(root,target)
在刪除B樹節點時，為了避免回溯，當遇到需要合並的節點時就立即執行合並，B樹的刪除演算法如下：從root向葉子節點按照search規律遍歷：
（1）
如果target在葉節點x中，則直接從x中刪除target，情況（2）和（3）會保證當再葉子節點找到target時，肯定能借節點或合並成功而不會引起父節點的關鍵字個數少於t-1。
（2）
如果target在分支節點x中：
（a）
如果x的左分支節點y至少包含t個關鍵字，則找出y的最右的關鍵字prev，並替換target，並在y中遞歸刪除prev。
（b）
如果x的右分支節點z至少包含t個關鍵字，則找出z的最左的關鍵字next，並替換target，並在z中遞歸刪除next。
（c）
否則，如果y和z都只有t-1個關鍵字，則將targe與z合並到y中，使得y有2t-1個關鍵字，再從y中遞歸刪除target。
（3）
如果關鍵字不在分支節點x中，則必然在x的某個分支節點p[i]中，如果p[i]節點只有t-1個關鍵字。
（a）
如果p[i-1]擁有至少t個關鍵字，則將x的某個關鍵字降至p[i]中，將p[i-1]的最大節點上升至x中。
（b）
如果p[i+1]擁有至少t個關鍵字，則將x個某個關鍵字降至p[i]中，將p[i+1]的最小關鍵字上升至x個。
（c）
如果p[i-1]與p[i+1]都擁有t-1個關鍵字，則將p[i]與其中一個兄弟合並，將x的一個關鍵字降至合並的節點中，成為中間關鍵字。