樹論（樹形結(jié)構(gòu)、二叉樹、二叉搜索樹、紅黑樹、Btree、B+Tree、赫夫曼樹、堆樹）
樹形結(jié)構(gòu)概念
在樹形結(jié)構(gòu)里面重要的術(shù)語：
-
結(jié)點(diǎn)：樹里面的元素。
-
父子關(guān)系：結(jié)點(diǎn)之間相連的邊
-
子樹：當(dāng)結(jié)點(diǎn)大于1時(shí)，其余的結(jié)點(diǎn)分為的互不相交的集合稱為子樹
-
度：一個(gè)結(jié)點(diǎn)擁有的子樹數(shù)量稱為結(jié)點(diǎn)的度
-
葉子：度為0的結(jié)點(diǎn)
-
孩子：結(jié)點(diǎn)的子樹的根稱為孩子結(jié)點(diǎn)
-
雙親：和孩子結(jié)點(diǎn)對(duì)應(yīng)
-
兄弟：同一個(gè)雙親結(jié)點(diǎn)
-
森林：由N個(gè)互不相交的樹構(gòu)成深林
-
結(jié)點(diǎn)的高度：結(jié)點(diǎn)到葉子結(jié)點(diǎn)的最長路徑
-
結(jié)點(diǎn)的深度：根結(jié)點(diǎn)到該結(jié)點(diǎn)的邊個(gè)數(shù)
-
結(jié)點(diǎn)的層數(shù)：結(jié)點(diǎn)的深度加1
-
樹的高度：根結(jié)點(diǎn)的高度
二叉樹
Binary Tree: 一種特殊的樹形結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)至多只有兩顆子樹
在二叉樹的第N層上至多有2^(N-1)個(gè)結(jié)點(diǎn)。最多有2^N-1個(gè)結(jié)點(diǎn)個(gè)數(shù)。
分類：
- 滿二叉樹：除葉子結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都有左右兩個(gè)子結(jié)點(diǎn)。
- 完全二叉樹：除最后一層外，其他的結(jié)點(diǎn)個(gè)數(shù)必須達(dá)到最大，并且最后一層結(jié)點(diǎn)都連續(xù)靠左排列。
思考
為什么要分滿二叉樹和完全二叉樹呢？因?yàn)橥ㄟ^定義可以看出，完全二叉樹只是滿二叉樹里面的一個(gè)子集
數(shù)組：性能高效，如果不是完全二叉樹浪費(fèi)空間
鏈表：也可以實(shí)現(xiàn)，性能沒有數(shù)組高
二叉樹遍歷
- 重要口訣：根節(jié)點(diǎn)輸出！子樹
- 前序：根 左 右 （A B C D E F G H K）
- 中序：左 根 右 （B C D A E F G H K）
- 后序：左 右 根 （B C D E F G H K A）
/**
* 二叉樹--前中后鏈?zhǔn)奖闅v
* 前: A B C D E F G H K
* 中: B C D A E F G H K
* 后: B C D E F G H K A
* 層:
* A
* B E
* C F
* D G
* H K
*/
@Data
class TreeNode {
private char data;
private TreeNode left;
private TreeNode right;
public TreeNode(char data, TreeNode left, TreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}
}
public class BinaryTree {
public void print(TreeNode node) {
System.out.print(node.getData() + " ");
}
public void pre(TreeNode root) { //前序：根(輸出) 左 右 A B C D E F G H K
print(root);
if (root.getLeft() != null) {
pre(root.getLeft()); //認(rèn)為是子樹，分解子問題
}
if (root.getRight() != null) {
pre(root.getRight());
}
}
public void in(TreeNode root) { //中序：左 根(輸出) 右 B C D A E F G H K
if (root.getLeft() != null) {
pre(root.getLeft()); //認(rèn)為是子樹，分解子問題
}
print(root);
if (root.getRight() != null) {
pre(root.getRight());
}
}
public void post(TreeNode root) { //后序：左 右 根(輸出) B C D E F G H K A
if (root.getLeft() != null) {
pre(root.getLeft()); //認(rèn)為是子樹，分解子問題
}
if (root.getRight() != null) {
pre(root.getRight());
}
print(root);
}
public List<List<Character>> level(TreeNode root) { //層次遍歷
if (root == null) return Collections.EMPTY_LIST;
List<List<Character>> res = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
List<Character> raw = new ArrayList<>();
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode item = queue.poll();
raw.add(item.getData());
if (item.getLeft() != null) {
queue.add(item.getLeft());
}
if (item.getRight() != null) {
queue.add(item.getRight());
}
}
res.add(raw);
}
return res;
}
public static void main(String[] args) {
TreeNode D = new TreeNode('D', null,null);
TreeNode H = new TreeNode('H', null,null);
TreeNode K = new TreeNode('K', null,null);
TreeNode C = new TreeNode('C', D,null);
TreeNode G = new TreeNode('G', H,K);
TreeNode B = new TreeNode('B', null,C);
TreeNode F = new TreeNode('F', G,null);
TreeNode E = new TreeNode('E', F,null);
TreeNode A = new TreeNode('A', B,E);
BinaryTree tree = new BinaryTree();
System.out.print("前: ");
tree.pre(A);
System.out.println();
System.out.print("中: ");
tree.in(A);
System.out.println();
System.out.print("后: ");
tree.post(A);
System.out.println();
System.out.println("層: ");
List<List<Character>> res = tree.level(A);
for (List<Character> re : res) {
for (Character character : re) {
System.out.print(character + " ");
}
System.out.println();
}
}
}
二叉搜索樹（二叉查找樹、二叉排序數(shù)）
- 如果它的左子樹不為空，則左子樹上結(jié)點(diǎn)的值都小于根結(jié)點(diǎn)
- 如果它的右子樹不為空，則右子樹上結(jié)點(diǎn)的值都大于根結(jié)點(diǎn)
- 子樹同樣也要遵循以上兩點(diǎn)
中序遍歷 ---- 左 根（輸出） 右：0 3 4 5 6 8
性能分析
- 查找logn
- 插入nlogn
- 刪除
-
- 要?jiǎng)h除的結(jié)點(diǎn)是葉子結(jié)點(diǎn) O(1)
-
- 要?jiǎng)h除的結(jié)點(diǎn)只有一個(gè)子樹（左或者右）O(1)
-
- 要?jiǎng)h除的結(jié)點(diǎn)有兩顆子樹：找后繼結(jié)點(diǎn)，而且后繼結(jié)點(diǎn)的左子樹一定為空 logn
-
/**
* 二叉搜索樹 增刪改查
*/
class BinaryNodeTeacher {
int data;
BinaryNodeTeacher left;
BinaryNodeTeacher right;
BinaryNodeTeacher parent;
public BinaryNodeTeacher(int data) {
this.data = data;
this.left = null;
this.right = null;
this.parent = null;
}
}
public class BinarySearchTreeTeacher {
public BinaryNodeTeacher find(BinaryNodeTeacher root, int key) {
BinaryNodeTeacher current = root;
while (current != null) {
if (key < current.data) {
current = current.left;
} else if (key > current.data) {
current = current.right;
} else {
return current;
}
}
return null;
}
public void insert(BinaryNodeTeacher root, int data) {
if (root.data < data) {
if (root.right != null) {
insert(root.right, data);
} else {
BinaryNodeTeacher newNode = new BinaryNodeTeacher(data);
newNode.parent = root;
root.right = newNode;
}
} else {
if (root.left != null) {
insert(root.left, data);
} else {
BinaryNodeTeacher newNode = new BinaryNodeTeacher(data);
newNode.parent = root;
root.left = newNode;
}
}
}
public BinaryNodeTeacher finSuccessor(BinaryNodeTeacher node) { // 查找node的后繼節(jié)點(diǎn)
if (node.right == null) { // 表示沒有右邊 那就沒有后繼
return node;
}
BinaryNodeTeacher cur = node.right;
BinaryNodeTeacher pre = node.right; // 開一個(gè)額外的空間 用來返回后繼節(jié)點(diǎn)，因?yàn)槲覀円业綖榭盏臅r(shí)候，那么其實(shí)返回的是上一個(gè)節(jié)點(diǎn)
while (cur != null) {
pre = cur;
cur = cur.left; // 注意后繼節(jié)點(diǎn)是要往左邊找，因?yàn)橛疫叺目隙ū茸筮叺拇?，我們要找的是第一個(gè)比根節(jié)點(diǎn)小的，所以只能往左邊
}
return pre; // 因?yàn)閏ur會(huì)變成null，實(shí)際我們是要cur的上一個(gè)點(diǎn)，所以就是pre來代替
}
public BinaryNodeTeacher remove(BinaryNodeTeacher root, int data) { // 刪除data
BinaryNodeTeacher delNode = find(root, data);
if (delNode == null) {
System.out.println("要?jiǎng)h除的值不在樹中");
return root;
}
// 1.刪除的點(diǎn)沒有左右子樹
if (delNode.left == null && delNode.right == null) {
if (delNode == root) {
root = null;
} else if (delNode.parent.data < delNode.data) { // 說明刪除的點(diǎn)是右子節(jié)點(diǎn)
delNode.parent.right = null;
} else {
delNode.parent.left = null;
}
} else if (delNode.left != null && delNode.right != null) { // 2.刪除的節(jié)點(diǎn)有兩顆子節(jié)點(diǎn)
BinaryNodeTeacher successor = finSuccessor(delNode); // 先找的后繼節(jié)點(diǎn)
// 后繼節(jié)點(diǎn)和刪除節(jié)點(diǎn)進(jìn)行交換，首先后繼節(jié)點(diǎn)的左節(jié)點(diǎn)是肯定為空的
successor.left = delNode.left; // 后繼的左邊變?yōu)閯h除的左邊
successor.left.parent = successor; // 刪除點(diǎn)的左邊parent指向后繼節(jié)點(diǎn)
// 再來看后繼節(jié)點(diǎn)的右邊
if (successor.right != null && successor.parent != delNode) { // 后繼節(jié)點(diǎn)有右邊,這其實(shí)就是下面情況3的第一種
successor.right.parent = successor.parent;
successor.parent.left = successor.right;
successor.right = delNode.right;
successor.right.parent = successor;
}else if(successor.right == null) { //如果后繼節(jié)點(diǎn)沒有右邊,那其實(shí)就是情況1，沒有左右子樹
if(successor.parent != delNode) { //如果后繼節(jié)點(diǎn)的parent不等于刪除的點(diǎn) 那么就需要把刪除的右子樹賦值給后繼節(jié)點(diǎn)
successor.parent.left = null; //注意原來的后繼節(jié)點(diǎn)上的引用要?jiǎng)h掉,否則會(huì)死循環(huán)
successor.right = delNode.right;
successor.right.parent = successor;
}
}
// 替換做完接下來就要?jiǎng)h除節(jié)點(diǎn)了
if (delNode == root) {
successor.parent = null;
root = successor;
return root;
}
successor.parent = delNode.parent;
if (delNode.data > delNode.parent.data) { // 刪除的點(diǎn)在右邊，關(guān)聯(lián)右子樹
delNode.parent.right = successor;
} else {
delNode.parent.left = successor;
}
} else { // 3.刪除點(diǎn)有一個(gè)節(jié)點(diǎn)
if (delNode.right != null) { // 有右節(jié)點(diǎn)
if (delNode == root) {
root = delNode.right;
return root;
}
delNode.right.parent = delNode.parent; // 把右節(jié)點(diǎn)的parent指向刪除點(diǎn)的parent
// 關(guān)聯(lián)父節(jié)點(diǎn)的左右子樹
if (delNode.data < delNode.parent.data) { // 刪除的點(diǎn)在左邊
delNode.parent.left = delNode.right;
} else {
delNode.parent.right = delNode.right;
}
} else {
if (delNode == root) {
root = delNode.left;
return root;
}
delNode.left.parent = delNode.parent;
if (delNode.data < delNode.parent.data) {
delNode.parent.left = delNode.left;
} else {
delNode.parent.right = delNode.left;
}
}
}
return root;
}
public void inOrde(BinaryNodeTeacher root) {
if (root != null) {
inOrde(root.left);
System.out.print(root.data);
inOrde(root.right);
}
}
// 用于獲得樹的層數(shù)
public int getTreeDepth(BinaryNodeTeacher root) {
return root == null ? 0 : (1 + Math.max(getTreeDepth(root.left), getTreeDepth(root.right)));
}
/**
*
* 測試用例
* 15
* 10
* 19
* 8
* 13
* 16
* 28
* 5
* 9
* 12
* 14
* 20
* 30
* -1
* 刪除：15 8 5 10 12 19 16 14 30 9 13 20 28
*
* 15
* / \
* 10 19
* / \ / \
* 8 13 16 28
* / \ / \ / \
* 5 9 12 14 20 30
*/
public static void main(String[] args) {
BinarySearchTreeTeacher binarySearchTree = new BinarySearchTreeTeacher();
BinaryNodeTeacher root = null;
Scanner cin = new Scanner(System.in);
int t = 1;
System.out.println("二叉搜索樹假定不存重復(fù)的子節(jié)點(diǎn),重復(fù)可用鏈表處理，請(qǐng)注意~~");
System.out.println("請(qǐng)輸入根節(jié)點(diǎn):");
int rootData = cin.nextInt();
root = new BinaryNodeTeacher(rootData);
System.out.println("請(qǐng)輸入第" + t + "個(gè)點(diǎn):輸入-1表示結(jié)束");
while (true) { //
int data = cin.nextInt();
if (data == -1)
break;
binarySearchTree.insert(root, data);
t++;
System.out.println("請(qǐng)輸入第" + t + "個(gè)點(diǎn):輸入-1表示結(jié)束");
}
binarySearchTree.show(root); //找的別人寫的打印二叉樹形結(jié)構(gòu)，感覺還不錯(cuò)，可以更加清晰
System.out.println("刪除測試:");
while(true) {
System.out.println("請(qǐng)輸入要?jiǎng)h除的點(diǎn)：-1表示結(jié)束");
int key = cin.nextInt();
root = binarySearchTree.remove(root, key);
binarySearchTree.show(root);
if(root == null) {
System.out.println("樹已經(jīng)沒有數(shù)據(jù)了~~");
break;
}
}
}
private void writeArray(BinaryNodeTeacher currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
// 保證輸入的樹不為空
if (currNode == null)
return;
// 先將當(dāng)前節(jié)點(diǎn)保存到二維數(shù)組中
res[rowIndex][columnIndex] = String.valueOf(currNode.data);
// 計(jì)算當(dāng)前位于樹的第幾層
int currLevel = ((rowIndex + 1) / 2);
// 若到了最后一層，則返回
if (currLevel == treeDepth)
return;
// 計(jì)算當(dāng)前行到下一行，每個(gè)元素之間的間隔（下一行的列索引與當(dāng)前元素的列索引之間的間隔）
int gap = treeDepth - currLevel - 1;
// 對(duì)左兒子進(jìn)行判斷，若有左兒子，則記錄相應(yīng)的"/"與左兒子的值
if (currNode.left != null) {
res[rowIndex + 1][columnIndex - gap] = "/";
writeArray(currNode.left, rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
}
// 對(duì)右兒子進(jìn)行判斷，若有右兒子，則記錄相應(yīng)的"\"與右兒子的值
if (currNode.right != null) {
res[rowIndex + 1][columnIndex + gap] = "\\";
writeArray(currNode.right, rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
}
}
public void show(BinaryNodeTeacher root) {
if (root == null) {
System.out.println("EMPTY!");
return ;
}
// 得到樹的深度
int treeDepth = getTreeDepth(root);
// 最后一行的寬度為2的（n - 1）次方乘3，再加1
// 作為整個(gè)二維數(shù)組的寬度
int arrayHeight = treeDepth * 2 - 1;
int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
// 用一個(gè)字符串?dāng)?shù)組來存儲(chǔ)每個(gè)位置應(yīng)顯示的元素
String[][] res = new String[arrayHeight][arrayWidth];
// 對(duì)數(shù)組進(jìn)行初始化，默認(rèn)為一個(gè)空格
for (int i = 0; i < arrayHeight; i++) {
for (int j = 0; j < arrayWidth; j++) {
res[i][j] = " ";
}
}
// 從根節(jié)點(diǎn)開始，遞歸處理整個(gè)樹
writeArray(root, 0, arrayWidth / 2, res, treeDepth);
// 此時(shí)，已經(jīng)將所有需要顯示的元素儲(chǔ)存到了二維數(shù)組中，將其拼接并打印即可
for (String[] line : res) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < line.length; i++) {
sb.append(line[i]);
if (line[i].length() > 1 && i <= line.length - 1) {
i += line[i].length() > 4 ? 2 : line[i].length() - 1;
}
}
System.out.println(sb.toString());
}
}
}
紅黑樹（實(shí)驗(yàn)室：AVL平衡二叉樹）二叉搜索樹退化成鏈表
紅黑樹的性質(zhì)：
- 每個(gè)結(jié)點(diǎn)不是紅色就是黑色
- 不可能有連在一起的紅色結(jié)點(diǎn)（黑色的就可以），每個(gè)葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)（NIL），也就是說，葉子節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)
- 根結(jié)點(diǎn)都是黑色 root
- 每個(gè)節(jié)點(diǎn)，從該節(jié)點(diǎn)到達(dá)其可達(dá)葉子節(jié)點(diǎn)的所有路徑，都包含相同數(shù)目的黑色節(jié)點(diǎn)
插入的時(shí)候旋轉(zhuǎn)和顏色變換規(guī)則：
- 變顏色的情況：當(dāng)前結(jié)點(diǎn)的父親是紅色，且它的祖父結(jié)點(diǎn)的另一個(gè)子結(jié)點(diǎn)
也是紅色。（叔叔結(jié)點(diǎn)）：
（1）把父節(jié)點(diǎn)設(shè)為黑色
（2）把叔叔也設(shè)為黑色
（3）把祖父也就是父親的父親設(shè)為紅色（爺爺）
（4）把指針定義到祖父結(jié)點(diǎn)(爺爺)設(shè)為當(dāng)前要操作的. - 左旋：當(dāng)前父結(jié)點(diǎn)是紅色，叔叔是黑色的時(shí)候，且當(dāng)前的結(jié)點(diǎn)是右子樹。左旋
以父結(jié)點(diǎn)作為左旋。指針變換到父親結(jié)點(diǎn) - 右旋：當(dāng)前父結(jié)點(diǎn)是紅色，叔叔是黑色的時(shí)候，且當(dāng)前的結(jié)點(diǎn)是左子樹。右旋
（1）把父結(jié)點(diǎn)變?yōu)楹谏?br> （2）把祖父結(jié)點(diǎn)變?yōu)榧t色 （爺爺）
（3）以祖父結(jié)點(diǎn)旋轉(zhuǎn)（爺爺）
左旋
右旋
紅黑樹的應(yīng)用
- HashMap
- TreeMap
- Windows底層：查找
- Linux進(jìn)程調(diào)度，nginx等
COPY
public class RedBlackTree {
private final int R = 0;
private final int B = 1;
private class Node {
int key = -1;
int color = B; // 顏色
Node left = nil; // nil表示的是葉子結(jié)點(diǎn)
Node right = nil;
Node p = nil;
Node(int key) {
this.key = key;
}
@Override
public String toString() {
return "Node [key=" + key + ", color=" + color + ", left=" + left.key + ", right=" + right.key + ", p=" + p.key + "]" + "\r\n";
}
}
private final Node nil = new Node(-1);
private Node root = nil;
public void printTree(Node node) {
if (node == nil) {
return;
}
printTree(node.left);
System.out.print(node.toString());
printTree(node.right);
}
private void insert(Node node) {
Node temp = root;
if (root == nil) {
root = node;
node.color = B;
node.p = nil;
} else {
node.color = R;
while (true) {
if (node.key < temp.key) {
if (temp.left == nil) {
temp.left = node;
node.p = temp;
break;
} else {
temp = temp.left;
}
} else if (node.key >= temp.key) {
if (temp.right == nil) {
temp.right = node;
node.p = temp;
break;
} else {
temp = temp.right;
}
}
}
fixTree(node);
}
}
private void fixTree(Node node) {
while (node.p.color == R) {
Node y = nil;
if (node.p == node.p.p.left) {
y = node.p.p.right;
if (y != nil && y.color == R) {
node.p.color = B;
y.color = B;
node.p.p.color = R;
node = node.p.p;
continue;
}
if (node == node.p.right) {
node = node.p;
rotateLeft(node);
}
node.p.color = B;
node.p.p.color = R;
rotateRight(node.p.p);
} else {
y = node.p.p.left;
if (y != nil && y.color == R) {
node.p.color = B;
y.color = B;
node.p.p.color = R;
node = node.p.p;
continue;
}
if (node == node.p.left) {
node = node.p;
rotateRight(node);
}
node.p.color = B;
node.p.p.color = R;
rotateLeft(node.p.p);
}
}
root.color = B;
}
void rotateLeft(Node node) {
if (node.p != nil) {
if (node == node.p.left) {
node.p.left = node.right;
} else {
node.p.right = node.right;
}
node.right.p = node.p;
node.p = node.right;
if (node.right.left != nil) {
node.right.left.p = node;
}
node.right = node.right.left;
node.p.left = node;
} else {
Node right = root.right;
root.right = right.left;
right.left.p = root;
root.p = right;
right.left = root;
right.p = nil;
root = right;
}
}
void rotateRight(Node node) {
if (node.p != nil) {
if (node == node.p.left) {
node.p.left = node.left;
} else {
node.p.right = node.left;
}
node.left.p = node.p;
node.p = node.left;
if (node.left.right != nil) {
node.left.right.p = node;
}
node.left = node.left.right;
node.p.right = node;
} else {
Node left = root.left;
root.left = root.left.right;
left.right.p = root;
root.p = left;
left.right = root;
left.p = nil;
root = left;
}
}
public void creatTree() {
int data[]= {23,32,15,221,3};
Node node;
System.out.println(Arrays.toString(data));
for(int i = 0 ; i < data.length ; i++) {
node = new Node(data[i]);
insert(node);
}
printTree(root);
}
/**
* [23, 32, 15, 221, 3]
* Node [key=3, color=0, left=-1, right=-1, p=15]
* Node [key=15, color=1, left=3, right=-1, p=23]
* Node [key=23, color=1, left=15, right=32, p=-1]
* Node [key=32, color=1, left=-1, right=221, p=23]
* Node [key=221, color=0, left=-1, right=-1, p=32]
*/
public static void main(String[] args) {
RedBlackTree bst = new RedBlackTree();
bst.creatTree();
}
}
Btree&B+Tree
B-Tree和B+Tree的區(qū)別
- B-tree所有的節(jié)點(diǎn)都會(huì)存數(shù)據(jù)
- b-tree葉子節(jié)點(diǎn)沒有鏈表
數(shù)據(jù)庫索引是什么樣的數(shù)據(jù)結(jié)構(gòu)呢？它為什么又能這么高效的查找呢？究竟使用了什么樣的算法呢？
select * from table where id = 10
select * from table where id > 12
select * from table where id > 12 and id < 20
改造二叉搜索樹：
能解決我們上面所有的sql語句；
效率 logn
2^32=21億；
IO：指的是從磁盤讀取數(shù)據(jù)。32層就要讀取32次。CPU,內(nèi)存，IO；
IO從磁盤讀一次會(huì)讀多少數(shù)據(jù)？計(jì)算機(jī)組成原理。Page的。頁，4KB
Int占多少空間？4B
思考
問題1：搜索效率：32次 （B+Tree 多叉樹）
問題2：查詢次數(shù)： (B+Tree 范圍 )
問題3：磁盤IO：解決這個(gè)問題；(B+Tree 只有葉子節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)地址)
B+Tree 數(shù)據(jù)結(jié)構(gòu)
Mysql 如何利用B+Tree 解決問題
Mysql 通過頁大小決定，一般是16kb，一個(gè)bigint主鍵類型創(chuàng)建索引消耗的空間是多少？
int 8 字節(jié)，指針一個(gè)算4字節(jié)，一頁的節(jié)點(diǎn)：16kb/(8+8)=1k 鍵值+指針
三階：102410241024=10 7374 1824
如何正確的建立索引：
- 索引不能太多，因?yàn)锽+tree的插入和刪除是要維護(hù)的，太多的索引會(huì)導(dǎo)致插入變慢。
- 建了索引的字段不能使用like ‘%%’否則是失效的
- 建索引的字段類型不能太大，字段越小階數(shù)就越大，效率就越高，int 和 bigint，varchar（10），varchar（100），text，lontext；B+Tree。全文索引
- 建索引的字段值不能太多一樣的，數(shù)學(xué)里面有個(gè)叫什么散列多一些（離散），比如我們把性別建索引會(huì)出現(xiàn)啥情況？左邊都是一樣的值 過濾不了一半。User sex單獨(dú)建索引 0 1
- 聯(lián)合索引的最左匹配原則。Select * from user where name = ‘mx’ and id = 1 我的對(duì)（ id,name)建的索引，mysql解析的時(shí)候會(huì)自動(dòng)優(yōu)化。
Select * from user where name = ‘mx’ and age=10我的對(duì)（ id,name,age)建的索引 - NOT IN 是不會(huì)走索引的 not in (1,2,3) In的值太多 mysql會(huì)報(bào)錯(cuò)的
赫夫曼樹（哈夫曼樹、哈夫曼編碼、前綴編碼）-- 壓縮軟件、通信電報(bào)
電報(bào)的設(shè)計(jì)：
1.電報(bào)加密后越短越好，發(fā)送快
2.破解難
3.解碼容易
4.換加密樹也要快
5.可逆的
計(jì)算下面三顆二叉樹的帶權(quán)路徑長度總和：
WPL(a):7*2+5*2+2*2+4*2=36()
WPL(b):7*3+5*3+2*1+4*2=46()
WPL(c):7*1+5*2+2*3+4*3=35()
左節(jié)點(diǎn)的邊設(shè)置為0
右節(jié)點(diǎn)的邊設(shè)置為1
? 哈夫曼編碼就是
A：0
B：10
C：110
D：111
構(gòu)建哈夫曼樹：
1.每次取數(shù)值最小的兩個(gè)節(jié)點(diǎn)，將之組成為一顆子樹。
2.移除原來的兩個(gè)點(diǎn)
3.然后將組成的子樹放入原來的序列中
4.重復(fù)執(zhí)行1 2 3 直到只剩最后一個(gè)點(diǎn)
/**
* 赫夫曼樹
*/
class HuffmanNode implements Comparable<HuffmanNode> {
String chars;
int fre; //頻率 權(quán)重
HuffmanNode parent;
HuffmanNode left;
HuffmanNode right;
@Override
public int compareTo(HuffmanNode o) {
return this.fre - o.fre;
}
}
public class HuffmanTree {
HuffmanNode root;
List<HuffmanNode> leafs; //葉子節(jié)點(diǎn)
Map<Character, Integer> weights; //葉子節(jié)點(diǎn)
Map<Character, String> charmap;
Map<String, Character> mapchar;
public HuffmanTree(Map<Character,Integer> weights) {
this.weights = weights;
leafs = new ArrayList<>();
charmap = new HashMap<>();
mapchar = new HashMap<>();
}
public void code() {
for (HuffmanNode node : leafs) {
Character c = new Character(node.chars.charAt(0));
HuffmanNode current = node;
String code = "";
do {
if (current.parent != null && current == current.parent.left) { //left
code = "0" + code;
} else {
code = "1" + code;
}
current = current.parent;
} while (current.parent != null);
charmap.put(c, code);
mapchar.put(code, c);
}
}
public void createTree() {
Character keys[] = weights.keySet().toArray(new Character[0]);
PriorityQueue<HuffmanNode> priorityQueue = new PriorityQueue<>();
for (Character key : keys) {
HuffmanNode huffmanNode = new HuffmanNode();
huffmanNode.chars = key.toString();
huffmanNode.fre = weights.get(key);
priorityQueue.add(huffmanNode);
leafs.add(huffmanNode);
}
int len = priorityQueue.size();
for (int i = 1; i <= len-1; i++) {
HuffmanNode n1 = priorityQueue.poll();
HuffmanNode n2 = priorityQueue.poll();
HuffmanNode newNode = new HuffmanNode();
newNode.fre = n1.fre + n2.fre;
newNode.chars = n1.chars + n2.chars;
newNode.left = n1;
newNode.right = n2;
n1.parent = newNode;
n2.parent = newNode;
priorityQueue.add(newNode);
}
root = priorityQueue.poll();
}
public String encode(String body) {
StringBuilder builder = new StringBuilder();
for (char c : body.toCharArray()) {
builder.append(charmap.get(c));
}
return builder.toString();
}
public String decode(String body) {
StringBuilder builder = new StringBuilder();
while (!body.equals("")) {
for (String code : mapchar.keySet()) {
if (body.startsWith(code)) {
body = body.replaceFirst(code,"");
builder.append(mapchar.get(code));
}
}
}
return builder.toString();
}
/**
* a : 10110
* b : 01
* c : 1010
* d : 00
* e : 11
* f : 10111
* g : 100
* encode: 0010111101111010
* decode: dffc
*/
public static void main(String[] args) {
Map<Character, Integer> weights = new HashMap<>();
weights.put('a',3);
weights.put('b',24);
weights.put('c',6);
weights.put('d',20);
weights.put('e',34);
weights.put('f',4);
weights.put('g',12);
HuffmanTree huffmanTree = new HuffmanTree(weights);
huffmanTree.createTree();
huffmanTree.code();
for (Map.Entry<Character, String> entry : huffmanTree.charmap.entrySet()) {
System.out.println(entry.getKey() + " : " + entry.getValue());
}
String encode = huffmanTree.encode("dffc");
System.out.println("encode: " + encode);
String decode = huffmanTree.decode(encode);
System.out.println("decode: " + decode);
}
}
堆樹
假設(shè)給你一個(gè)序列：8 4 20 7 3 1 25 14 17
利用堆樹進(jìn)行排序：
- 先按照序列順序存儲(chǔ)在完全二叉樹中：建堆
- 從最后一個(gè)非葉子節(jié)點(diǎn)堆化。為什么是最后一個(gè)非葉子節(jié)點(diǎn)而不是最后一個(gè)葉子節(jié)點(diǎn)呢？（最后葉子節(jié)點(diǎn)沒有左右節(jié)點(diǎn)無法比較）
堆的插入有兩種實(shí)現(xiàn)方式：
- 從下往上
- 從上往下
其插入過程就叫做堆化文章來源：http://www.zghlxwxcb.cn/news/detail-428949.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-428949.html
**
* 堆樹
*
* 建堆
* 排序
*
* 1. 優(yōu)先級(jí)隊(duì)列問題： 刪除最大的
* 2. top n 熱搜排行榜問題：1000萬的數(shù)字
* 3. 定時(shí)器 堆頂
* 4. 給你1億不重復(fù)的數(shù)字，求出top10，前10最大的數(shù)字，還可動(dòng)態(tài)添加
*/
public class HeapTree {
//建大頂堆
public static void maxHeap(int data[], int parent, int end) {
int leftSon = parent * 2 + 1; //下標(biāo)從0開始+1
while (leftSon < end) {
int temp = leftSon;
//temp表示的是 我們左右節(jié)點(diǎn)大的那一個(gè)
if (leftSon + 1 < end && data[leftSon] < data[leftSon + 1]) {
temp = leftSon + 1; //右節(jié)點(diǎn)比左節(jié)點(diǎn)大
}
//比較左右節(jié)點(diǎn)大的那一個(gè)temp和父節(jié)點(diǎn)比較大小
if (data[parent] > data[temp]) {
return; //不需要交換
} else {
int t = data[parent]; //交換
data[parent] = data[temp];
data[temp] = t;
parent = temp; //繼續(xù)堆化
leftSon = parent * 2 + 1;
}
}
}
public static void heapSort(int data[]) {
int len = data.length;
//從后向上建
//建堆從哪里開始 最后一個(gè)的父元素開始（len/2 - 1）（父元素中：最后一個(gè)父元素是第幾個(gè)，從0開始）
for (int parent = len/2 - 1; parent >= 0; parent--) { //nlog(n)
maxHeap(data, parent, len);
}
//從上向下建
//最后一個(gè)數(shù)和第一個(gè)數(shù)交換
int headHeap = 0;
for (int tailHeap = len - 1; tailHeap > 0; tailHeap--) { //nlog(n)
int temp = data[headHeap];
data[headHeap] = data[tailHeap];
data[tailHeap] = temp;
maxHeap(data, headHeap, tailHeap);
}
}
/**
* Arrays: [1, 3, 4, 7, 8, 14, 17, 20, 25]
*/
public static void main(String[] args) {
int data[] = {8, 4, 20, 7, 3, 1, 25, 14, 17};
heapSort(data);
System.out.printf("Arrays: " + Arrays.toString(data));
}
}
topK
class TopK {
private int k = 10;
private int data[] = new int[k];
public void topK() {
Random random = new Random();
long time = System.currentTimeMillis();
int size = 0;
boolean init = false;
for (int i = 0; i < 100000000; i++) {
int num = random.nextInt(100000000);
if (size < k) {
data[size] = num;
size++;
} else {
if (!init) {
for (int j = k/2 - 1; j >=0; j--) {
minHeap(data, 0, k);
}
init = true;
}
if (num > data[0]) {
data[0] = num;
minHeap(data, 0, k);
}
}
}
System.out.println("耗時(shí)：" + (System.currentTimeMillis() - time) + "ms \n");
for (int datum : data) {
System.out.print(datum+", ");
}
}
private void minHeap(int[] data, int start, int end) {
int parent = start;
int son = parent * 2 + 1;
while (son < end) {
int temp = son;
if (son + 1 < end && data[son] > data[son +1]) { //右節(jié)點(diǎn)比左節(jié)點(diǎn)大
temp = son + 1; //根號(hào)右節(jié)點(diǎn)和父節(jié)點(diǎn)
}
//temp表示我們左右節(jié)點(diǎn)小的那一個(gè)
if (data[parent] < data[temp]) {
return;
} else {
int t = data[parent];
data[temp] = t;
parent = temp;
son = parent * 2 + 1;
}
}
return;
}
public static void main(String[] args) {
TopK topK = new TopK();
topK.topK();
}
}
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法（三）：樹論（樹形結(jié)構(gòu)、二叉樹、二叉搜索樹、紅黑樹、Btree&B+Tree、赫夫曼樹、堆樹）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
