因为是复习，从基础开始一起复习。

如果冲着标题来的，可以直接跳到后半部分看B树的内容(～￣▽￣)～

支持云栖社区！同时俺也有自己的独立博客——

，因为在社区博客里只能发发技术文章之类的，但在自己博客我会写一些最近随笔和读书笔记等等哈哈，也希望大家能支持一下 ( •̀ ω •́ )y

这里是我独立博客里这篇文章的链接：

一、二叉树

二叉树的基本操作

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。所以在利用索引查询的时候，不能把整个索引全部加载到内存，只有逐一加载每一个磁盘页，这里磁盘页对应着索引树的节点，如图（图片源于程序员小灰）。

算法之树（一，B-树原理详解）(Java版)-持续更新补充一、二叉树二、二叉查找树三、平衡二叉树四、B-树、B+树

当数据比较大，无法全部存入内存时，需要将部分数据存在外存中，在需要的时候读入内存，修改之后又写回外存。由于外存的速度与内存有几个数量级的差别，所以节省在外存上花的时间，对搜索树的性能提高时最有效的。

最常见的外存就是磁盘。磁盘是块设备，也就是说磁盘的读写单位是以块为单位，一般地块大小从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-树原理详解）(Java版)-持续更新补充一、二叉树二、二叉查找树三、平衡二叉树四、B-树、B+树

一、二叉树

二叉树的基本操作

二、二叉查找树

二叉查找树的操作

三、平衡二叉树

四、B-树、B+树

B-树

为什么不用二叉查找树？

B树文件查找的具体过程

B树的特征

B树的应用场景

B树的代码实现

继续阅读

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

spark/scala关于【资源文件】加载方法概述外部文件加载方案测试资源文件打包入jar包中小结

NOSQL安全攻击

mybatis_入门程序Mybatis入门

mysql使用source命令导入.sql文件

AOP编程_Android优雅权限框架(1)概念基础，2021金三银四前言正文大纲正文

面试题解析：你接口测试是怎么做的？

登录plsql 报错 the account is locked --用户被锁

Effective Java 8:通用程序设计

SequoiaDB巨杉数据库C++驱动概述

OOM三种类型

工厂模式-三种类型

【递归】高效率求2的n次幂

win10本地scala和spark安装安装scala安装spark

scala (3) Function 和 Method

hdu7108哈希