php-紅黑樹、散列表、跳表理解入門

就是把鏈表的結構稍加改造，這種數(shù)據結構叫

創(chuàng)新互聯(lián)公司成都網站建設按需設計網站，是成都網站推廣公司,為三輪攪拌車提供網站建設服務,有成熟的網站定制合作流程，提供網站定制設計服務：原型圖制作、網站創(chuàng)意設計、前端HTML5制作、后臺程序開發(fā)等。成都網站建設熱線：18982081108

為了提升鏈表的查詢效率，怎么讓鏈表支持類似‘數(shù)組’那樣的‘二分’算法呢

跳表是一個各方面性能都比較優(yōu)秀的 動態(tài)數(shù)據結構 ，可以支持快速地插入、刪除、查找操作，寫起來也不復雜，甚至可以替代紅黑樹。

Redis 中的有序集合（Sorted Set）就是用跳表來實現(xiàn)的。

那 Redis 為什么會選擇用跳表(和散列表)來實現(xiàn)有序集合呢？ 為什么不用紅黑樹呢？這個問題一會在回答，先看看跳表的數(shù)據結構

其實概念很簡單，就是在鏈表上加上了

當我們在不停插入數(shù)據，如果我們不更新索引，可能出現(xiàn)某 2 個索引結點之間數(shù)據非常多的情況。極端情況下，跳表還會退化成單鏈表。

紅黑樹、AVL 樹這樣平衡二叉樹，是通過左右旋的方式保持左右子樹的大小平衡，而跳表是通過 隨機函數(shù) 來維護平衡性。

插入、刪除、查找以及迭代輸出有序序列這幾個操作，紅黑樹也可以完成，時間復雜度跟跳表是一樣的。但是， 按照區(qū)間來查找數(shù)據這個操作，紅黑樹的效率沒有跳表高。

對于按照區(qū)間查找數(shù)據這個操作，跳表可以做到 O(logn) 的時間復雜度定位區(qū)間的起點，然后在原始鏈表中順序往后遍歷就可以了。

Redis 鍵值構建一個散列表，這樣按照 key 來刪除、查找一個成員對象的時間復雜度就變成了 O(1)。同時，借助跳表結構，其他操作也非常高效。

散列表的英文叫“Hash Table”，我們平時也叫它“哈希表”或者“Hash 表”

散列技術是在記錄的存儲位置和它的關鍵字之間建立一個確定的對應關系 f，使得每個關鍵字 key 對應一個存儲位置 f(key)。查找時根據這個對應關系匠互給定的 key 的映射 f(key)

這種關系 f 稱為散列函數(shù)（又稱哈希函數(shù)）。散列技術將記錄存儲在一塊連續(xù)的存儲空間中，這塊連續(xù)存儲空間稱為散列表或哈希表。那么關鍵字對應的記錄存儲位置稱為散列地址。

散列函數(shù)的構造方法特點就是：計算簡單、散列地址分布均勻

大家一定聽說過 hash 碰撞。就是2個不同的 key 對應著不同的 f 關系。但這是幾乎不可能的，即便像業(yè)界著名的MD5、SHA、CRC等哈希算法，也無法完全避免這種散列沖突。而且，因為數(shù)組的存儲空間有限，也會加大散列沖突的概率。

我們只能通過其它途徑來尋找方法。我們常用的散列沖突解決方法有兩類，開放尋址法（open addressing）和鏈表法（chaining）。

所謂的開放尋址法就是一但發(fā)生了沖突，就去尋找下一個空的散地址，只要散列表足夠大，空的散列表地址總能找到，并將記錄存入。

鏈地址法又稱鏈表法，其實當發(fā)生沖突時存入鏈表，如下圖很容易就可以看明白。此時，已經不存在什么沖突地址的問題，無論有多少沖突，都只是在當前位置給單鏈表增加結點的問題。

這種不常見，就是把沖突的單獨找個地方。

顧名思義，紅黑樹中的節(jié)點，一類被標記為黑色，一類被標記為紅色。除此之外，一棵紅黑

平衡二叉樹 是一種二叉排序樹，其中每一個節(jié)點的左子樹和右子樹的高度不能大于 1

紅黑樹是一種平衡二叉查找樹。它是為了解決普通二叉查找樹在數(shù)據更新的過程中，復雜度退化的問題而產生的。紅黑樹的高度近似 log2n，所以它是近似平衡，插入、刪除、查找操作的時間復雜度都是 O(logn)。

平衡二叉查找樹其實有很多，比如，Splay Tree（伸展樹）、Treap（樹堆）等，但是我們提到平衡二叉查找樹，聽到的基本都是紅黑樹。

紅黑樹在眾多里面，表現(xiàn)的最為平衡。

“近似平衡”就等價為性能不會退化得太嚴重。

一棵紅黑樹還需要滿足這樣幾個要求：

看到這里你會很頭大，什么黑的紅的，完全不懂。賦上連接，有時間在看

散列表 ：插入刪除查找都是O(1), 是最常用的，但其缺點是不能順序遍歷(存入的數(shù)據是無順序的)以及擴容縮容的性能損耗。適用于那些不需要順序遍歷，數(shù)據更新不那么頻繁的。

散列表總和鏈表、跳表一起出現(xiàn)組合使用。

跳表 ：插入刪除查找都是O(logn), 并且能順序遍歷。缺點是空間復雜度O(n)。適用于不那么在意內存空間的，其順序遍歷和區(qū)間查找非常方便。

跳表還可以和散列表組合讓刪除、查找一個成員對象操作變?yōu)镺(1)，也就是說利用了散列表查找速度，跳表的順序結構

紅黑樹 ：插入刪除查找都是O(logn), 中序遍歷即是順序遍歷，穩(wěn)定。缺點是難以實現(xiàn)，去查找不方便。其實跳表更佳，但紅黑樹已經用于很多地方了。

數(shù)據結構—樹的詳解

樹是非線性存儲結構，存儲的是具有“一對多”關系的數(shù)據元素的集合。

使用樹結構存儲的集合 {A,B,C,D,E,F,G,H,I,J,K,L,M} 的示意圖。對于數(shù)據 A 來說，和數(shù)據 B、C、D 有關系；對于數(shù)據 B 來說，和 E、F 有關系。這就是“一對多”的關系。

將具有“一對多”關系的集合中的數(shù)據元素按照圖中的形式進行存儲，整個存儲形狀在邏輯結構上看，類似于實際生活中倒著的樹，所以稱這種存儲結構為“樹型”存儲結構。

使用樹結構存儲的每一個數(shù)據元素都被稱為“結點”。例如，圖 1中，數(shù)據元素 A 就是一個結點；

對于圖 1中的結點 A、B、C、D 來說，A 是 B、C、D 結點的父結點（也稱為“雙親結點”），而 B、C、D 都是 A 結點的子結點（也稱“孩子結點”）。對于 B、C、D 來說，它們都有相同的父結點，所以它們互為兄弟結點。

每一個非空樹都有且只有一個被稱為根的結點。圖 1中，結點A就是整棵樹的根結點。

樹根的判斷依據為：如果一個結點沒有父結點，那么這個結點就是整棵樹的根結點。

如果結點沒有任何子結點，那么此結點稱為葉子結點（葉結點）。例如圖 1中，結點 K、L、F、G、M、I、J 都是這棵樹的葉子結點。

如圖 1中，整棵樹的根結點為結點 A，而如果單看結點 B、E、F、K、L 組成的部分來說，也是棵樹，而且節(jié)點 B 為這棵樹的根結點。所以稱 B、E、F、K、L 這幾個結點組成的樹為整棵樹的子樹；同樣，結點 E、K、L 構成的也是一棵子樹，根結點為 E。

注意：單個結點也是一棵樹，只不過根結點就是它本身。圖 1中，結點 K、L、F 等都是樹，且都是整棵樹的子樹。

知道了子樹的概念后，樹也可以這樣定義：樹是由根結點和若干棵子樹構成的。

如果集合本身為空，那么構成的樹就被稱為空樹。

空樹中沒有結點。

補充：在樹結構中，對于具有同一個根結點的各個子樹，相互之間不能有交集。例如，圖 1中，除了根結點 A，其余元素又各自構成了三個子樹，根結點分別為 B、C、D，這三個子樹相互之間沒有相同的結點。如果有，就破壞了樹的結構，不能算做是一棵樹。結點的度和層次

對于一個結點，擁有的子樹數(shù)（結點有多少分支）稱為結點的度（Degree）。例如，圖 1中，根結點 A 下分出了 3 個子樹，所以，結點 A 的度為 3。

一棵樹的度是樹內各結點的度的最大值。圖 1表示的樹中，各個結點的度的最大值為 3，所以，整棵樹的度的值是 3。

從一棵樹的樹根開始，樹根所在層為第一層，根的孩子結點所在的層為第二層，依次類推。對于圖 1來說，A 結點在第一層，B、C、D 為第二層，E、F、G、H、I、J 在第三層，K、L、M 在第四層。

一棵樹的深度（高度）是樹中結點所在的最大的層次。圖 1樹的深度為 4。

如果兩個結點的父結點雖不相同，但是它們的父結點處在同一層次上，那么這兩個結點互為堂兄弟。例如，圖 1中，結點 G 和 E、F、H、I、J 的父結點都在第二層，所以之間為堂兄弟的關系。

如果樹中結點的子樹從左到右看，誰在左邊，誰在右邊，是有規(guī)定的，這棵樹稱為有序樹；反之稱為無序樹。

在有序樹中，一個結點最左邊的子樹稱為"第一個孩子"，最右邊的稱為"最后一個孩子"。

圖 1來說，如果是其本身是一棵有序樹，則以結點 B 為根結點的子樹為整棵樹的第一個孩子，以結點 D 為根結點的子樹為整棵樹的最后一個孩子。

由 m（m = 0）個互不相交的樹組成的集合被稱為森林。圖 1中，分別以 B、C、D 為根結點的三棵子樹就可以稱為森林。

樹可以理解為是由根結點和若干子樹構成的，而這若干子樹本身是一個森林，所以，樹還可以理解為是由根結點和森林組成的。用一個式子表示為：

Tree =（root,F），其中，root 表示樹的根結點，F(xiàn) 表示由 m（m = 0）棵樹組成的森林。

數(shù)據結構中為了存儲和查找的方便，用各種樹結構來存儲文件，我們首先介紹下基本的樹的種類：二叉查找樹（二叉排序樹）、平衡二叉樹（AVL樹）、紅黑樹、B-樹、B+樹、字典樹（trie樹）、后綴樹、廣義后綴樹。

二叉查找樹是一種動態(tài)查找表，具有這些性質：

（1）若它的左子樹不為空，則左子樹上的所有節(jié)點的值都小于它的根節(jié)點的值；

（2）若它的右子樹不為空，則右子樹上所有節(jié)點的值都大于它的根節(jié)點的值；

（3）其他的左右子樹也分別為二叉查找樹；

（4）二叉查找樹是動態(tài)查找表，在查找的過程中可見添加和刪除相應的元素，在這些操作中需要保持二叉查找樹的以上性質。

含有相同節(jié)點的二叉查找樹可以有不同的形態(tài)，而二叉查找樹的平均查找長度與樹的深度有關，所以需要找出一個查找平均長度最小的一棵，那就是平衡二叉樹，具有以下性質：

（1）要么是棵空樹，要么其根節(jié)點左右子樹的深度之差的絕對值不超過1；

（2）其左右子樹也都是平衡二叉樹；

（3）二叉樹節(jié)點的平衡因子定義為該節(jié)點的左子樹的深度減去右子樹的深度。則平衡二叉樹的所有節(jié)點的平衡因子只可能是-1,0,1。

紅黑樹是一種自平衡二叉樹，在平衡二叉樹的基礎上每個節(jié)點又增加了一個顏色的屬性，節(jié)點的顏色只能是紅色或黑色。具有以下性質：

（1）根節(jié)點只能是黑色；

（2）紅黑樹中所有的葉子節(jié)點后面再接上左右兩個空節(jié)點，這樣可以保持算法的一致性，而且所有的空節(jié)點都是黑色；

（3）其他的節(jié)點要么是紅色，要么是黑色，紅色節(jié)點的父節(jié)點和左右孩子節(jié)點都是黑色，及黑紅相間；

（4）在任何一棵子樹中，從根節(jié)點向下走到空節(jié)點的路徑上所經過的黑節(jié)點的數(shù)目相同，從而保證了是一個平衡二叉樹。

B-樹是一種平衡多路查找樹，它在文件系統(tǒng)中很有用。一棵m階B-樹（圖為4階B-樹），具有下列性質：

（1）樹中每個節(jié)點至多有m棵子樹；

（2）若根節(jié)點不是葉子節(jié)點，則至少有2棵子樹；

（3）除根節(jié)點之外的所有非終端節(jié)點至少有 m/2 棵子樹；

（4）每個節(jié)點中的信息結構為（A0,K1,A1,K2......Kn,An），其中n表示關鍵字個數(shù)，Ki為關鍵字，Ai為指針；

（5）所有的葉子節(jié)點都出現(xiàn)在同一層次上，且不帶任何信息，也是為了保持算法的一致性。

B+數(shù)是B-樹的一種變形，它與B-樹的差別在于（圖為3階B+樹）：

（1）有n棵子樹的節(jié)點含有n個關鍵字；

（2）所有的葉子節(jié)點包含了全部關鍵字的信息，及指向這些關鍵字記錄的指針，且葉子節(jié)點本身按關鍵字大小自小到大順序鏈接；

（3）所有非終端節(jié)點可以看成是索引部分，節(jié)點中僅含有其子樹（根節(jié)點）中最大（或最?。╆P鍵字，所有B+樹更像一個索引順序表；

（4）對B+樹進行查找運算，一是從最小關鍵字起進行順序查找，二是從根節(jié)點開始，進行隨機查找。

字典樹是一種以樹形結構保存大量字符串。以便于字符串的統(tǒng)計和查找，經常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計。它的優(yōu)點是：利用字符串的公共前綴來節(jié)約存儲空間，最大限度地減少無謂的字符串比較，查詢效率比哈希表高。具有以下特點：

（1）根節(jié)點為空；

（2）除根節(jié)點外，每個節(jié)點包含一個字符；

（3）從根節(jié)點到某一節(jié)點，路徑上經過的字符連接起來，為該節(jié)點對應的字符串。

（4）每個字符串在建立字典樹的過程中都要加上一個區(qū)分的結束符，避免某個短字符串正好是某個長字符串的前綴而淹沒。

所謂后綴樹，就是包含一則字符串所有后綴的壓縮了的字典樹。先說說后綴的定義。給定一長度為n的字符串S=S 1 S 2 ..S i ..S n ，和整數(shù)i，1 = i = n，子串S i S i+1 ...S n 都是字符串S的后綴。以字符串S=XMADAMYX為例，它的長度為8，所以S[1..8], S[2..8], ... , S[8..8]都算S的后綴，我們一般還把空字串也算成后綴。這樣，我們一共有如下后綴。對于后綴S[i..n]，我們說這項后綴起始于i。

所有這些后綴字符串組成一棵字典樹：

上圖，我們可以看到不少值得壓縮的地方。比如藍框標注的分支都是獨苗，沒有必要用單獨的節(jié)點同邊表示。如果我們允許任意一條邊里包含多個字母，就可以把這種沒有分叉的路徑壓縮到一條邊。另外每條邊已經包含了足夠的后綴信息，我們就不用再給節(jié)點標注字符串信息了。我們只需要在葉節(jié)點上標注上每項后綴的起始位置。于是我們得到下圖：

這樣的結構丟失了某些后綴。比如后綴X在上圖中消失了，因為它正好是字符串XMADAMYX的前綴。為了避免這種情況，我們也規(guī)定每項后綴不能是其它后綴的前綴。要解決這個問題其實挺簡單，在待處理的子串后加一個空字串就行了。例如我們處理XMADAMYX前，先把XMADAMYX變?yōu)?XMADAMYX$，于是就得到suffix tree。

這就形成一棵后綴樹了。關于如何建立一棵后綴樹，已有很成熟的算法，能在o(n)時間內解決。

廣義后綴樹是好幾個字符串的的所有后綴組成的字典樹，同樣每個字符串的所有后綴都具有一個相同的結束符，不同字符串的結束符不同。

傳統(tǒng)的后綴樹只能處理一個單詞的所有后綴。廣義后綴樹存儲任意多個單詞的所有后綴。例如字符串“abab”和“baba”，首先將它們使用特殊結束符鏈接起來，如表示成"ababbaba#",然后求連接后的新字符的后綴樹，遍歷所得后綴樹，如遇到特殊字符，如"baba#",然后求連接后的新字符的后綴樹，遍歷所得后綴樹，如遇到特殊字符，如"","#"等則去掉以該節(jié)點為跟的子樹，最后所得后綴樹即為原字符串組的廣義后綴樹。其實質是將兩個字符串的所有后綴，即：abab,bab,bab,ab,b,b,baba#,aba#,ba#,a#,組成字典樹，再進行壓縮處理。

廣義后綴樹的一個常應用就是判斷兩個字符串的相識度。

簡單地理解，滿足以下兩個條件的樹就是二叉樹：

二叉樹的性質經過前人的總結，二叉樹具有以下幾個性質：

性質 3 的計算方法為：對于一個二叉樹來說，除了度為 0 的葉子結點和度為 2 的結點，剩下的就是度為 1 的結點（設為 n1），那么總結點 n=n 0 +n 1 +n 2 。

同時，對于每一個結點來說都是由其父結點分支表示的，假設樹中分枝數(shù)為 B，那么總結點數(shù) n=B+1。而分枝數(shù)是可以通過 n1 和 n2 表示的，即 B=n 1 +2 n 2 。所以，n 用另外一種方式表示為 n=n 1 +2 n 2 +1。

兩種方式得到的 n 值組成一個方程組，就可以得出 n 0 =n 2 +1。

二叉樹還可以繼續(xù)分類，衍生出滿二叉樹和完全二叉樹。

如果二叉樹中除了葉子結點，每個結點的度都為 2，則此二叉樹稱為滿二叉樹。

滿二叉樹除了滿足普通二叉樹的性質，還具有以下性質：

如果二叉樹中除去最后一層節(jié)點為滿二叉樹，且最后一層的結點依次從左到右分布，則此二叉樹被稱為完全二叉樹。

如圖 3a) 所示是一棵完全二叉樹，圖 3b) 由于最后一層的節(jié)點沒有按照從左向右分布，因此只能算作是普通的二叉樹。

完全二叉樹除了具有普通二叉樹的性質，它自身也具有一些獨特的性質，比如說，n 個結點的完全二叉樹的深度為 [log 2 n ]+1。

[log 2 n ]表示取小于[log 2 n ]的最大整數(shù)。例如，[[log 2 4 ]] = 2，而 [[log 2 5 ]] 結果也是 2。

對于任意一個完全二叉樹來說，如果將含有的結點按照層次從左到右依次標號（如圖 3a)），對于任意一個結點 i ，完全二叉樹還有以下幾個結論成立：

如何根據制定的數(shù)據使用PHP生成一個二叉樹

假如你所說的二叉樹是指這種的話

那么你的數(shù)據結構一定要滿足一個條件，則每一條數(shù)據必須記錄好父級的標識

?php

$data?=?array(

array(

'id'?=?1,

'pid'?=?0,

'name'?=?""新建腦圖,

),

array(

'id'?=?2,

'pid'?=?1,

'name'?=?"分支主題",

),

array(

'id'?=?3,

'pid'?=?1,

'name'?=?"分支主題",

),

);

?

上述二位數(shù)組中的 id為2，3的子數(shù)組的父級（pid）id均是1，則他們的父級就是id為1的數(shù)組

?php

foreach($data?as?$key=$value){

if(?$value['pid']?==?'0'){

$parent[]?=?$value;

unset($data[$key]);

}?

}

foreach($parent?as?$key=$value){

foreach($data?as?$k=$v){

if(?$v['pid']?==?$value['id']?){

$parent[$key]['_child'][]?=?$v;

unset($data[$k]);

}?

}

}

?

通過以上循環(huán)過后，對應二叉樹關系的數(shù)組就可以做出來了

當然上述代碼只能進行到二級二叉樹，如果想做出無限級二叉樹的數(shù)組，則必須使用到遞歸函數(shù)了

PS：上述代碼是網頁里手打的，沒經過測試，但思路肯定是沒問題的哈

【數(shù)據結構】樹的定義和樹的三種存儲結構

樹（Tree）是n（n=0）個結點的有限集。n=0時稱為空樹。在任意一顆非空樹中：

假設以一組連續(xù)空間存儲數(shù)的結點，同時在每個結點中， 附設一個指示器指示其雙親結點到鏈表中的位置 。

把每個結點的孩子結點排列起來，以 單鏈表作為存儲結構 ，則n個結點有n個孩子鏈表，如果是葉子結點則此單鏈表為空。然后 n個頭指針又組成一個線性表，采用順序存儲結構 ，存放進一個一維數(shù)組中。

孩子表示法有兩種結點結構： 孩子鏈表的孩子結點 和 表頭數(shù)組的表頭結點

對于孩子表示法，查找某個結點的某個孩子，或者找某個結點的兄弟，只需要查找這個結點的孩子單鏈表即可。但是 當要尋找某個結點的雙親時 ，就不是那么方便了。所以可以將雙親表示法和孩子表示法結合，形成 雙親孩子表示法 。

任意一棵樹，它的結點的第一個孩子如果存在就是唯一的，它的右兄弟存在也是唯一的。因此，設置兩個指針，分別指向該結點的第一個孩子和此結點的右兄弟。

網站題目：php樹數(shù)據結構,樹結構 數(shù)據庫
本文路徑：http://sd-ha.com/article28/hdhcjp.html

成都網站建設公司_創(chuàng)新互聯(lián)，為您提供網站排名、網站收錄、營銷型網站建設、面包屑導航、搜索引擎優(yōu)化、ChatGPT

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)