學習筆記—查詢
線性表查詢
順序查詢
儲存結構可以是順序表，也可以是連結串列。
逐個比較查詢，如果找到，返回資料或者索引，如果沒有找到，返回null。
/**
* 時間複雜度T(n) = O(n)
* 空間複雜度S(n) = O(1)
* @param arr 待查詢的陣列
* @param num查詢的值
* @return 如果找到，返回索引；如果未找到，返回-1
*/
public static int search(int [] arr,int num) {
int index = -1;
for(int i = 0; i < arr.length; i ++) {
if(arr[i] == num) {
index = i;
break;
}
}
return index;
}
折半查詢
折半查詢又稱為二分查詢。
這種查詢方法查詢效率高，但查詢表必須滿足兩個條件:
(1) 查詢表必須採用 順序儲存結構
(2) 查詢表內元素必須按大小有序排列
不使用遞迴
/**
* 不使用遞迴的折半查詢
* T(n) = O (logn)
* S(n) = O (1)
* @param array 待查詢的陣列
* @param key查詢的值
* @return如果找到，返回索引；如果未找到，返回-1
*/
public static int binarySearch(int[] array,int key) {
// 指定low 和 high
int low = 0;
int high = array.length - 1;
// 折半查詢
while (low <= high) {
// 求得mid
int mid = (low + high) / 2;
// 判斷是否等於
if(key == array[mid]) {
return mid;
} else if (key < array[mid]) {
high = mid -1;
} else {
low = mid + 1;
}
}
return -1;
}
使用遞迴
/**
* 使用遞迴的折半查詢
* T(n) = O (logn)
* S(n) = O (1*logn)
* @param array 待查詢的陣列
* @param key查詢的值
* @return如果找到，返回索引；如果未找到，返回-1
*/
public static int binarySearch(int [] array,int key) {
// 指定low 和 high
int low = 0;
int high = array.length - 1;
return binarySearch(array,key,low,high);
}
public static int binarySearch(int[] array,int key,int low, int high) {
// 遞迴結束條件
if(low > high) {
return -1;
}
int mid = (low + high) / 2;
if(key == array[mid]) {
return mid;
} else if(key < array[mid]) {
return binarySearch(array,key,low,mid-1);
} else {
return binarySearch(array,key,mid+1,high);
}
}
查詢樹
二叉查詢/搜尋/排序樹 BST （binary search/sort tree）
或者是一棵空樹；
或者是具有下列性質的二叉樹：
（1) 若它的左子樹不空，則左子樹上所有結點的值均不大於它的根結點的值；
（2) 若它的右子樹不空，則右子樹上所有結點的值均不小於它的根結點的值；
（3) 它的左、右子樹也分別為二叉排序樹。
對二叉查詢樹進行中序遍歷，可得到有序集合。
二叉平衡樹（Self-balancing binary search tree）
自平衡二叉查詢樹 又被稱為AVL樹（有別與ALV演算法）
或者是一棵空樹；
或它的左右兩個子樹的高度差 （平衡因子） 的絕對值不超過1，
並且左右兩個子樹都是一棵平衡二叉樹
平衡二叉樹必定是二叉排序樹，反之則不一定。
平衡因子（平衡度） 結點的平衡因子是結點的左子樹與右子樹的高度差。
平衡二叉樹的目的是為了減少二叉查詢樹層次，提高查詢速度
平衡二叉樹的常用實現方法有AVL、紅黑樹、替罪羊樹、Treap、伸展樹等
紅黑樹
R-B Tree，全稱是Red-Black Tree，又稱為“紅黑樹”，它是一種平衡二叉樹。紅黑樹的每個結點上都有儲存位表示結點的顏色，可以是紅（Red）或黑（Black）。
紅黑樹的特性：
（1) 每個結點或者是黑色，或者是紅色。
（2) 根結點是黑色。
（3) 每個葉子結點（NIL）是黑色。[注意：這裡是葉子結點，是指為空（NI或NULL）的葉子結點！]
（4) 如果一個結點是紅色的，則它的子結點必須是黑色的。
（5) 從一個結點到該結點的子孫結點的所有路徑上包含相同數目的黑結點。
確保沒有一條路徑會比其他路徑長出倆倍。因而，紅黑樹是相對是接近平衡的二叉樹。
紅黑樹的應用比較廣泛，主要用它來儲存有序的資料，它的時間複雜度是O(log 2 N),效率非常高。
它雖然是複雜的，但它的最壞情況執行時間也是非常良好的，並且在實踐中是高效的：它可以在O(log n)時間內做查詢，插入和刪除，這裡的n是樹中元素的數目。
例如，Java集合中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虛擬記憶體的管理，都是通過紅黑樹去實現的。
B樹（blanced tree）
與二叉平衡樹相比，是多叉的
可以降低樹的深度，提高查詢效率
B樹應檔案系統的要求而發展起來，大量資料存放在外存中，通常存放在硬碟中。
由於是海量資料，不可能一次調入記憶體。因此，要多次訪問外存。但硬碟的驅動受機械運動的制約，速度慢。
B-tree作為索引組織檔案，提高訪問速度、減少時間。
B+樹
在B-樹基礎上，為葉子結點增加連結串列指標，所有關鍵字都在葉子結點中出現，非葉子結點作為葉子結點的索引；
B+樹總是到葉子結點才命中；
資料庫的索引的預設資料結構就是採用B+樹。
B*樹
是B+樹的變體，在B+樹的非根和非葉子結點再增加指向兄弟的指標
