目錄

1、 紅黑樹的性質(zhì)

2、 紅黑樹的插入與旋轉(zhuǎn)

3、 紅黑樹與平衡二叉樹

4、 二叉平衡樹、紅黑樹、B樹、B+樹的區(qū)別與聯(lián)系

5、 hello world 程序開始到打印到屏幕上的全過程?

---

?

1、 紅黑樹的性質(zhì)

性質(zhì)1.節(jié)點是紅色或黑色。

性質(zhì)2.根節(jié)點是黑色。

性質(zhì)3.每個葉子節(jié)點都是黑色的空節(jié)點（NIL節(jié)點）。

性質(zhì)4.每個紅色節(jié)點的兩個子節(jié)點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點)

性質(zhì)5.從任一節(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點。

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

下圖就是一個很典型的紅黑樹：

2、 紅黑樹的插入與旋轉(zhuǎn)

1、添加的節(jié)點必須為紅色

2、變色的情況：當前結(jié)點的父親是紅色，且它的叔結(jié)點也是紅色：

2.1 把父節(jié)點設置為黑色

2.2 把叔節(jié)點設置為黑色

2.3 把祖父節(jié)點設置為紅色

2.4 把當前指針定義到祖父節(jié)點，設為當前要操作的

3、左旋的情況：當前父節(jié)點是紅色，叔節(jié)點是黑色，且當前的節(jié)點是右子樹。

3.1 以父節(jié)點作為左旋。

4、右旋的情況：當前父節(jié)點是紅色，叔節(jié)點是黑色，且當前的節(jié)點是左子樹。

4.1 把父節(jié)點變成黑色

4.2 把祖父節(jié)點變?yōu)榧t色

4.3 以祖父節(jié)點右旋轉(zhuǎn)

lsy注：

點這里

https://blog.csdn.net/qq_41687938/article/details/119634248

3、 紅黑樹與平衡二叉樹

1、紅黑樹放棄了追求完全平衡，追求大致平衡，在與平衡二叉樹的時間復雜度相差不大的情況下，保證每次插入最多只需要三次旋轉(zhuǎn)就能達到平衡，實現(xiàn)起來也更為簡單。

2、平衡二叉樹追求絕對平衡，條件比較苛刻，實現(xiàn)起來比較麻煩，每次插入新節(jié)點之后需要旋轉(zhuǎn)的次數(shù)不能預知。

lsy注：https://blog.csdn.net/qq_41687938/article/details/119634248

4、 二叉平衡樹、紅黑樹、B樹、B+樹的區(qū)別與聯(lián)系

1.二叉樹的查找的時間復雜度是O(log2N)，其查找效率與深度有關，而普通的二叉樹可能由于內(nèi)部節(jié)點排列問題退化成鏈表，這樣查找效率就會很低。

2.平衡二叉樹是更好的選擇，因為它保持平衡，即通過旋轉(zhuǎn)調(diào)整結(jié)構(gòu)保持最小的深度。其查找的時間復雜度也是O(log2N)。

索引的結(jié)構(gòu)也并非AVL樹或更優(yōu)秀的紅黑樹，盡管它的查詢的時間復雜度很低。作為索引的結(jié)構(gòu)應該是盡可能少的執(zhí)行磁盤IO操作，因為執(zhí)行磁盤IO操作非常的耗時。所以需要利用上磁盤的預讀功能。平衡二叉樹沒利用上。

3.B樹(多路搜索樹)是為了充分利用磁盤預讀功能來而創(chuàng)建的一種數(shù)據(jù)結(jié)構(gòu)，也就是說B樹就是為了作為索引才被發(fā)明出來的。

紅黑樹這種結(jié)構(gòu)，h明顯要深的多。由于邏輯上很近的節(jié)點（父子）物理上可能很遠，無法利用局部性，所以紅黑樹的I/O漸進復雜度也為O(h)，效率明顯比B-Tree差很多。

4.?比B樹更適合作為索引的結(jié)構(gòu)是B+樹

B樹：有序數(shù)組+平衡多叉樹；

B+樹：有序數(shù)組鏈表+平衡多叉樹；

B+樹的關鍵字全部存放在葉子節(jié)點中，非葉子節(jié)點用來做索引，而葉子節(jié)點中有一個指針指向一下個葉子節(jié)點。做這個優(yōu)化的目的是為了提高區(qū)間訪問的性能。而正是這個特性決定了B+樹更適合用來存儲外部數(shù)據(jù)。

lsy注：B樹和B-樹都是指B-Tree

詳解平衡二叉樹、紅黑樹、B樹、B+樹在索引中的應用_子木呀的博客-CSDN博客

5、 hello world 程序開始到打印到屏幕上的全過程?

1.用戶告訴操作系統(tǒng)執(zhí)行HelloWorld程序（通過鍵盤輸入等）

2．操作系統(tǒng)：找到helloworld程序的相關信息，檢查其類型是否是可執(zhí)行文件；并通過程序首部信息，確定代碼和數(shù)據(jù)在可執(zhí)行文件中的位置并計算出對應的磁盤塊地址。

3．操作系統(tǒng)：創(chuàng)建一個新進程，將HelloWorld可執(zhí)行文件映射到該進程結(jié)構(gòu)，表示由該進程執(zhí)行helloworld程序。

4．操作系統(tǒng)：為helloworld程序設置cpu上下文環(huán)境，并跳到程序開始處。

5．執(zhí)行helloworld程序的第一條指令，發(fā)生缺頁異常

6．操作系統(tǒng)：分配一頁物理內(nèi)存，并將代碼從磁盤讀入內(nèi)存，然后繼續(xù)執(zhí)行helloworld程序

7．helloword程序執(zhí)行puts函數(shù)（系統(tǒng)調(diào)用），在顯示器上寫一字符串

8．操作系統(tǒng)：找到要將字符串送往的顯示設備，通常設備是由一個進程控制的，所以，操作系統(tǒng)將要寫的字符串送給該進程

9．操作系統(tǒng)：控制設備的進程告訴設備的窗口系統(tǒng)，它要顯示該字符串，窗口系統(tǒng)確定這是一個合法的操作，然后將字符串轉(zhuǎn)換成像素，將像素寫入設備的存儲映像區(qū)

10．視頻硬件將像素轉(zhuǎn)換成顯示器可接收和一組控制數(shù)據(jù)信號

11．顯示器解釋信號，激發(fā)液晶屏

12．OK，我們在屏幕上看到了HelloWorld

總結(jié)

以上是生活随笔為你收集整理的二十万字C/C++、嵌入式软开面试题全集宝典十一的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。