树结构是一类重要的非线性数据结构。直观来看，树是以分支关系定义的层次结构。树结构在客观世界广泛存在，如人类社会的族谱和各种社会组织机构都可用树来形象表示。
树在计算机领域中也得到广泛应用，尤以二叉树最为常用。如在操作系统中，用树来表示文件目录的组织结构。在编译系统中，用树来表示源程序的语法结构。在数据库系统中，树结构也是信息的重要组织形式之一。

1、树的定义

1.1、树的定义

树(Tree)是n(n>=0)个结点的有限集，它或为空树(n= 0);,或为非空树，对千非空树T:

• (1) 有且仅有一个称之为根的结点；
• (2) 除根结点以外的其余结点可分为 m(m>0）个互不相交的有限集 T1, T2 , …，Tn，其中每
  一个集合本身又是一棵树，并且称为根的子树(SubTree)。

图1：树的示例

1.2、树的相关术语

这里结合图1 （b）为例：

• 结点:树中的一个独立单元。包含一个数据元素及若于指向其子树的分支。如图 A 、 B 、 C 、 D 等。
• 结点的度：结点拥有的子树数称为结点的度。例如，A的度为 3, C的度为1, F的度为0。
• 树的度:树的度是树内各结点度的最大值。图 1 (b) 所示的树的度为3。
• 叶子/终端结点： 度为 0 的结点称为叶子或终端结点。结点 K 、 L 、 F 、 G 、 M 、 I 、 J都是树的叶子。
• 非终端结点：度不为 0 的结点称为非终端结点或分支结点。除根结点之外，非终端结点也称为内部结点。
• 双亲和孩子：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。例如，B的双亲为A, B的孩子有E和F。
• 兄弟:同一个双亲的孩子之间互称兄弟。例如，H 、 I 和J互为兄弟。
• 祖先:从根到该结点所经分支上的所有结点。例如， M 的祖先为 A 、 D 和 H。
• 子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。如 B 的子孙为 E 、 K 、 L和 F。
• 层次:结点的层次从根开始定义起，根为 第一层，根的孩子为第二层。树中任一结点的层次等千其双亲结点的层次加 1。
• 堂兄弟:双亲在同 一层的结点互为堂兄弟。 例如，结点 G 与E 、 F、 H 、 I 、 J互为堂兄弟。
• 树的深度:树中结点的最大层次称为树的深度或高度。图1 (b)所示的树的深度为4。
• 有序树和无序树:如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。
• 森林:是 m (m>0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。由此，也可以用森林和树相互递归的定义来描述树。

1.3、二叉树的定义

二叉树(Binary Tree)是n(n>=0)个结点所构成的集合，它或为空树(n =0); 或为非空树，对于非空树T:

• (1) 有且仅有一个称之为根的结点；
• (2) 除根结点以外的其余结点分为两个互不相交的子集T1和T2, 分别称为T的左子树和右子树，且T1和T2本身又都是二叉树。

二叉树与树一样具有递归性质，二叉树与树的区别主要有以下两点：

• (1) 二叉树每个结点至多只有两棵子树（即二叉树中不存在度大千2 的结点）；
• (2) 二叉树的子树有左右之分，其次序不能任意颠倒。

图2：二叉树的五种基本形态

1.4、二叉树的性质

二叉树具有下列重要特性：

• 性质1 二叉树第i(i≥1)层上的结点数最多为 2^i-1^。
• 性质2 高度为k的二叉树最多有 2^k^-1 个结点。
• 性质3 对任何二叉树T,设n~0~、n~1~、n~2~ 分别表示度数为 0、 1、 2 的结点个数， 则 n~0~=n~2~+1。

满二叉树和完全二叉树：

满二叉树和完全二叉树是二叉树的两种特殊情形。

一棵深度为 A 且有 2^k^ -1 个结点的二叉树称为满二叉树。

如图 3 所示是深度分别为 1、 2、 3 的满二叉树。 满二叉树的特点是每一层上的结点数都达到最大值， 即对给定的深度， 它是具有最多结点数的二叉树。 满二叉树不存在度数为 1 的结点， 每个分支结点均有两棵高度相同的子树， 且树叶都在最下一层上。

图3：三种不同深度的满二叉树

若一棵二叉树至多只有最下面的两层结点的度数可以小于 2, 并且最下一层上的结点都集中在该层最左边的若干位置上， 则此二叉树称为完全二叉树。如图4所示：

图4：完全二叉树

由定义及示例可以看出满二叉树是完全二叉树， 但完全二叉树不一定是满二叉树。

• 性质4 具有 个结点的完全二叉树(包括满二叉树）的高度为 [log~2~n]+1(或者[log~2~(n+1)])。
• 性质5 满二叉树原理非空满二叉树的叶结点数等于其分支结点数加1。
• 性质6 —棵非空二叉树空子树的数目等于其结点数目加 1。

2、二叉树实现

2.1、二叉树存储结构

• 顺序存储

和线性表类似，二叉树的存储结构也可采用顺序存储和链式存储两种方式。

顺序存储是将二叉树所有元素编号，存入到一维数组的对应位置。顺序存储比较适合完全二叉树，只要从根起按层序存储即可，依次自上而下、自左至右存储结点元素， 即将完全二叉树上编号为i 的结点元素存储在如 上定义的一维数组中下标为i-1的数组元素中。

对于非完全二叉树，存在空间的浪费。

图5：二叉树顺序存储示意图

• 链式存储

由于采用顺序存储结构存储一般二叉树造成大量存储空间的浪费， 因此， 一般二叉树的存储结构更多地采用链接的方式。

在链式存储结构里，我们需要对节点进行定义，每个节点包含数据、左孩子、右孩子。

图6：二叉树链式存储节点示意图

左孩子指向节点的左孩子，右节点指向节点的右孩子。

图7：二叉树的二叉链表表示

下面来看一看链式存储结构的具体实现。

2.2、二叉树链式存储及常见操作实现

2.2.1、节点类

这里添加了一个父节点的属性，方便后面的一些操作

/**
 * @Author 三分恶
 * @Date 2020/10/8
 * @Description 二叉树节点
 */
public class BinaryTreeNode {
    private Object data;  //数据
    private BinaryTreeNode leftChild;  //左孩子
    private BinaryTreeNode rightChild; //右孩子
    private BinaryTreeNode parent;     //父节点
    //省略getter、setter
    
    /**
     * 重写equals方法，这里设置为数据相等即认为是同一节点（这个规则不合理，待改进）
     * @param obj
     * @return
     */
    @Override
    public boolean equals(Object obj) {
        //比较对象为BinaryTreeNode类实例
        if (obj instanceof BinaryTreeNode){
            BinaryTreeNode compareNode= (BinaryTreeNode) obj;
            //设置为数据相同即相同
            if (compareNode.getData().equals(this.getData())){
                return true;
            }
        }
        return false;
    }
}

2.2.2、创建

/**
 * @Author 三分恶
 * @Date 2020/10/8
 * @Description 二叉树-链式
 */
public class BinaryTree {
    private BinaryTreeNode root;     //根节点
    public BinaryTree() {
    }
    public BinaryTree(BinaryTreeNode root) {
        this.root = root;
    }
    public BinaryTreeNode getRoot() {
        return root;
    }
    public void setRoot(BinaryTreeNode root) {
        this.root = root;
    }
}

2.2.2、清空

    /**
     * 二叉树的清空
     * 递归清空某个节点的子树
     * @param node
     */
    public void clear(BinaryTreeNode node){
        if (node!=null){
            //递归清空左子树
            clear(node.getLeftChild());
            //递归清空右子树
            clear(node.getRightChild());
            //将该节点置为null
            node=null;
        }
    }
    /**
     * 清空二叉树
     */
    public void clear(){
        clear(root);
    }

2.2.3、判空

判断根节点是否存在。

    /**
     * 判断二叉树是否为空
     * @return
     */
    public boolean isEmpty(){
        return root==null;
    }

2.2.4、获取二叉树的高度

首先需要一种获取以某个节点为子树的高度方法，使用递归实现。如果一个节点为空，那么这个节点肯定是一颗空树，高度为0；如果不为空，则遍历地比较它的左右子树高度，高的一个为这颗子树的最大高度，然后加上自身的高度即可。

    /**
     * 获取指定节点的子树的高度
     * @param node
     * @return
     */
    public int height(BinaryTreeNode node){
        if (node==null){
            return 0;
        }
        //递归获取左子树高度
        int l=height(node.getLeftChild());
        //递归获取右子树高度
        int r=height(node.getRightChild());
        //子树高度+1，因为还有节点这一层
        return l>=r? (l=1):(r=1);
    }
    /**
     * 获取二叉树的高度
     * @return
     */
    public int height(){
        return height(root);
    }

2.2.5、获取节点个数

获取二叉树节点数，需要获取以某个节点为根的子树的节点数实现。

如果节点为空，则个数肯定为0；如果不为空，则算上这个节点之后，继续递归计算所有子树的节点数，全部相加即可

    /**
     * 获取某个节点及子树的节点个数
     * @param node
     * @return
     */
    public int size(BinaryTreeNode node){
       if (node==null){
           return 0;
       }
       //递归获取左子树节点数
       int l=size(node.getLeftChild());
       //递归获取右子树节点数
       int r=size(node.getRightChild());
       return l+r+1;
    }
    /**
     * 获取二叉树节点个数
     * @return
     */
    public int size(){
        return size(root);
    }

2.2.6、获取末端叶子节点

通过递归左右子树，获得左右子树末端的叶子节点。

    /**
     * 获取节点左子树的末端节叶子点
     * @param node
     * @return
     */
    public BinaryTreeNode getLeftLeaf(BinaryTreeNode node){
        if (node==null){
           return null;
        }
        if (node.getLeftChild()==null){
            return node;
        }else{
           node=getLeftLeaf(node.getLeftChild());
        }
        return node;
    }
    /**
     * 获取整个二叉树左子树最末端的叶子节点
     * @return
     */
    public BinaryTreeNode getLeftLeaf(){
        return getLeftLeaf(root);
    }
    /**
     * 获取某个节点右子树最末端的叶子节点
     * @param node
     * @return
     */
    public BinaryTreeNode getRightLeaf(BinaryTreeNode node){
        if (node==null){
            return null;
        }
        if (node.getRightChild()==null){
            return node;
        }else{
            node=getRightLeaf(node.getRightChild());
        }
        return node;
    }
    /**
     * 获取整个二叉树右子树最末端叶子节点
     * @return
     */
    public BinaryTreeNode getRightLeaf(){
        return getRightLeaf(root);
    }

2.2.7、插入

这里只是实现了给节点插入左孩子、右孩子,只考虑了插入的节点的左右孩子不存在的情况。

    /**
     *  给某个节点插入左孩子
     * @param parent
     * @param newNode
     */
    public void insertLeft(BinaryTreeNode parent,BinaryTreeNode newNode){
        parent.setLeftChild(newNode);
        newNode.setParent(parent);
    }
    /**
     * 给某个节点插入右孩子
     * @param parent
     * @param newNode
     */
    public void insertRitht(BinaryTreeNode parent,BinaryTreeNode newNode){
        parent.setRightChild(newNode);
        newNode.setParent(parent);
    }

2.2.8、删除

从二叉树中删除节点，稍微复杂一些，需要考虑三种情形。

• 被删除的节点左右子树均为空

这是最简单的一种情形，只需要把被被删除节点的父亲节点的孩子节点指向null即可。

图8：二叉树节点删除——左右子树均为空

• 被删除的节点左右子树有一个为空
  这种情形，只需要将被删除元素的左子树的父节点移动到被删除元素的父节点，然后将被删除元素移除即可。

图9：二叉树节点删除——右子树为空

图9：二叉树节点删除——左子树为空

• 被删除的节点左右子树均不为空
  这是最复杂的一种情形。这里博主偷了一个懒，选择了填坑的方式，将需要删除的节点删除，挖了一个坑，找到二叉树左子树叶子节点，把这个节点给填进去。

具体代码实现：

    /**
     * 删除节点
     * @param subNode 遍历的节点
     * @param node 待删除节点
     * @return
     */
    public BinaryTreeNode deleteNode(BinaryTreeNode subNode,BinaryTreeNode node){
       if (subNode==null){
           return null;
       }
       //父节点
       BinaryTreeNode parent=null;
       if (subNode.equals(node)){
           parent=node.getParent();
           //情形1、当前节点没有孩子节点
           if (subNode.getLeftChild()==null&&subNode.getRightChild()==null){
               //删除父节点和当前节点的关联
               this.changeChild(parent,subNode,null);
               //情形2、当前节点只有左节点或右节点
           } else if (subNode.getLeftChild()==null){   //情形2.1只有右孩子节点
               //将父节点孩子节点设置为当前节点的右孩子
               this.changeChild(parent,subNode,subNode.getRightChild());
           }else if (subNode.getRightChild()==null){  //情形2，2只有左孩子节点
               //将父节点孩子节点设置为当前节点的左孩子
               this.changeChild(parent,subNode,subNode.getLeftChild());
           }else{                             //情形3、左右孩子节点都有
               //左子树末端叶子节点
               BinaryTreeNode leftLeaf=getLeftLeaf(subNode);
               //将父节点孩子节点设置为末端叶子节点
               this.changeChild(parent,subNode,leftLeaf);
               //将叶子节点父节点子节点置为null
               this.changeChild(leftLeaf.getParent(),leftLeaf,null);
               //叶子节点父节点
               leftLeaf.setParent(parent);
              //被删除的节点置为null，帮助gc
               subNode=null;
           }
       }
       //递归左子树
       if (deleteNode(subNode.getLeftChild(),node)!=null){
           deleteNode(subNode.getLeftChild(),node);
       }else {
           //递归右子树
           deleteNode(subNode.getRightChild(),node);
       }
       return subNode;
    }
    /**
     *  替换父亲节点的孩子节点
     * @param parent 父亲节点
     * @param replacedNode 被替换的节点
     * @param aimNode 替换的节点
     */
    void changeChild(BinaryTreeNode parent,BinaryTreeNode replacedNode,BinaryTreeNode aimNode){
        //被替换节点是左孩子
        if (replacedNode==parent.getLeftChild()){
            parent.setLeftChild(aimNode);
        }else{
            //被替换节点是右孩子
            parent.setRightChild(aimNode);
        }
    }

2.3、遍历二叉树

常见的二叉树遍历方法有前序、中序、后序、层次等。

2.3.1、前序遍历

前序遍历(Preorder Traversal)是先遍历根结点， 再遍历左子树， 最后才遍历右子树。 及时二叉树非空， 则依次进行如下操作：

• 访问根节点
• 前序遍历左子树
• 前序遍历右子树

图8：前序遍历二叉树示意图

    /**
     * 从某个节点开始先序遍历子树
     * @param node
     */
    public void preOrder(BinaryTreeNode node){
        if (node!=null){
            //遍历根节点
            System.out.println(node.getData());
            //遍历左子树
            preOrder(node.getLeftChild());
            //遍历右子树
            preOrder(node.getRightChild());
        }
    }
    /**
     * 先序遍历整个二叉树
     */
    public void  preOrder(){
        preOrder(root);
    }

2.3.2、中序遍历

中序遍历(Inorder Traversal)是先遍历左子树， 再遍历根结点， 最后才遍历右子树。 即若二叉树非空， 则依次进行如下操作：

• 中序遍历左子树；
• 访问根结点；
• 中序遍历右子树。

图9：中序遍历二叉树示意图

    /**
     * 从某个节点开始中序遍历子树
     * @param node
     */
    public void inOrder(BinaryTreeNode node){
        if (node!=null){
            //中序遍历左子树
            inOrder(node.getLeftChild());
            //访问根节点
            System.out.println(node.getData());
            //中序遍历右子树
            inOrder(node.getRightChild());
        }
    }
    /**
     * 中序遍历整个二叉树
     */
    public void inOrder(){
        inOrder(root);
    }

2.3.3、后序遍历

后序遍历(Postorder Traversal)是先遍历左子树， 再遍历右子树， 最后才遍历根结点。即若二叉树非空， 则依次进行如下操作：

• 后序遍历左子树；
• 后序遍历右子树；
• 访问根结点。

图10：后序遍历二叉树示意图

    /**
     * 从某个节点开始后序遍历子树
     * @param node
     */
    public void postOrder(BinaryTreeNode node){
        if (node!=null){
            //后序遍历左子树
            preOrder(node.getLeftChild());
            //后序遍历右子树
            preOrder(node.getRightChild());
            //访问根节点
            System.out.println(node.getData());
        }
    }
    /**
     * 后序遍历整个二叉树
     */
    public void postOrder(){
        preOrder(root);
    }

由二叉树的先序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树。

2.3.4、层次遍历

层次遍历是指从二叉树的第一层(根结点)开始， 从上至下逐层遍历， 在同一层中， 则按从左到右的顺序对结点逐个访问。

图11：层次遍历二叉树示意图

由层次遍历的操作可以推知， 在进行层次遍历时， 对一层结点访问完后， 再按照它们的访问次序对各个结点的左孩子和右孩子顺序访问， 就完成了对下一层从左到右的访问。

因此， 在进行层次遍历时， 需设置一个队列结构， 遍历从二叉树的根结点开始， 首先将根结点指针入队， 然后从队头取出一个元素， 每取出一个元素， 执行两个操作： 访问该元素所指结点； 若该元素所指结点的左、 右孩子结点非空， 则将该元素所指结点的左孩子指针和右孩子指针顺序入队。此过程循环进行， 直至队列为空， 表示二叉树的层次遍历结束。

所以， 对一棵非空的二叉树进行层次遍历可按照如下步骤进行:

• (1) 初始化一个队列；
• (2) 二叉树的根结点放入队列；
• (3) 重复步骤(4)~(7)直至队列为空；
• (4) 从队列中取出一个结点 x;
• (5) 访问结点x;
• (6) 如果 x 存在左子结点， 将左子结点放入队列；
• (7) 如果 x 存在右子结点， 将右子结点放入队列。

3、线索二叉树

在上面我们了解了二叉树的常见遍历方法，接下来看一看二叉树的线索化。

3.1、二叉树的线索化

在线性结构中， 各结点的逻辑关系是顺序的， 寻找某一结点的前趋结点和后继结点很方便。 对于二叉树， 由于它是非线性结构， 所以树中的结点不存在前趋和后继的概念， 但当我们对二叉树以某种方式遍历后， 就可以得到二叉树中所有结点的一个线性序列， 在这种意义下， 二叉树中的结点就有了前趋结点和后继结点。

二叉树通常采用二叉链表作为存储结构， 在这种存储结构下， 由于每个结点有两个分别指向其左儿子和右儿子的指针， 所以寻找其左、 右儿子结点很方便， 但要找该结点的前趋结点和后继结点则比较困难。

图12：二叉链表示意图

为方便寻找二叉树中结点的前趋结点或后继结点， 可以通过一次遍历记下各结点在遍历所得的线性序列中的相对位置。 保存这种信息的一种简单的方法是在每个结点增加两个指针域， 使它们分别指向依某种次序遍历时所得到的该结点的前趋结点和后继结点， 显然这样做要浪费相当数量的存储单元。

如果仔细分析一棵具有 n 个结点的二叉树， 就会发现,当它采用二叉链表作存储结构时， 二叉树中的所有结点共有n+1 个空指针域。 因此， 可以设法利用这些空指针碎来存放结点的前趋结点和后继结点的指针信息， 这种附加的指针称为“ 线索” 。 我们可以作这样的规定， 当某结点的左指针域为空时， 令其指向依某种方式遍历时所得到的该结点的前趋结点， 否则指向它的左儿子； 当某结点的右指针域为空时，令其指向依某种方式遍历时所得到的该结点的后继结点， 否则指向它的右儿子。

图13：增加线索的中序遍历二叉树

增加了线索的二叉链表称为线索链表， 相应的二叉树称为线索二叉树(Threaded Binary Tree)。

为了区分一个结点的指针是指向其儿子的指针还是指向其前趋或者后继的线索， 可以在每个结点上增加两个线索标志域 leftType 和 rightType， 这样线索链表的结点结构为：

图14：线索二叉树节点

一棵二叉树以某种方式遍历并使其变成线索二叉树的过程称为二叉树的线索化。对同一棵二叉树遍历的方式不同， 所得到的线索树也不同， 二叉树主要有前序、 中序和后序 3 种遍历方式， 所以线索树也有前序线索二叉树、 中序线索二叉树和后序线索二叉树3种。

图15：线索二叉树示意图

3.2、中序线索二叉树的实现

这一节来实现中序遍历线索二叉树。

3.1.1、线索二叉树节点

/**
 * @Author 三分恶
 * @Date 2020/10/11
 * @Description 线索二叉树节点
 */
public class ClueBinaryTreeNode {
    //节点数据
    int data;
    //左儿子
    ClueBinaryTreeNode leftNode;
    //右儿子
    ClueBinaryTreeNode rightNode;
    //标识指针类型,其中0,1分别表示有无线索化，默认为0
    int leftType;
    int rightType;
}    

3.1.2、创建中序线索二叉树

建立线索二叉树， 或者说， 对二叉树线索化， 实质上就是遍历一棵二叉树， 在遍历的过程中， 检査当前结点的左、 右指针域是否为空， 如果为空， 将它们改为指向前趋结点或后继结点的线索。

以图12的二叉树为例：

图16：中序线索二叉树

• 定义一个节点pre用来存储当前节点，类似指针。

• 从根节点1开始递归，如果当前节点为空，返回；遍历到4，此时4的前驱结点为null,结点5的前驱结点为2

• 遍历到5的时候指向前驱结点2，前驱结点2为上一层递归的指针，因此指向它的前驱结点就行，再把左指针类型置为1

• 如果当前节点的前驱结点pre的右指针为null,则将它设置为当前节点，此时即4的后继结点为2，并将右指针类型置为1

• 每处理一个节点，当前节点是下一个节点的前驱节点

来看一下具体实现：

/**
 * @Author 三分恶
 * @Date 2020/10/11
 * @Description 中序线索二叉树
 */
public class ClueBinaryTree {
    private ClueBinaryTreeNode root;   //根节点
    private ClueBinaryTreeNode pre;   //每个节点的前趋节点
    public ClueBinaryTreeNode getRoot() {
        return root;
    }
    public void setRoot(ClueBinaryTreeNode root) {
        this.root = root;
    }
    /**
     * 构建中序线索二叉树
     */
    public void clueBinaryNodes() {
        clueBinaryNodes(root);
    }
    /**
     * 构建中序线索二叉树
     * @param node 起始节点
     */
    public void clueBinaryNodes(ClueBinaryTreeNode node) {
        //当前节点如果为null，直接返回
        if(node==null) {
            return;
        }
        //递归处理左子树
        clueBinaryNodes(node.leftNode);
        //处理前驱节点
        if(node.leftNode==null){
            //让当前节点的左指针指向前驱节点
            node.leftNode=pre;
            //改变当前节点左指针的类型
            node.leftType=1;
        }
        //处理前驱的右指针，如果前驱节点的右指针是null(没有指下右子树)
        if(pre!=null&&pre.rightNode==null) {
            //让前驱节点的右指针指向当前节点
            pre.rightNode=node;
            //改变前驱节点的右指针类型
            pre.rightType=1;
        }
        //每处理一个节点，当前节点是下一个节点的前驱节点
        pre=node;
        //处理右子树
        clueBinaryNodes(node.rightNode);
    }
}

4、二叉查找树

二叉树的一个重要作用是用作查找。

4.1、二叉查找树的概念和操作

二叉查找树定义：

又称为是二叉排序树（Binary Sort Tree）或二叉搜索树。二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

• 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
• 左、右子树也分别为二叉排序树；
• 没有键值相等的节点。

图17：二叉查找树的示意图

二叉查找树的高度决定了二叉查找树的查找效率。

和普通的二叉树相比，二叉查找树的节点是有序的。

　　二叉查找树的插入过程如下：

• 若当前的二叉查找树为空，则插入的元素为根节点;

• 若插入的元素值小于根节点值，则将元素插入到左子树中;

• 若插入的元素值不小于根节点值，则将元素插入到右子树中。

4.1、二叉查找树的实现

• 节点类：因为要比较节点大小，所以继承Comparable类

    /**
     * 二叉查找树节点
     *
     * @param <T>
     */
    class BSTNode<T extends Comparable<T>> {
        T key;                // 关键字(键值)
        BSTNode<T> left;    // 左孩子
        BSTNode<T> right;    // 右孩子
        BSTNode<T> parent;    // 父结点
        //省略构造方法、getter、setter
     }    

• 插入：插入需要比较插入节点和当前节点的大小

   /**
     * 将结点插入到二叉树中
     *
     * @param bst 二叉树
     * @param z   插入的节点
     */
    private void insert(BSTree<T> bst, BSTNode<T> z) {
        int cmp;
        BSTNode<T> y = null;
        BSTNode<T> x = bst.mRoot;
        // 查找z的插入位置
        while (x != null) {
            y = x;
            //与当前节点比较
            cmp = z.key.compareTo(x.key);
            //比当前节点小，插入为左孩子
            if (cmp < 0) {
                x = x.left;
            } else {
                //比当前节点大，插入为右孩子
                x = x.right;
            }
        }
        z.parent = y;
        if (y == null)
            bst.mRoot = z;
        else {
            cmp = z.key.compareTo(y.key);
            if (cmp < 0) {
                y.left = z;
            } else {
                y.right = z;
            }
        }
    }
    /**
     * 新建结点(key)，并将其插入到二叉树中
     * @param key 插入结点的键值
     */
    public void insert(T key) {
        BSTNode<T> z = new BSTNode<T>(key, null, null, null);
        //插入新节点
        if (z != null) {
            insert(this, z);
        }
    }

• 查找:查找的节点比当前节点大就去查找右子树，比当前节点小就去查找左子树。

    /**
     *  (递归实现)查找"二叉树x"中键值为key的节点
     * @param x
     * @param key
     * @return
     */
    private BSTNode<T> search(BSTNode<T> x, T key) {
        if (x == null) {
            return x;
        }
        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            return search(x.left, key);
        } else if (cmp > 0) {
            return search(x.right, key);
        } else {
            return x;
        }
    }
    public BSTNode<T> search(T key) {
        return search(mRoot, key);
    }
    
    /**
     * (非递归实现)查找"二叉树x"中键值为key的节点
     * @param x
     * @param key
     * @return
     */
    private BSTNode<T> iterativeSearch(BSTNode<T> x, T key) {
        while (x != null) {
            int cmp = key.compareTo(x.key);
            if (cmp < 0) {
                x = x.left;
            } else if (cmp > 0) {
                x = x.right;
            } else {
                return x;
            }
        }
        return x;
    }
    public BSTNode<T> iterativeSearch(T key) {
        return iterativeSearch(mRoot, key);
    }

其余操作遍历，删除，清空等这里不再赘言。

5、平衡二叉树

二叉查找树查找算法的性能取决于二叉树的结构，而 二叉查找树的形状则取决于其数据集。

如果数据呈有序排列，则二叉排序树是线性的，查找的时间复杂度为O(n); 反之，如果二叉排序树的结构合理，则查找速度较快，查找的时间复杂度为 O(log~2~n)。

树的高度越小，查找速度越快——从树的形态来看，就是使树尽可能平衡。

有资料将平衡二叉树和AVL视作一体，本文采用了AVL树是平衡二叉树的一种的说法。

5.1、AVL树

AVL树是最先发明的自平衡二叉查找树。AVL树得名于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis，他们在 1962 年的论文 “An algorithm for the organization of information” 中发表了它。

AVL树是带平衡条件的二叉查找树：

• (1 ) 左子树和右子树的深度之差的绝对值不超过1;
• (2) 左子树和右子树也是平衡二叉树。

若将二叉树上结点的平衡因子(Balance Factor, BF)定义为该结点左子树和右子树的深度之
差，则平衡二叉树上所有结点的平衡因子只可能是 -1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1 , 则该二叉树就是不平衡的。

图18：平衡的二叉树

图19：不平衡的二叉树

在AVL中任何节点的两个儿子子树的高度最大差别为1，所以它也被称为高度平衡树，n个结点的AVL树最大深度约1.44log2n。得益于这个特征，它的深度和 log~2~n 是同数量级的（其中n为结点数）。 由此，其查找的时间复杂度是O(log~2~n)。

5.1.2、AVL树的平衡调整方法

插入结点时， 首先按照二叉排序树处理， 若插入结点后破坏了平衡二叉树的特性， 需对平衡二叉树进行调整。 调整方法是：找到离插入结点最近且平衡因子绝对值超过1的祖先结点， 以该结点为根的子树称为最小不平衡子树， 可将重新平衡的范围局限千这棵子树。

在平衡调整的过程中，有一个关键点是旋转。

这里有一个具体例子：

图20：平衡树的生成过程

• (1) 空树和1个结点⑬的树显然都是平衡的二叉树。在插入24之后仍是平衡的， 只是根结点的平衡因子BF由0变为-1, 如图18(a) -（c）所示。
• (2) 在继续插入37之后， 由千结点 ⑬ 的BF值由 -1 变成 -2, 由此出现了不平衡的现象。此时好比一根扁担出现一头重一头轻的现象， 若能将扁担的支撑点由 ⑬ 改至 ㉔ ， 扁担的两头就平衡了。此，可以对树做一个向左逆时针 ＂ 旋转 ＂ 的操作，令结点 ㉔为根，而结点 ⑬ 为它的左子树，此时，结点⑬ 和 ㉔ 的平衡因子都为0, 而且仍保持二叉排序树的特性，如图18(d)~ (e)所示。
• (3) 在继续插入90和53之后，结点 ㊲ 的BF值由-1变成-2, 排序树中出现了新的不平衡现象，需进行调整。但此时由于是结点邸插在结点 (90) 的左子树上，因此不能如上做简单调整。离插入结点最近的最小不平衡子树是以结点 ㊲为根的子树。这时，必须以 (53) 作为根结点，而使 ㊲ 成为它的左子树的根，(90) 成为它的右子树的根。这好比对树做了两次 “旋转” 操作，先向右顺时针旋转，后向左逆时针旋转（见图18 (f)~(h)), 使二叉排序树由不平衡转化为平衡。

一般情况下，假设最小不平衡子树的根结点为 A, 则失去平衡后进行调整的规律可归纳为下列4种情况。

• (1) LL 型：由于在 A 左子树根结点的左子树上插入结点，A 的平衡因子由 1 增至 2, 致使以A为根的子树失去平衡，则需进行一次向右的顺时针旋转操作，如图21所示。

图21：LL 型调整操作示意图

图22所示为两个LL型调整的实例。

图22：LL 型调整示例

• (2) RR 型：由千在 A 的右子树根结点的右子树上插入结点， A 的平衡因子由 -1 变为 -2,致使以 A 为根结点的子树失去平衡，则需进行一次向左的逆时针旋转操作，如图23所示。

图23：RR 型调整操作示意图

图24所示为两个RR型调整的实例。

图24：RR型调整示例

• (3) LR型：由千在A的左子树根结点的右子树上插入结点， A的平衡因子由1增至2,致使以A为根结点的子树失去平衡， 则需进行两次旋转操作。 第一次对B及其右子树进行逆时针旋转， C转上去成为B的根， 这时变成了LL型， 所以第二次进行LL型的顺时针旋转即可恢复平衡。 如果C原来有左子树， 则洞整C的左子树为B的右子树， 如图25所示。

图25：LR型调整操作示意图

LR型旋转前后A、 B、C三个结点平衡因子的变化分为3种情况， 图 26 所示为3种 LR型调整的实例。

图26：LR型调整示例

• (4) RL 型：由千在 A 的右子树根结点的左子树上插入结点， A 的平衡因子由 -1 变为-2,致使以 A 为根结点的子树失去平衡， 则旋转方法和 LR 型相对称， 也需进行两次旋转， 先顺时针右旋， 再逆时针左旋， 如图 27 所示。

图27：RL型调整操作示意图

同 LR 型旋转类似， RL 型旋转前后 A 、 B 、 C 三个结点的平衡因子的变化也分为 3 种情况，图 28 所示为 3 种 RL 型调整的实例。

图28：RL型调整示例

上述 4 种情况中，(1) 和 (2) 对称，进行的是单旋转的操作；(3) 和 (4) 对称，进行的是双旋转的操作。

旋转操作的正确性容易由 “保持二叉排序树的特性：中序遍历所得关键字序列自小至大有序” 证明之。 同时， 无论哪一种情况， 在经过平衡旋转处理之后，以 B 或 C 为根的新子树为平衡二叉树，而且它们的深度和插入之前以 A为根的子树相同。

因此， 当平衡的二叉排序树因插入结点而失去平衡时， 仅需对最小不平衡子树进行平衡旋转处理即可。 因为经过旋转处理之后的子树深度和插入之前相同，因而不影响插入路径上所有祖先结点的平衡度。

5.1.3、AVL树的插入

在平衡的二叉排序树BBST上插入一个新的数据元素e的递归算法可描述如下。

在上面我们看到插入节点，如果破坏了AVL树的平衡，则需要进行旋转，即上面的四种情况：

• LL
  执行一次右旋转

• RR
  执行一次左旋转

• LR
  先左旋，后右旋

• RL
  先右旋后左旋

5.1.3、AVL树删除

前面已经看过二叉树的删除操作，AVL树的删除操作同样分为三种情况：

• 删除节点为叶子节点
• 删除节点有左子树或右子树
• 删除节点有左子树和右子树

只不过 AVL 树在删除节点后需要重新检查平衡性并修正，同时，删除操作与插入操作后的平衡修正区别在于，插入操作后只需要对插入栈中的弹出的第一个非平衡节点进行修正，而删除操作需要修正栈中的所有非平衡节点。

具体代码实现：

public class AVLBinaryTree {
    public int size;
    //节点
    class Node{
        public int val;
        public Node left,right;
        public int height;
        public Node(int val){
            this.val=val;
            left=null;
            right=null;
            height=1;
        }
    }
    //添加一个节点
    public Node add(Node node,int val){
        if (node==null){
            size++;
            return new Node(val);
        }
        if (node.val<val) node.right=add(node.right,val);
        if (node.val>val) node.left=add(node.left,val);
        //更新高度
        node.height=Math.max(getHeight(node.left),getHeight(node.right))+1;
        //计算平衡因子
        int balanceFactor=getBlalanceFactor(node);
        //维护平衡
        //LL
        if (balanceFactor>1&&getBlalanceFactor(node.left)>=0){
            return rightRotate(node);
        }
        //RR
        if (balanceFactor<-1&&getBlalanceFactor(node.right)<=0){
            return leftRotate(node);
        }
        //LR
        if (balanceFactor>1&&getBlalanceFactor(node.left)<0){
            node.left=leftRotate(node.left);
            return rightRotate(node);
        }
        //RL
        if (balanceFactor<-1&&getBlalanceFactor(node.right)>0){
            node.right=rightRotate(node.right);
            return leftRotate(node);
        }
        return node;
    }
    /**
     * 对根节点x进行向左旋转操作，更新height后返回新的根节点y
     * @param x
     * @return
     */
    public Node leftRotate(Node x){
        Node y=x.right;
        Node T3=y.left;
        y.left=x;
        x.right=T3;
        //更新height
        x.height=Math.max(getHeight(x.left),getHeight(x.right))+1;
        y.height=Math.max(getHeight(y.left),getHeight(y.right))+1;
        return y;
    }
    /**
     * 对根节点进行右旋转操作，更新height后返回新的根节点y
     * @param x
     * @return
     */
    public Node rightRotate(Node x){
        Node y=x.left;
        Node T3=y.right;
        y.right=x;
        x.left=T3;
        //更新height
        x.height=Math.max(getHeight(x.left),getHeight(x.right))+1;
        y.height=Math.max(getHeight(y.left),getHeight(y.right))+1;
        return y;
    }
    //获得节点Node的高度
    public int getHeight(Node node){
        if (node==null){
            return 0;
        }
        return node.height;
    }
    //获取节点的平衡因子
    private int getBlalanceFactor(Node node){
        if (node==null){
            return 0;
        }
        return getHeight(node.left)-getHeight(node.right);
    }
    /**
     * 删除节点
     * @param node
     * @param val
     * @return
     */
    public Node remove(Node node,int val){
        if (node==null) return null;
        Node retNode;
        //递归查找要删除的节点
        if (node.val<val){
            node.left=remove(node.left,val);
            retNode=node;
        }else if(node.val>val){
            node.right=remove(node.right,val);
            retNode=node;
        }else{
            //找到了要删除的节点
            //情形1：被删除节点为叶子节点
            if (node.right==null){
                Node leftNode=node.left;
                node.left=null;
                size--;
                retNode=leftNode;
            }
            //情形2.1:被删除节点只有右孩子
            if (node.left==null){
                Node leftNode=node.left;
                node.left=null;
                size--;
                retNode=leftNode;
            }
            //情形2.2：被删除节点只有左孩子
            if (node.right==null){
                Node rightNode=node.right;
                node.right=null;
                size--;
                retNode=rightNode;
            }else{
                //情形3:被删除节点有左、右孩子
                Node minNode=minimum(node);
                minNode.right=remove(node.right,minNode.val);
                node.left=node.right=null;
                retNode=minNode;
            }
        }
        if (retNode==null) return retNode;
        
        //删除完成，开始进行二叉树的平衡
        //更新高度
        retNode.height= Math.max(getHeight(retNode.left),getHeight(retNode.right)+1);
        //计算平衡因子
        int balanceFactor=getBlalanceFactor(retNode);
        
        //维护平衡
        //维护平衡
        //LL
        if (balanceFactor>1&&getBlalanceFactor(retNode.left)>=0){
            return rightRotate(retNode);
        }
        //RR
        if (balanceFactor<-1&&getBlalanceFactor(retNode.right)<=0){
            return leftRotate(retNode);
        }
        //LR
        if (balanceFactor>1&&getBlalanceFactor(retNode.left)<0){
            retNode.left=leftRotate(retNode.left);
            return rightRotate(retNode);
        }
        //RL
        if (balanceFactor<-1&&getBlalanceFactor(retNode.right)>0){
            retNode.right=rightRotate(retNode.right);
            return leftRotate(retNode);
        }
        return retNode;
    }
    //获取该节点的整个子树的最小值
    public Node minimum(Node node){
        if (node.left==null){
            return node;
        }
        return minimum(node.left);
    }
}

5.2、红黑树

红黑树是一种常见的自平衡二叉查找树，常用于关联数组、字典，在各种语言的底层实现中被广泛应用，Java 的 TreeMap 和 TreeSet 就是基于红黑树实现的。

5.2.1、红黑树的定义和性质

红黑树::红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由鲁道夫·贝尔发明的，称之为”对称二叉B树”，它现在的名字来自Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中。

红黑树是具有如下性质的二叉查找树：

• （1）每个节点是黑色或者红色

• （2）根节点是黑色。

• （3）每个叶子节点是黑色。

• （4）从任意一个节点到叶子节点，所经过的黑色节点数目必须相等

• （5） 空节点被认为是黑色的

图29：红黑树示例图

5.2.2、红黑树的平衡调整方法

作为一种平衡二叉树，红黑树的自平衡调整方法和AVL类似。关键也是在旋转。旋转同样也是左旋和右旋。找到了两个左旋和右旋的动图。

和AVL树不同的是，红黑树还有颜色性质，所以还会进行变色来平衡红黑树。

5.2.2、红黑树的插入

红黑树的插入和AVL树类似，同样是插入节点后需要对二叉树的平衡性进行修复。

新插入的节点是红色的，插入修复操作如果遇到父节点的颜色为黑则修复操作结束。也就是说，只有在父节点为红色节点的时候是需要插入修复操作的。

插入修复操作分为以下的三种情况，而且新插入的节点的父节点都是红色的：

1. 叔叔节点也为红色。
2. 叔叔节点为空，且祖父节点、父节点和新节点处于一条斜线上。
3. 叔叔节点为空，且祖父节点、父节点和新节点不处于一条斜线上。

• 情形1
  情形1的操作是将父节点和叔叔节点与祖父节点的颜色互换，这样就符合了RBTRee的定义。即维持了高度的平衡，修复后颜色也符合RBTree定义的第三条和第四条。下图中，操作完成后A节点变成了新的节点。如果A节点的父节点不是黑色的话，则继续做修复操作。

图30：红黑树插入修复情形1

• 情形2
  情形2的操作是将B节点进行右旋操作，并且和父节点A互换颜色。通过该修复操作RBTRee的高度和颜色都符合红黑树的定义。如果B和C节点都是右节点的话，只要将操作变成左旋就可以了。

图31：红黑树插入修复情形2

• 情形3：
  情形3的操作是将C节点进行左旋，这样就从情形3转换成情形2了，然后针对情形2进行操作处理就行了。情形2操作做了一个右旋操作和颜色互换来达到目的。如果树的结构是下图的镜像结构，则只需要将对应的左旋变成右旋，右旋变成左旋即可。

图32：红黑树插入修复情形3

• 总结
  插入后的修复操作是一个向root节点回溯的操作，一旦牵涉的节点都符合了红黑树的定义，修复操作结束。之所以会向上回溯是由于情形操作会将父节点，叔叔节点和祖父节点进行换颜色，有可能会导致祖父节点不平衡(红黑树定义3)。这个时候需要对祖父节点为起点进行调节（向上回溯）。

  祖父节点调节后如果还是遇到它的祖父颜色问题，操作就会继续向上回溯，直到root节点为止，根据定义root节点永远是黑色的。在向上的追溯的过程中，针对插入的3中情况进行调节。直到符合红黑树的定义为止。直到牵涉的节点都符合了红黑树的定义，修复操作结束。

如果上面的3中情况如果对应的操作是在右子树上，做对应的镜像操作就是了。

5.2.3、红黑树的删除

红黑树的删除大体上和二叉查找树的删除类似，如果是叶子节点就直接删除，如果是非叶子节点，会用对应的中序遍历的后继节点来顶替要删除节点的位置。

但是，红黑树删除之后需要做修复的操作，使树符合红黑树的定义。

删除修复操作在遇到被删除的节点是红色节点或者到达root节点时，修复操作完毕。

删除修复操作是针对删除黑色节点才有的，当黑色节点被删除后会让整个树不符合RBTree的定义的第四条。需要做的处理是从兄弟节点上借调黑色的节点过来，如果兄弟节点没有黑节点可以借调的话，就只能往上追溯，将每一级的黑节点数减去一个，使得整棵树符合红黑树的定义。

删除操作的总体思想是从兄弟节点借调黑色节点使树保持局部的平衡，如果局部的平衡达到了，就看整体的树是否是平衡的，如果不平衡就接着向上追溯调整。

（删除黑色节点后）删除修复操作分四种情况：

• 情形1：待删除的节点的兄弟节点是红色的节点

  由于兄弟节点是红色节点的时候，无法借调黑节点，所以需要将兄弟节点提升到父节点，由于兄弟节点是红色的，根据红黑树的定义，兄弟节点的子节点是黑色的，就可以从它的子节点借调了。

  情形1这样转换之后就会变成后面的情形2，情形 3，或者情形 4进行处理了。上升操作需要对C做一个左旋操作，如果是镜像结构的树只需要做对应的右旋操作即可。

  之所以要做情形1操作是因为兄弟节点是红色的，无法借到一个黑节点来填补删除的黑节点。

图33：红黑树删除情形1

• 情形2：待删除的节点的兄弟节点是黑色的节点，且兄弟节点的子节点都是黑色的

  情形2的删除操作是由于兄弟节点可以消除一个黑色节点，因为兄弟节点和兄弟节点的子节点都是黑色的，所以可以将兄弟节点变红，这样就可以保证树的局部的颜色符合定义了。这个时候需要将父节点A变成新的节点，继续向上调整，直到整颗树的颜色符合红黑树的定义为止。

  情形2这种情况下之所以要将兄弟节点变红，是因为如果把兄弟节点借调过来，会导致兄弟的结构不符合红黑树的定义，这样的情况下只能是将兄弟节点也变成红色来达到颜色的平衡。当将兄弟节点也变红之后，达到了局部的平衡了，但是对于祖父节点来说是不符合定义4的。这样就需要回溯到父节点，接着进行修复操作。

图34：红黑树删除情形2

• 情形3：待调整的节点的兄弟节点是黑色的节点，且兄弟节点的左子节点是红色的，右节点是黑色的(兄弟节点在右边)，如果兄弟节点在左边的话，就是兄弟节点的右子节点是红色的，左节点是黑色的

  情形3的删除操作是一个中间步骤，它的目的是将左边的红色节点借调过来，这样就可以转换成情形4状态了，在情形4状态下可以将D，E节点都阶段过来，通过将两个节点变成黑色来保证红黑树的整体平衡。

  之所以说情形3是一个中间状态，是因为根据红黑树的定义来说，下图并不是平衡的，他是通过case 2操作完后向上回溯出现的状态。之所以会出现情形3和后面的情形4的情况，是因为可以通过借用侄子节点的红色，变成黑色来符合红黑树定义4.

图35：红黑树删除情形3

• 情形4：待调整的节点的兄弟节点是黑色的节点，且右子节点是是红色的(兄弟节点在右边)，如果兄弟节点在左边，则就是对应的就是左节点是红色的

  情形4的操作是真正的节点借调操作，通过将兄弟节点以及兄弟节点的右节点借调过来，并将兄弟节点的右子节点变成红色来达到借调两个黑节点的目的，这样的话，整棵树还是符合红黑树的定义的。

  情形这种情况的发生只有在待删除的节点的兄弟节点为黑，且子节点不全部为黑，才有可能借调到两个节点来做黑节点使用，从而保持整棵树都符合红黑树的定义。

  图36：红黑树删除情形4
  
  

代码实现：

• 节点类

public class RBTreeNode<T extends Comparable<T>> {
    private T value;//node value
    private RBTreeNode<T> left;//left child pointer
    private RBTreeNode<T> right;//right child pointer
    private RBTreeNode<T> parent;//parent pointer
    private boolean red;//color is red or not red
    //省略getter、setter，构造方法
}    

• 红黑树

public class RBTree<T extends Comparable<T>> {
    private final RBTreeNode<T> root;
    //node number
    private java.util.concurrent.atomic.AtomicLong size =
            new java.util.concurrent.atomic.AtomicLong(0);
    //in overwrite mode,all node's value can not  has same	value
    //in non-overwrite mode,node can have same value, suggest don't use non-overwrite mode.
    private volatile boolean overrideMode=true;
    public RBTree(){
        this.root = new RBTreeNode<T>();
    }
    public RBTree(boolean overrideMode){
        this();
        this.overrideMode=overrideMode;
    }
    public boolean isOverrideMode() {
        return overrideMode;
    }
    public void setOverrideMode(boolean overrideMode) {
        this.overrideMode = overrideMode;
    }
    /**
     * number of tree number
     * @return
     */
    public long getSize() {
        return size.get();
    }
    /**
     * get the root node
     * @return
     */
    private RBTreeNode<T> getRoot(){
        return root.getLeft();
    }
    /**
     * add value to a new node,if this value exist in this tree,
     * if value exist,it will return the exist value.otherwise return null
     * if override mode is true,if value exist in the tree,
     * it will override the old value in the tree
     *
     * @param value
     * @return
     */
    public T addNode(T value){
        RBTreeNode<T> t = new RBTreeNode<T>(value);
        return addNode(t);
    }
    /**
     * find the value by give value(include key,key used for search,
     * other field is not used,@see compare method).if this value not exist return null
     * @param value
     * @return
     */
    public T find(T value){
        RBTreeNode<T> dataRoot = getRoot();
        while(dataRoot!=null){
            int cmp = dataRoot.getValue().compareTo(value);
            if(cmp<0){
                dataRoot = dataRoot.getRight();
            }else if(cmp>0){
                dataRoot = dataRoot.getLeft();
            }else{
                return dataRoot.getValue();
            }
        }
        return null;
    }
    /**
     * remove the node by give value,if this value not exists in tree return null
     * @param value include search key
     * @return the value contain in the removed node
     */
    public T remove(T value){
        RBTreeNode<T> dataRoot = getRoot();
        RBTreeNode<T> parent = root;
        while(dataRoot!=null){
            int cmp = dataRoot.getValue().compareTo(value);
            if(cmp<0){
                parent = dataRoot;
                dataRoot = dataRoot.getRight();
            }else if(cmp>0){
                parent = dataRoot;
                dataRoot = dataRoot.getLeft();
            }else{
                if(dataRoot.getRight()!=null){
                    RBTreeNode<T> min = removeMin(dataRoot.getRight());
                    //x used for fix color balance
                    RBTreeNode<T> x = min.getRight()==null ? min.getParent() : min.getRight();
                    boolean isParent = min.getRight()==null;
                    min.setLeft(dataRoot.getLeft());
                    setParent(dataRoot.getLeft(),min);
                    if(parent.getLeft()==dataRoot){
                        parent.setLeft(min);
                    }else{
                        parent.setRight(min);
                    }
                    setParent(min,parent);
                    boolean curMinIsBlack = min.isBlack();
                    //inherit dataRoot's color
                    min.setRed(dataRoot.isRed());
                    if(min!=dataRoot.getRight()){
                        min.setRight(dataRoot.getRight());
                        setParent(dataRoot.getRight(),min);
                    }
                    //remove a black node,need fix color
                    if(curMinIsBlack){
                        if(min!=dataRoot.getRight()){
                            fixRemove(x,isParent);
                        }else if(min.getRight()!=null){
                            fixRemove(min.getRight(),false);
                        }else{
                            fixRemove(min,true);
                        }
                    }
                }else{
                    setParent(dataRoot.getLeft(),parent);
                    if(parent.getLeft()==dataRoot){
                        parent.setLeft(dataRoot.getLeft());
                    }else{
                        parent.setRight(dataRoot.getLeft());
                    }
                    //current node is black and tree is not empty
                    if(dataRoot.isBlack() && !(root.getLeft()==null)){
                        RBTreeNode<T> x = dataRoot.getLeft()==null
                                ? parent :dataRoot.getLeft();
                        boolean isParent = dataRoot.getLeft()==null;
                        fixRemove(x,isParent);
                    }
                }
                setParent(dataRoot,null);
                dataRoot.setLeft(null);
                dataRoot.setRight(null);
                if(getRoot()!=null){
                    getRoot().setRed(false);
                    getRoot().setParent(null);
                }
                size.decrementAndGet();
                return dataRoot.getValue();
            }
        }
        return null;
    }
    /**
     * fix remove action
     * @param node
     * @param isParent
     */
    private void fixRemove(RBTreeNode<T> node,boolean isParent){
        RBTreeNode<T> cur = isParent ? null : node;
        boolean isRed = isParent ? false : node.isRed();
        RBTreeNode<T> parent = isParent ? node : node.getParent();
        while(!isRed && !isRoot(cur)){
            RBTreeNode<T> sibling = getSibling(cur,parent);
            //sibling is not null,due to before remove tree color is balance
            //if cur is a left node
            boolean isLeft = parent.getRight()==sibling;
            if(sibling.isRed() && !isLeft){//case 1
                //cur in right
                parent.makeRed();
                sibling.makeBlack();
                rotateRight(parent);
            }else if(sibling.isRed() && isLeft){
                //cur in left
                parent.makeRed();
                sibling.makeBlack();
                rotateLeft(parent);
            }else if(isBlack(sibling.getLeft()) && isBlack(sibling.getRight())){//case 2
                sibling.makeRed();
                cur = parent;
                isRed = cur.isRed();
                parent=parent.getParent();
            }else if(isLeft && !isBlack(sibling.getLeft())
                    && isBlack(sibling.getRight())){//case 3
                sibling.makeRed();
                sibling.getLeft().makeBlack();
                rotateRight(sibling);
            }else if(!isLeft && !isBlack(sibling.getRight())
                    && isBlack(sibling.getLeft()) ){
                sibling.makeRed();
                sibling.getRight().makeBlack();
                rotateLeft(sibling);
            }else if(isLeft && !isBlack(sibling.getRight())){//case 4
                sibling.setRed(parent.isRed());
                parent.makeBlack();
                sibling.getRight().makeBlack();
                rotateLeft(parent);
                cur=getRoot();
            }else if(!isLeft && !isBlack(sibling.getLeft())){
                sibling.setRed(parent.isRed());
                parent.makeBlack();
                sibling.getLeft().makeBlack();
                rotateRight(parent);
                cur=getRoot();
            }
        }
        if(isRed){
            cur.makeBlack();
        }
        if(getRoot()!=null){
            getRoot().setRed(false);
            getRoot().setParent(null);
        }
    }
    //get sibling node
    private RBTreeNode<T> getSibling(RBTreeNode<T> node,RBTreeNode<T> parent){
        parent = node==null ? parent : node.getParent();
        if(node==null){
            return parent.getLeft()==null ? parent.getRight() : parent.getLeft();
        }
        if(node==parent.getLeft()){
            return parent.getRight();
        }else{
            return parent.getLeft();
        }
    }
    private boolean isBlack(RBTreeNode<T> node){
        return node==null || node.isBlack();
    }
    private boolean isRoot(RBTreeNode<T> node){
        return root.getLeft() == node && node.getParent()==null;
    }
    /**
     * find the successor node
     * @param node current node's right node
     * @return
     */
    private RBTreeNode<T> removeMin(RBTreeNode<T> node){
        //find the min node
        RBTreeNode<T> parent = node;
        while(node!=null && node.getLeft()!=null){
            parent = node;
            node = node.getLeft();
        }
        //remove min node
        if(parent==node){
            return node;
        }
        parent.setLeft(node.getRight());
        setParent(node.getRight(),parent);
        //don't remove right pointer,it is used for fixed color balance
        //node.setRight(null);
        return node;
    }
    private T addNode(RBTreeNode<T> node){
        node.setLeft(null);
        node.setRight(null);
        node.setRed(true);
        setParent(node,null);
        if(root.getLeft()==null){
            root.setLeft(node);
            //root node is black
            node.setRed(false);
            size.incrementAndGet();
        }else{
            RBTreeNode<T> x = findParentNode(node);
            int cmp = x.getValue().compareTo(node.getValue());
            if(this.overrideMode && cmp==0){
                T v = x.getValue();
                x.setValue(node.getValue());
                return v;
            }else if(cmp==0){
                //value exists,ignore this node
                return x.getValue();
            }
            setParent(node,x);
            if(cmp>0){
                x.setLeft(node);
            }else{
                x.setRight(node);
            }
            fixInsert(node);
            size.incrementAndGet();
        }
        return null;
    }
    /**
     * find the parent node to hold node x,if parent value equals x.value return parent.
     * @param x
     * @return
     */
    private RBTreeNode<T> findParentNode(RBTreeNode<T> x){
        RBTreeNode<T> dataRoot = getRoot();
        RBTreeNode<T> child = dataRoot;
        while(child!=null){
            int cmp = child.getValue().compareTo(x.getValue());
            if(cmp==0){
                return child;
            }
            if(cmp>0){
                dataRoot = child;
                child = child.getLeft();
            }else if(cmp<0){
                dataRoot = child;
                child = child.getRight();
            }
        }
        return dataRoot;
    }
    /**
     * red black tree insert fix.
     * @param x
     */
    private void fixInsert(RBTreeNode<T> x){
        RBTreeNode<T> parent = x.getParent();
        while(parent!=null && parent.isRed()){
            RBTreeNode<T> uncle = getUncle(x);
            if(uncle==null){//need to rotate
                RBTreeNode<T> ancestor = parent.getParent();
                //ancestor is not null due to before before add,tree color is balance
                if(parent == ancestor.getLeft()){
                    boolean isRight = x == parent.getRight();
                    if(isRight){
                        rotateLeft(parent);
                    }
                    rotateRight(ancestor);
                    if(isRight){
                        x.setRed(false);
                        parent=null;//end loop
                    }else{
                        parent.setRed(false);
                    }
                    ancestor.setRed(true);
                }else{
                    boolean isLeft = x == parent.getLeft();
                    if(isLeft){
                        rotateRight(parent);
                    }
                    rotateLeft(ancestor);
                    if(isLeft){
                        x.setRed(false);
                        parent=null;//end loop
                    }else{
                        parent.setRed(false);
                    }
                    ancestor.setRed(true);
                }
            }else{//uncle is red
                parent.setRed(false);
                uncle.setRed(false);
                parent.getParent().setRed(true);
                x=parent.getParent();
                parent = x.getParent();
            }
        }
        getRoot().makeBlack();
        getRoot().setParent(null);
    }
    /**
     * get uncle node
     * @param node
     * @return
     */
    private RBTreeNode<T> getUncle(RBTreeNode<T> node){
        RBTreeNode<T> parent = node.getParent();
        RBTreeNode<T> ancestor = parent.getParent();
        if(ancestor==null){
            return null;
        }
        if(parent == ancestor.getLeft()){
            return ancestor.getRight();
        }else{
            return ancestor.getLeft();
        }
    }
    private void rotateLeft(RBTreeNode<T> node){
        RBTreeNode<T> right = node.getRight();
        if(right==null){
            throw new java.lang.IllegalStateException("right node is null");
        }
        RBTreeNode<T> parent = node.getParent();
        node.setRight(right.getLeft());
        setParent(right.getLeft(),node);
        right.setLeft(node);
        setParent(node,right);
        if(parent==null){//node pointer to root
            //right  raise to root node
            root.setLeft(right);
            setParent(right,null);
        }else{
            if(parent.getLeft()==node){
                parent.setLeft(right);
            }else{
                parent.setRight(right);
            }
            //right.setParent(parent);
            setParent(right,parent);
        }
    }
    private void rotateRight(RBTreeNode<T> node){
        RBTreeNode<T> left = node.getLeft();
        if(left==null){
            throw new java.lang.IllegalStateException("left node is null");
        }
        RBTreeNode<T> parent = node.getParent();
        node.setLeft(left.getRight());
        setParent(left.getRight(),node);
        left.setRight(node);
        setParent(node,left);
        if(parent==null){
            root.setLeft(left);
            setParent(left,null);
        }else{
            if(parent.getLeft()==node){
                parent.setLeft(left);
            }else{
                parent.setRight(left);
            }
            setParent(left,parent);
        }
    }
    private void setParent(RBTreeNode<T> node,RBTreeNode<T> parent){
        if(node!=null){
            node.setParent(parent);
            if(parent==root){
                node.setParent(null);
            }
        }
    }
    /**
     * debug method,it used print the given node and its children nodes,
     * every layer output in one line
     * @param root
     */
    public void printTree(RBTreeNode<T> root){
        java.util.LinkedList<RBTreeNode<T>> queue =new java.util.LinkedList<RBTreeNode<T>>();
        java.util.LinkedList<RBTreeNode<T>> queue2 =new java.util.LinkedList<RBTreeNode<T>>();
        if(root==null){
            return ;
        }
        queue.add(root);
        boolean firstQueue = true;
        while(!queue.isEmpty() || !queue2.isEmpty()){
            java.util.LinkedList<RBTreeNode<T>> q = firstQueue ? queue : queue2;
            RBTreeNode<T> n = q.poll();
            if(n!=null){
                String pos = n.getParent()==null ? "" : ( n == n.getParent().getLeft()
                        ? " LE" : " RI");
                String pstr = n.getParent()==null ? "" : n.getParent().toString();
                String cstr = n.isRed()?"R":"B";
                cstr = n.getParent()==null ? cstr : cstr+" ";
                System.out.print(n+"("+(cstr)+pstr+(pos)+")"+"\t");
                if(n.getLeft()!=null){
                    (firstQueue ? queue2 : queue).add(n.getLeft());
                }
                if(n.getRight()!=null){
                    (firstQueue ? queue2 : queue).add(n.getRight());
                }
            }else{
                System.out.println();
                firstQueue = !firstQueue;
            }
        }
    }
    public static void main(String[] args) {
        RBTree<String> bst = new RBTree<String>();
        bst.addNode("d");
        bst.addNode("d");
        bst.addNode("c");
        bst.addNode("c");
        bst.addNode("b");
        bst.addNode("f");
        bst.addNode("a");
        bst.addNode("e");
        bst.addNode("g");
        bst.addNode("h");
        bst.remove("c");
        bst.printTree(bst.getRoot());
    }
}

6、树、森林、二叉树

上面已经学习了二叉树以及一些特殊的二叉树，接下来学习树的表示及相关操作。

6.1、树的存储结构

表现树的存储结构的形式有很多，有3种比较常见。

6.1.1、双亲表示法

这种表示方法中， 以一组连续的存储单元存储树的节点，每个节点除了数据域data外，还附设一个parent域用以指示其双亲节点的位置， 其结点形式如图37所示。

图37：双亲表示法的节点

这种存储结构利用了每个结点 （除根以外）只有唯一的双亲的性质。 在这种存储结构下 ， 求结点的双亲十分方便， 也很容易求树的根， 但求结点的孩子时需要遍历整个结构。

图38：树的双亲表示法示例

6.1.2、孩子表示法

由于树中每个节点可能有多棵子树， 则可用多重链表， 即每个结点有多个指针域， 其中每个
指针指向一棵子树的根节点，此时链表中的节点可以有如图 39 所示的两种结点节点。

图39：孩子表示法的两种节点


图 40 (a)所示为图 38 中的树的孩子表示法。 与双亲表示法相反， 孩子表示法便于那些涉及孩子的操作的实现。可以把双亲表示法和孩子表示法结合起来，即将双亲表示和孩子链表合在一起。 图 40(b) 所示的就是这种存储结构的一 例， 它和图 40 (a)表示的是同一棵树。

图40：图 38 的树的另外两种表示法

6.1.3、孩子兄弟法

又称二叉树表示法，或二叉链表表示法，即以二叉链表做树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，分别命名为 firstchild 域和 nextsibling域，其结点形式如图41所示。

图41：孩子兄弟表示法的结点

图42所示为图40中的树的孩子兄弟链表。利用这种存储结构便于实现各种树的操作。

图42：图38的树的二叉链表表示法

6.2、树转换为二叉树

在这里我们约定树是有序的，树中每一个节点的儿子结点按从左到右的次序顺序编号。

如图43所示的一棵树，根节点 A有三个儿子 B、 C、 D， 可以认为节点 B为 A的第一个儿子节点， 结点 C 为 A的第二个儿子节点， 节点 D 为 A 的第三个儿子节点。

图43：一般树

将一棵树转换为二叉树的方法是：

• (1) 树中所有相邻兄弟之间加一条连线；
• (2) 对树中的每个结点， 只保留它与第一个儿子结点之间的连线， 删去它与其他儿子结点之间的连线。
• (3) 以树的根结点为轴心， 将整棵树顺时针转动一定的角度， 使之结构层次分明。

树转换为二叉树的转换过程示意图如下：

图44：树转换为二叉树的过程

6.3、二叉树还原为树

树转换为二叉树这一转换过程是可逆的， 可以依据二叉树的根结点有无右儿子结点，将一棵二叉树还原为树， 具体方法如下：

• (1) 若某结点是其双亲的左儿子， 则把该结点的右儿子、 右儿子的右儿子、 … 都与该结点的双亲结点用线连起来；
• (2) 删掉原二叉树中所有的双亲结点与右儿子结点的连线；
• (3) 整理由(1)、（2)两步所得到的树， 使之结构层次分明。

二叉树还原为树的过程示意图如下所示：

图45：二叉树还原为树的过程

6.4、森林转换为二叉树

森林是若干棵树的集合， 森林亦可用二叉树表示。
森林转换为二叉树的方法如下：

• (1) 将森林中的每棵树转换成相应的二叉树；
• (2) 第一棵二叉树不动， 从第二棵二叉树开始， 依次将后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子， 当所有的二叉树连在一起后， 这样所得到的二叉树就是由森林转换得到的二叉树。

森林及其转换为二叉树的过程如下图所示：

图46：森林及其转换为二叉树的过程

6.5、树与森林的遍历

6.5.1、树的遍历

由树结构的定义可引出两种次序遍历树的方法：一种是先根（次序）遍历树，即：先访问树的根结点，然后依次先根遍历根的每棵子树；另一种是后根（次序）遍历，即先依次后根遍历每棵子树，然后访问根结点。

例如，对图 38 所示的树进行先根遍历，可得树的先根序列为：

R A D E B C F G H K

对该树进行后根遍历，则得树的后根序列为：

D E A B G H K F C R

按照森林和树相互递归的定义，可以推出森林的两种遍历方法：先序遍历和中序遍历。

6.5.2、森林的遍历

森林的遍历有两种方式： 前序遍历和中序遍历。

前序遍历

前序遍历的过程：

• (1) 访问森林中第一棵树的根结点；
• (2) 前序遍历第一棵树的根结点的子树森林；
• (3) 前序遍历剩余的其他子森林。

对于图 46 所示的森林进行前序遍历， 得到的结果序列为 A B C D E F G H I J K。

中序遍历

中序遍历的过程：

• (1) 中序遍历第一棵树的根结点的子树森林；
• (2) 访问森林中第一棵树的根结点；
• (3) 中序遍历剩余的其他子森林。

对于图 46 所示的森林进行中序遍历， 得到的结果序列为 B A D E F C J H K I G 。

根据森林与二叉树的转换关系以及森林和二叉树的遍历定义可以推论： 森林前序遍历和中序遍历分别与所转换的二叉树的前序遍历和中序遍历的结果序列相同。

7、B树

在前面学习了平衡二叉树，B树也是一种平衡查找树，不过不是二叉树。

B树也称B-树，它是一种多路平衡查找树。

一棵m阶的B树定义如下：

• 每个节点最多有m-1个关键字（可以存有的键值对）。
• 根节点最少可以只有1个关键字。
  * 非根节点至少有m/2个关键字。
• 每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
• 所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度都相同。
• 每个节点都存有索引和数据，也就是对应的key和value。

看一个B树的实例（字母大小 C>B>A）

图47：B树示例

看看B树的一些基本操作。

7.1、查找

查找和平衡二叉树类似，不过B树是多路的而已。以图47中查找15为例：

• （1）获取根节点的关键字进行比较，当前根节点关键字为39，15<39，所以往找到指向左边的子节点（二分法规则，左小右大，左边放小于当前节点值的子节点、右边放大于当前节点值的子节点）；
• （2） 获取到关键字12、22, 12<15<22，所以查找12和22中间的节点
• （3）获取到关键字13和15，因为15=15，所以返回关键字和指针信息；如果没有找到所包含的节点，返回null。

7.2、插入

插入的时候，需要记住一个规则：判断当前结点key的个数是否小于等于m-1，如果满足，直接插入即可，如果不满足，将节点的中间的key将这个节点分为左右两部分，中间的节点放到父节点中即可。

例子：在5阶B树中，结点最多有4个key,最少有2个key（注意：下面的节点统一用一个节点表示key和value）。

• 插入18，70，50,40
  

• 插入22
  
  插入22时，发现这个节点的关键字已经大于4了，所以需要进行分裂，分裂的规则在上面已经讲了，分裂之后，如下。

• 接着插入23，25，39
  

分裂，得到下面的。

7.3、删除

B树的删除操作相对于插入操作是相对复杂一些。

• 树初始状态如下

• 删除15，这种情况是删除叶子节点的元素，如果删除之后，节点数还是大于m/2，这种情况只要直接删除即可。

• 接着，把22删除，这种情况的规则：22是非叶子节点，对于非叶子节点的删除，我们需要用后继key（元素）覆盖要删除的key，然后在后继key所在的子支中删除该后继key。对于删除22，需要将后继元素24移到被删除的22所在的节点。

此时发现26所在的节点只有一个元素，小于2个（m/2），这个节点不符合要求，这时候的规则（向兄弟节点借元素）：如果删除叶子节点，如果删除元素后元素个数少于（m/2），并且它的兄弟节点的元素大于（m/2），也就是说兄弟节点的元素比最少值m/2还多，将先将父节点的元素移到该节点，然后将兄弟节点的元素再移动到父节点。这样就满足要求。

看看操作过程：

• 接着删除28，删除叶子节点，删除后不满足要求，所以，我们需要考虑向兄弟节点借元素，但是，兄弟节点也没有多的节点（2个），借不了，怎么办呢？如果遇到这种情况，首先，还是将先将父节点的元素移到该节点，然后，将当前节点及它的兄弟节点中的key合并，形成一个新的节点。

移动之后，跟兄弟节点合并。

8、B+树

B+树是B树的变体，也是一种多路搜索树。

B+树·和B树有一些共同的特性：

• 根节点至少一个元素
• 非根节点元素范围：m/2 <= k <= m-1

B+树和B树也有一些不一样的地方：

• B+树有两种类型的节点：非叶子结点（也称索引结点）和叶子结点。非叶子节点不存储数据，只存储索引，数据都存储在叶子节点。
• 非叶子结点中的key都按照从小到大的顺序排列，对于非叶子结点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。
• 每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接。
• 父节点存有右孩子的第一个元素的索引。

看一个B+树的示例：

8.1、查找

B+树的查找右两种方式：

• （1）从最小关键字起顺序查找；

• （2）从根节点开始，进行随机查找

在查找时，若非叶子节点上的关键字等于给定值，并不终止，而是继续向下直到叶子节点。因此，在B+树中，不管查找成功与否，每次查找都是走了一条从根到叶子节点的路径。其余同B树的查找类似。

8.2、插入

插入操作有一个规则：当节点元素数量大于m-1的时候，按中间元素分裂成左右两部分，中间元素分裂到父节点当做索引存储，但是，本身中间元素还是分裂右边这一部分的。

以一颗5阶B+树的插入过程为例，5阶B+树的节点最少2个元素，最多4个元素。

• 插入5，10，15，20

• 插入25，此时元素数量大于4个了，分裂

• 接着插入26，30，继续分裂

8.3、删除

删除操作比B树简单一些，因为叶子节点有指针的存在，向兄弟节点借元素时，不需要通过父节点了，而是可以直接通过兄弟节移动即可（前提是兄弟节点的元素大于m/2），然后更新父节点的索引；如果兄弟节点的元素不大于m/2（兄弟节点也没有多余的元素），则将当前节点和兄弟节点合并，并且删除父节点中的key，

下面来看一个具体的实例：

• B+树的初始状态

• 删除10，删除后，不满足要求，发现左边兄弟节点有多余的元素，所以去借元素，最后，修改父节点索引

• 删除元素5，发现不满足要求，并且发现左右兄弟节点都没有多余的元素，所以，可以选择和兄弟节点合并，最后修改父节点索引

• 发现父节点索引也不满足条件，所以，需要做跟上面一步一样的操作

B+树相比较B树有一些优点：

• B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快
• B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定
• B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高
• B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描

这里不再给出B树和B+树代码实现，代码实现可见参考【26】

---

上一篇：重学数据结构（五、串）

本博客为学习笔记，参考资料如下！
水平有限，难免错漏，欢迎指正！

参考：

【1】：邓俊辉 编著. 《数据结构与算法》
【2】：王世民 等编著 . 《数据结构与算法分析》
【3】： Michael T. Goodrich 等编著.《Data-Structures-and-Algorithms-in-Java-6th-Edition》
【4】：严蔚敏、吴伟民 编著 . 《数据结构》
【5】：程杰 编著 . 《大话数据结构》
【6】：[Data Structure] 数据结构中各种树
【7】：Tree
【8】：Binary Tree
【9】：Java数据结构与算法——二叉树及操作(包括二叉树遍历)
【10】：Java数据结构和算法（十）——二叉树
【11】：阿粉带你玩转二叉查找树
【12】：JAVA递归实现线索化二叉树
【13】：二叉查找树(三)之 Java的实现
【14】：一步一步写平衡二叉树（AVL树）
【15】：什么是平衡二叉树（AVL）
【16】：什么是平衡二叉树（AVL）
【17】：动画 | 什么是AVL树？
【18】：详解什么是平衡二叉树（AVL）（修订补充版）
【19】：红黑树深入剖析及Java实现
【20】：平衡查找树之红黑树
【21】：漫画：什么是红黑树？
【22】：面试官问你B树和B+树，就把这篇文章丢给他
【23】：平衡二叉树、B树、B+树、B*树 理解其中一种你就都明白了
【24】：B树和B+树的插入、删除图文详解
【25】：B树Java代码实现以及测试
【26】：Introduction of B-Tree
【27】：B+树详解