二叉搜索樹演算法
① 數據結構與演算法-二叉樹(Binary Tree)
名詞解釋
節點: 每個元素
父子關系: 用來連線相鄰節點之間的關系
父節點: A節點就是B節點的父節點
子節點: B節點就是A節點的子節點
兄弟節點: B、C、D這三個節點的父節點是同一個節點
根結點: 沒有父節點的節點
葉子結點: 沒有子節點的節點
節點的高度: 節點到葉子結點到最長路徑(邊數) (計數起點為0, 從下往上)
節點的深度: 根節點到這個節點經歷過的邊個數 (計數起點為0, 從上往下)
節點的層數: 節點到深度 + 1 (計數起點為1)
樹的高度: 根節點的高度
特點
最常用的樹數據結構
每個節點最多有兩個子節點(左子節點、右子節點)
滿二叉樹: 葉子節點全都在最底層，除了葉子節點之外，每個節點都有左右兩個子節點
完全二叉樹: 葉子節點都在最底下兩層，最後一層的葉子節點都 靠左排列 ，並且除了最後一層，其他層的節點個數都要達到最大
二叉樹存儲方式
數組順序存儲法
通過數組下標來順序存儲數據 (i表示當前節點深度,從0開始)
根節點: i = 1，左節點:2 * i，右節點: 2 * i + 1，父節點: i / 2
完全二叉樹採用此方式節省內存空間
鏈式存儲法
每個節點需要存儲三分數據:當前節點數據、左節點指針、右節點指針,比較佔用空間
遍歷
常用方式
前序遍歷: 樹任意節點，先列印當前節點，再列印它的左子樹，最後列印它的右子樹
中序遍歷: 樹任意節點，先列印它的左子樹，再列印當前節點，最後列印它的右子樹
後序遍歷: 樹任意節點，先列印它的左子樹，再列印它的右子樹，最後列印當前節點
二叉樹的前、中、後序遍歷就是一個遞歸的過程
時間復雜度是O(n)
每個節點最多被訪問兩次，遍歷操作的時間復雜度跟節點的個數n成正比
特點
二叉查找樹為實現快速查找而生，支持快速查找一個數據、快速插入、快速刪除一個數據
特殊結構: 其左子樹每個節點的值 < 樹的任意一個節點的值 < 其右子樹每個節點的值
先取根節點，如果它等於要查找的數據，那就返回。
如果要查找的數據比根節點的值小，那就在左子樹中遞歸查找；
如果要查找的數據比根節點的值大，那就在右子樹中遞歸查找
一般插入的數據在葉子節點上，從根節點開始依次比較要插入的數據和節點的大小關系
如果插入數據比節點的數值大，並且節點的右子樹為空，將新數據插到右子節點位置；
如果不為空，就再遞歸遍歷右子樹，查找插入位置。
如果插入數據比節點的數值小，並且節點的左子樹為空，將新數據插到左子節點位置；
如果不為空，就再遞歸遍歷左子樹，查找插入位置。
針對要刪除節點的子節點個數的不同，需分三種情況來處理
1.如果要刪除的節點沒有子節點，步驟如下: (如圖中的刪除節點55)
只需將父節點中指向要刪除節點的指針置為null
2.如果要刪除的節點只有一個子節點，步驟如下: (如圖中刪除節點13)
只需將父節點中指向要刪除節點的指針，讓它指向要刪除節點的子節點即可
3.如果要刪除的節點有兩個子節點，步驟如下: (如圖中的刪除節點18)
首先，需要找到這個節點的右子樹中的最小節點，把它替換到要刪除的節點上；
然後，再刪除掉這個最小節點，因為最小節點肯定沒有左子節點
刪除操作，有個優化方案: 就是單純將要刪除的節點標記為「已刪除」，
這種方案刪除操作就變簡單很多，但是比較浪費內存空間
支持快速地查找最大節點和最小節點、前驅節點和後繼節點
另外一種重要特性:
中序遍歷二叉查找樹，可以輸出有序的數據序列，時間復雜度為O(n)
因此，二叉查找樹也叫作二叉排序樹
以上幾種操作都默認樹中節點存儲的都是數字，而且都是不存在鍵值相同的情況
實際應用場景中採用對象的某個欄位作為鍵值來構建二叉查找樹，其他欄位稱為衛星數據
如果存儲的兩個對象鍵值相同，兩種解決方案
1.把值相同的數據都存儲在同一個節點(採用鏈表或支持動態擴容的數組等數據結構)
2.每個節點只存儲一個數據，把這個新插入的數據當作大於這個節點的值來處理，如下圖:
查找操作
當查找數據時遇到值相同的節點，繼續在右子樹中查找，直到遇到葉子節點才停止。
這樣就把鍵值等於要查找值的所有節點都查找出來
刪除操作
先查找到每個要刪除的節點，然後再按前面講的刪除操作的方法，依次刪除
對於同一組數據可構造不同二叉查找樹。查找、插入、刪除操作的執行效率都不一樣
圖最左邊樹，根節點的左右子樹極度不平衡，退化成鏈表，查找時間復雜度為O(n)
最理想的情況，二叉查找樹是一棵完全二叉樹（或滿二叉樹）
時間復雜度都跟樹的高度成正比，也就是O(height)
樹的高度就等於最大層數減一，為了方便計算，我們轉換成層來表示
滿二叉樹: 下一層節點個數是上一層的2倍，第K層包含節點個數就是2^(K-1)
完全二叉樹: 假設最大層數是L，總的節點個數n，它包含的節點個數在1個到2^(L-1)個之間
L的范圍是[ , +1]，完全二叉樹的高度小於等於
極度不平衡的二叉查找樹，它的查找性能肯定不能滿足我們的需求
平衡二叉查找樹: 樹的高度接近logn，時間復雜度較穩定為O(logn)
1.排序對比
散列表中的數據是無序存儲的，如果要輸出有序的數據，需要先進行排序
二叉查找樹只需要中序遍歷，就可以在O(n)的時間復雜度內，輸出有序的數據序列
2.性能穩定性對比
散列表擴容耗時很多，而且當遇到散列沖突時，性能不穩定
最常用的平衡二叉查找樹的性能非常穩定，時間復雜度穩定在O(logn)
3.時間復雜度對比
散列表查找等操作時間復雜度是常量級，因存在哈希沖突，這個常量不一定比logn小
另外加上哈希函數的耗時，也不一定就比平衡二叉查找樹的效率高
4.結構設計對比
散列表構造比較復雜，需要考慮:散列函數設計、沖突解決辦法、擴容、縮容等
平衡二叉查找樹只需要考慮平衡性，而且目前這個的解決方案較成熟、固定
5.空間復雜度
散列表: 避免過多散列沖突，裝載因子不能太大，特別基於開放定址法，否則浪費太多空間
② 求個二叉排序樹查找的遞歸演算法
#include<iostream> #include<string> #include<cstring> using namespace std; class BinaryTreeNode {public: string data; int w; BinaryTreeNode *leftchild; BinaryTreeNode *rightchild; BinaryTreeNode *parent; int pos[50]; BinaryTreeNode(string a,int postion) { data=a; w=1; leftchild=NULL; rightchild=NULL; parent=NULL; pos[0]=postion; } }; class BSTree {public: BinaryTreeNode *root; BSTree(){root=NULL;} void Insert(string a,int postion); void Delete(string key); BinaryTreeNode *Search(string key,BinaryTreeNode*& pr,BinaryTreeNode *&parent); void InOrder(BinaryTreeNode *&root); void PreOrder(BinaryTreeNode *&root); }; void BSTree::InOrder(BinaryTreeNode *&root) { if(root) { InOrder(root->leftchild); cout<<root->data; cout<<" "<<root->w<<endl; InOrder(root->rightchild); } } void BSTree::PreOrder(BinaryTreeNode*& root) { if(root) { cout<<root->data; cout<<" "<<root->w<<endl; PreOrder(root->leftchild); PreOrder(root->rightchild); } } BinaryTreeNode *BSTree::Search(string key,BinaryTreeNode*& pr,BinaryTreeNode*& parents) { BinaryTreeNode *p=root; pr=root; while(p) { parents=p; if(key<p->data) { pr=p; p=p->leftchild; } else if(key>p->data) { pr=p; p=p->rightchild; } else return p; } return NULL; } void BSTree::Insert(string a,int postion) { BinaryTreeNode *pr,*p,*pp=NULL; p=Search(a,pr,pp); if(p!=NULL) { p->w++; p->pos[p->w-1]=postion; return; } BinaryTreeNode *r=new BinaryTreeNode(a,postion); if(!root) root=r; else if(a<pp->data) pp->leftchild=r; else pp->rightchild=r; } void BSTree::Delete(string key) { BinaryTreeNode *p,*pr,*pp; p=Search(key,pp,pr); if(p==NULL) return; if(p->leftchild&&p->rightchild) { BinaryTreeNode *s=p->rightchild,*ps=p; while(s->leftchild) { ps=s; s=s->leftchild; } p->data=s->data; p->w=s->w; for(int i=0;i<s->w;i++) { p->pos[i]=s->pos[i]; } pp=ps; p=s; } if(p->leftchild) { if(pp->leftchild==p) { pp->leftchild=p->leftchild; p->leftchild->parent=pp; } else { pp->rightchild=p->leftchild; p->leftchild->parent=pp; } } else if(p->rightchild) { if(pp->leftchild
③ 題目3． 平衡二叉樹演算法查找樹中某節點的時間復雜度是多少
平均查找的時間復雜度為O(log n)。
平衡樹的查找過程和排序樹的相同。在查找過程中和給定值進行比較關鍵字個數不超過樹的深度。
如果二叉樹的元素個數為n，那麼不管是對樹進行插入節點、查找、刪除節點都是log(n)次循環調用就可以了。它的時間復雜度相對於其他數據結構如數組等是最優的。
是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹。常用演算法有紅黑樹、AVL、Treap、伸展樹等。
(3)二叉搜索樹演算法擴展閱讀：
二叉樹也是遞歸定義的，其結點有左右子樹之分，邏輯上二叉樹演算法有五種基本形態：
(1)空二叉樹——(a)
(2)只有一個根結點的二叉樹——(b);
(3)右子樹為空的二叉樹——(c);
(4)左子樹為空的二叉樹——(d);
(5)完全二叉樹——(e)
注意：盡管二叉樹與樹有許多相似之處，但二叉樹不是樹的特殊情形。
④ 二叉樹的深度演算法怎麼算啊
二叉樹的深度演算法：
一、遞歸實現基本思想：
為了求得樹的深度，可以先求左右子樹的深度，取二者較大者加1即是樹的深度，遞歸返回的條件是若節點為空，返回0
演算法：
1
int
FindTreeDeep(BinTree
BT){
2
int
deep=0;
3
if(BT){
4
int
lchilddeep=FindTreeDeep(BT->lchild);
5
int
rchilddeep=FindTreeDeep(BT->rchild);
6
deep=lchilddeep>=rchilddeep?lchilddeep+1:rchilddeep+1;
7
}
8
return
deep;
9
}
二、非遞歸實現基本思想：
受後續遍歷二叉樹思想的啟發，想到可以利用後續遍歷的方法來求二叉樹的深度，在每一次輸出的地方替換成算棧S的大小，遍歷結束後最大的棧S長度即是棧的深度。
演算法的執行步驟如下：
（1）當樹非空時，將指針p指向根節點，p為當前節點指針。
（2）將p壓入棧S中，0壓入棧tag中，並令p執行其左孩子。
（3）重復步驟（2），直到p為空。
（4）如果tag棧中的棧頂元素為1，跳至步驟（6）。從右子樹返回
（5）如果tag棧中的棧頂元素為0，跳至步驟（7）。從左子樹返回
（6）比較treedeep與棧的深度，取較大的賦給treedeep，對棧S和棧tag出棧操作，p指向NULL，並跳至步驟（8）。
（7）將p指向棧S棧頂元素的右孩子，彈出棧tag，並把1壓入棧tag。（另外一種方法，直接修改棧tag棧頂的值為1也可以）
（8）循環（2）~（7），直到棧為空並且p為空
（9）返回treedeep，結束遍歷
1
int
TreeDeep(BinTree
BT
){
2
int
treedeep=0;
3
stack
S;
4
stack
tag;
5
BinTree
p=BT;
6
while(p!=NULL||!isEmpty(S)){
7
while(p!=NULL){
8
push(S,p);
9
push(tag,0);
10
p=p->lchild;
11
}
12
if(Top(tag)==1){
13
deeptree=deeptree>S.length?deeptree:S.length;
14
pop(S);
15
pop(tag);
16
p=NULL;
17
}else{
18
p=Top(S);
19
p=p->rchild;
20
pop(tag);
21
push(tag,1);
22
}
23
}
24
return
deeptree;
25
}