算法之树（一，B-树原理详解）(Java版)-持续更新补充
因为是复习，从基础开始一起复习。
如果冲着标题来的，可以直接跳到后半部分看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)实现
