因為是複習,從基礎開始一起複習。
如果沖着标題來的,可以直接跳到後半部分看B樹的内容(~ ̄▽ ̄)~
支援雲栖社群!同時俺也有自己的獨立部落格——
白水東城,因為在社群部落格裡隻能發發技術文章之類的,但在自己部落格我會寫一些最近随筆和讀書筆記等等哈哈,也希望大家能支援一下 ( •̀ ω •́ )y
這裡是我獨立部落格裡這篇文章的連結:
算法之樹(一,B-樹原理詳解)(Java版)-持續更新補充一、二叉樹
二叉樹的基本操作
public class BinaryTreeNode {
private int data;
private BinaryTreeNode leftChild;
private BinaryTreeNode rightChild;
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public BinaryTreeNode getLeftChild() {
return leftChild;
}
public void setLeftChild(BinaryTreeNode leftChild) {
this.leftChild = leftChild;
}
public BinaryTreeNode getRightChild() {
return rightChild;
}
public void setRightChild(BinaryTreeNode rightChild) {
this.rightChild = rightChild;
}
}
public class BinaryTree {
private BinaryTreeNode root;
public BinaryTree() {
}
public BinaryTree(BinaryTreeNode root) {
this.root = root;
}
public void setRoot(BinaryTreeNode root) {
this.root = root;
}
public BinaryTreeNode getRoot() {
return root;
}
public void clear(BinaryTreeNode node) {
if(node != null) {
clear(node.getLeftChild());
clear(node.getRightChild());
node = null;
}
}
public void clear() {
clear(root);
}
public boolean isEmpty() {
return root == null;
}
public int height() {
return height(root);
}
public int height(BinaryTreeNode node) {
if(node == null) {
return 0;
}else {
int l = height(node.getLeftChild());
int r = height(node.getRightChild());
return l < r ? r + 1 : l + 1;
}
}
public int size() {
return size(root);
}
public int size(BinaryTreeNode node) {
if(node == null) {
return 0;
}else {
return 1 + size(node.getLeftChild()) + size(node.getRightChild());
}
}
public BinaryTreeNode getParent(BinaryTreeNode node) {
return (root == null || root == node) ? null : getParent(root, node);
}
public BinaryTreeNode getParent(BinaryTreeNode subTree, BinaryTreeNode node) {
if(subTree == null) {
return null;
}
if(subTree.getLeftChild() == node || subTree.getRightChild() == node) {
return subTree;
}
BinaryTreeNode parent = null;
if((parent = getParent(subTree.getLeftChild(),node)) != null) {
return parent;
}else {
return getParent(subTree.getRightChild(), node);
}
}
public BinaryTreeNode getLeftTree(BinaryTreeNode node) {
return node.getLeftChild();
}
public BinaryTreeNode getRightTree(BinaryTreeNode node) {
return node.getRightChild();
}
public void insertLeft(BinaryTreeNode parent, BinaryTreeNode newNode) {
parent.setLeftChild(newNode);
}
public void insertRight(BinaryTreeNode parent, BinaryTreeNode newNode) {
parent.setRightChild(newNode);
}
public void visited(BinaryTreeNode node) {
}
public void preOrder(BinaryTreeNode node) {
if(node != null) {
visited(node);
preOrder(node.getLeftChild());
preOrder(node.getRightChild());
}
}
public void inOrder(BinaryTreeNode node) {
if(node != null) {
inOrder(node.getLeftChild());
visited(node);
inOrder(node.getRightChild());
}
}
public void postOrder(BinaryTreeNode node) {
if(node != null) {
postOrder(node.getLeftChild());
postOrder(node.getRightChild());
visited(node);
}
}
}
二、二叉查找樹
簡單來說就是左子樹結點值都小于根結點,右子樹都大于根結點。
二叉查找樹的操作
public class BinarySearchingTree {
private BinaryTreeNode root;
public BinarySearchingTree(BinaryTreeNode root) {
this.root = root;
}
public BinaryTreeNode search(int data) {
return search(root, data);
}
//二叉查找樹的插入操作很簡單,找到和待插入結點同樣值的結點則不插入,
//否則在樹的末尾建立一個結點,不需要變動其他結點
public void insert(int data) {
if(root == null) {
root = new BinaryTreeNode();
root.setData(data);
}else {
searchAndInsert(null, root, data);
}
}
//如果待删除的結點左右子樹都不為空,
//則選擇右子樹的最左結點或者左子樹的最右結點來代替
public void delete(int data) {
if(root.getData() == data) {
root = null;
return;
}
//知道要删除那個結點的父結點很關鍵
//但無法确定要删除的結點是其父結點的左還是右結點
//需要特别判斷一下
BinaryTreeNode parent = searchParent(data);
if(parent == null) {
return;
}
BinaryTreeNode node = search(parent, data);
if(node.getLeftChild() == null && node.getRightChild() == null) {
//葉子結點,直接删除
if(parent.getLeftChild() != null && parent.getLeftChild().getData() == data) {
parent.setLeftChild(null);
}else {
parent.setRightChild(null);
}
}else if(node.getLeftChild() != null && node.getRightChild() == null) {
//左子樹不為空
if(parent.getLeftChild()!= null && parent.getLeftChild().getData() ==data) {
parent.setLeftChild(node.getLeftChild());
}else {
parent.setRightChild(node.getRightChild());
}
}else if(node.getLeftChild() == null && node.getClass() != null) {
//右子樹不為空
if(parent.getLeftChild() != null && parent.getLeftChild().getData() == data) {
parent.setLeftChild(node.getRightChild());
}else {
parent.setRightChild(node.getRightChild());
}
}else {
//左右子樹都不為空
//查找右子樹最左子節點
BinaryTreeNode deleteNode = node;
BinaryTreeNode temp = node.getRightChild();
//1. 右子樹沒有左孩子,直接上移
if(temp.getLeftChild() == null) {
temp.setLeftChild(deleteNode.getLeftChild());
}else {
while(temp.getLeftChild() != null) {
node = temp;
temp = temp.getLeftChild();
}
//2. 繼承節點原右子樹上移
node.setLeftChild(temp.getRightChild());
//3. 繼承節點就位
temp.setLeftChild(deleteNode.getLeftChild());
temp.setRightChild(deleteNode.getRightChild());
}
//4. 更新父節點為删除結點的原父節點
if(parent.getLeftChild() != null && parent.getLeftChild().getData() == data) {
parent.setLeftChild(temp);
}else {
parent.setRightChild(temp);
}
}
}
public BinaryTreeNode searchParent(int data) {
return searchParent(null, root, data);
}
public BinaryTreeNode getRoot() {
return root;
}
private BinaryTreeNode searchAndInsert(BinaryTreeNode parent, BinaryTreeNode node, int data) {
if(node == null) {
node = new BinaryTreeNode();
node.setData(data);
if(data > parent.getData()) {
parent.setRightChild(node);
}else {
parent.setLeftChild(node);
}
return node;
}else if(node.getData() == data) {
return node;
}else if(data > node.getData()) {
return searchAndInsert(node, node.getRightChild(), data);
}else {
return searchAndInsert(node, node.getLeftChild(), data);
}
}
private BinaryTreeNode search(BinaryTreeNode node, int data) {
if(node == null) {
return null;
}else if(node.getData() == data) {
return node;
}else if(data > node.getData()) {
return search(node.getRightChild(), data);
}else {
return search(node.getLeftChild(), data);
}
}
private BinaryTreeNode searchParent(BinaryTreeNode parent, BinaryTreeNode node, int data) {
if(node == null) {
return null;
}else if(node.getData() == data) {
return parent;
}else if(data > node.getData()) {
return searchParent(node, node.getRightChild(), data);
}else {
return searchParent(node, node.getLeftChild(), data);
}
}
}
三、平衡二叉樹
Balanced Binary Tree,又叫AVL樹(由提出者名字縮寫而來)。簡單來說,在二叉查找樹的基礎上,要保持左右子樹高度差不超過1,我們把左子樹高度減去右子樹高度叫做平衡因子(Balanced Factor,BF)
二叉查找樹查找的時間複雜度最好是O(logn),最壞是O(n),而AVL最好最壞都是O(logn),插入和删除也是O(logn)。
代碼暫時省略,以後回來補充
四、B-樹、B+樹
B-樹
B減樹和B樹是一個意思,那個不是減号而是短橫。這個不糾結,意思明白就行。
B樹是用于在外存工作的平衡搜尋樹,MySQL中的索引主要是基于hash表或者B+樹。
為什麼不用二叉查找樹?
資料庫索引為啥不用二叉查找樹實作呢?
二叉查找樹的時間複雜度為O(logn),從算法邏輯上講查找速度和比較次數都是最小的。但是,現實要考慮 磁盤IO。
資料庫索引是存在磁盤上的,因為資料量很大的時候索引大小可能達到幾個G。是以在利用索引查詢的時候,不能把整個索引全部加載到記憶體,隻有逐一加載每一個磁盤頁,這裡磁盤頁對應着索引樹的節點,如圖(圖檔源于程式員小灰)。
當資料比較大,無法全部存入記憶體時,需要将部分資料存在外存中,在需要的時候讀入記憶體,修改之後又寫回外存。由于外存的速度與記憶體有幾個數量級的差别,是以節省在外存上花的時間,對搜尋樹的性能提高時最有效的。
最常見的外存就是磁盤。磁盤是塊裝置,也就是說磁盤的讀寫機關是以塊為機關,一般地塊大小從0.5k到4k。即使你隻讀取一個位元組,磁盤也是将包含該位元組的所有資料讀取到硬碟中。而在磁盤讀取過程中,最占用時間的是磁盤的尋道,也就是磁頭在盤片上找到需要讀取的塊所在位置的時間,而在盤片上順序讀取資料的所花的時間是占比比較小的。
要減少外存上花的時間,就可以從減少讀盤次數以及減少尋道時間着手。B樹采取的方法就是,就充分的利用盤塊的空間,在一個盤塊中盡可能多的存儲資訊,或者在連續的盤塊位址上存儲盡可能多的資訊。在資料結構上的變化就是每個節點存儲多個key資訊以及包含多個子節點。
磁盤的IO次數由樹的高度決定的,在最壞的情況下磁盤的IO數等于索引樹的高度。而B-樹是一棵平衡的m-路查找樹,一個m-路查找樹,高度為h,每一個節點最多容納m-1個關鍵字,是以一棵m-路查找樹總共可容納
m^k - 1
個關鍵字。
與二叉查找樹比較,當高度為h,能容納
2^h - 1
個關鍵字,高度若為3,則二叉查找樹隻能容納7個關鍵字;而對于200-路查找樹可以容納
200^3 - 1
個關鍵字!
再說回來,為了減少磁盤的IO次數,就需要把原來“瘦高”的樹結構變得“矮胖”,而這個正滿足B樹的特征之一。
B樹是多路平衡查找樹,它的每一個節點最多包含k個孩子,k被稱為B樹的階,k的大小取決于磁盤頁的大小。就像剛才舉例200-路查找樹一樣。
B樹檔案查找的具體過程
假設每一個磁盤頁正好存放一個B樹的節點,而子樹的指針就是存放另一個磁盤頁的位址。
那麼查找操作就是:首先是根節點(從磁盤調出資料,進行第一次磁盤I/O,資料讀入記憶體進行查找),記憶體中可以順序也可以二分,如果找到要查找的那個數則OK,否則要确認指針的位置,也就是确認是那棵子樹,然後遞歸下去。
圖檔來自: v_JULY_v的CSDN部落格
B樹的特征
- 根結點至少有兩個子女。
- 每個中間節點都包含k-1個元素和k個孩子,其中 m/2 <= k <= m
- 每一個葉子節點都包含k-1個元素,其中 m/2 <= k <= m
- 所有的葉子結點都位于同一層。
- 每個節點中的元素從小到大排列,節點當中k-1個元素正好是k個孩子包含的元素的值域分劃。
B樹在查詢中比較的次數不比二叉查找樹少,但是因為B樹把多個關鍵字放在了同一個節點中,這樣減少了磁盤的IO次數,同時在記憶體中比較耗時幾乎可以忽略,是以隻要樹高度足夠低,IO次數足夠少,就能調高查找性能。
B樹的應用場景
B-樹主要用于檔案系統以及部分資料庫索引,比如非關系型資料庫MongoDB。
B樹的代碼實作
先mark在這,暫時不打算搞。
OK,下一篇接着搞樹!總結了幾個大牛的書和部落格的内容,記下筆記,也希望能對你有幫助( ̄︶ ̄)↗
看到這裡一定是真愛了,有啥疑惑可以留言噢~~
沒有的話,再看看我的獨立部落格——
也OK!哈哈
獨立部落格剛搞不久,支援雲栖社群,也希望大家能支援下俺的部落格= ̄ω ̄=
參考
- 《輕松學算法》趙烨
- 漫畫:什麼是B-樹(程式員小灰)
- 從B樹、B+樹、B*樹談到R 樹
- B樹(Java)實作