树

平衡二叉树（二分搜索树 BST: Binary Search Tree ）

首先如果普通二叉树每个节点满足：左子树所有节点值小于它的根节点值，且右子树所有节点值大于它的根节点值，则这样的二叉树就是排序二叉树。

构建二叉树的基本属性和节点Node：

public class MyBST<E extends Comparable<E>> {
    private class Node {
        E e;
        Node left;
        Node right;

        public Node(E e) {
            this.e = e;
        }
    }

    private int size;
    private Node root;
}

插入操作

首先要从根节点开始往下找到自己要插入的位置（即新节点的父节点）；具体流程是：新节点与当前节点比较，如果相同则表示已经存在且不能再重复插入；如果小于当前节点，则到左子树中寻找，如果左子树为空则当前节点为要找的父节点，新节点插入到当前节点的左子树即可；如果大于当前节点，则到右子树中寻找，如果右子树为空则当前节点为要找的父节点，新节点插入到当前节点的右子树即可。

递归插入：

    public boolean add(E e) {
        int oldSize = size;
        root = add(e, root);
        if (oldSize != size) {
            return true;
        }
        return false;
    }

    private Node add(E e, Node node) {
        if (node == null) {
            size++;
            return new Node(e);
        }
        if (e.compareTo(node.e) <= 0) {
            node.left = add(e, node.left);
        } else {
            node.right = add(e, node.right);
        }
        return node;
    }

删除操作

1. 删除树中最小元素

应为树的左子树的值都小于或等于父节点的值，树的右节点的值大于父节点的值，故：最小值只能在树的最左边的叶子结点上或值是没有左叶子结点的父节点上。

    public void delMin(Node node) {
        if (node == null) {
            return;
        }
        if (node.left != null) {
            if (node.left.left == null) {
                node.left = node.left.right;
                size--;
            } else {
                delMin(node.left);
            }
        }
    }

2. 删除树中最大元素

（与删除最小元素原理相似，只是这次是在右边）。

    public void delMax(Node node) {
        if (node == null) {
            return;
        }
        if (node.right!= null) {
            if (node.right.right == null) {
                node.right = node.right.left;
                size--;
            } else {
                delMax(node.right);
            }
        }
    }

3. 任意删除某个元素操作

删除操作主要分为三种情况， 即要删除的节点无子节点，要删除的节点只有一个子节点，要删除的节点有两个子节点。

1. 对于要删除的节点无子节点可以直接删除，即让其父节点将该子节点置空即可。
2. 对于要删除的节点只有一个子节点，则替换要删除的节点为其子节点。
3. 对于要删除的节点有两个子节点， 则首先找该节点的替换节点（即该节点下的右子树中最小的节点或者是该节点下左子树中最大节点），接着替换要删除的节点为替换节点，然后删除替换节点。

    // 删除掉以node为根的二分搜索树中值为e的节点, 递归算法
    // 返回删除节点后新的二分搜索树的根
    private Node remove(Node node, E e){

        if( node == null )
            return null;

        if( e.compareTo(node.e) < 0 ){
            node.left = remove(node.left , e);
            return node;
        }
        else if(e.compareTo(node.e) > 0 ){
            node.right = remove(node.right, e);
            return node;
        }
        else{   // e.compareTo(node.e) == 0

            // 待删除节点左子树为空的情况
            if(node.left == null){
                Node rightNode = node.right;
                node.right = null;
                size --;
                return rightNode;
            }

            // 待删除节点右子树为空的情况
            if(node.right == null){
                Node leftNode = node.left;
                node.left = null;
                size --;
                return leftNode;
            }

            // 待删除节点左右子树均不为空的情况

            // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
            // 用这个节点顶替待删除节点的位置
            Node successor = minimum(node.right);
            successor.right = removeMin(node.right);
            successor.left = node.left;

            node.left = node.right = null;
            return successor;
        }
    }

查询操作

查找操作的主要流程为：先和根节点比较，如果相同就返回， 如果小于根节点则到左子树中递归查找，如果大于根节点则到右子树中递归查找。因此在排序二叉树中可以很容易获取最大（最右最深子节点）和最小（最左最深子节点）值。
(方法很简单，这里就不上代码了)

扩展 二分搜索树的　键值对（Ｋ，Ｖ）实现

package com.njauit.tree;

/**
 * @author 张文军 @Description: @Company:it.njauit.cn
 * @version:1.0
 * @date 2020/4/1213:12
 */
public class MyBSTKV<K extends Comparable<K>, V> {
  private class Node {
    private K key;
    private V value;
    private Node right, left;

    public Node(K key, V value) {
      this.key = key;
      this.value = value;


    }
  }

  private Node root;
  private int size;

  public int getSize() {
    return size;
  }

  public void add(K key, V value) {
    root = add(key, value, root);
  }

  private Node add(K key, V value, Node node) {
    if (node == null) {
      size++;
      return new Node(key, value);
    }

    if (key.compareTo(node.key) < 0) {
      node.left = add(key, value, node.left);
    } else if (key.compareTo(node.key) > 0) {
      node.right = add(key, value, node.right);
    }else{//key 相同的情况下，相当于是在做跟新操作。
        node.value = value;
    }
    return node;
  }
}

利用这种树结构，可以很简单的实现集合了。

平衡二叉树 ( AVL )

出现原因：

应为二分搜索树在极端条件下会退化为链表
比如这样：

为了解决这种情况的发生，应此平衡二叉数才会应运而生。

主要性质

平衡二叉树（Balanced BinaryTree）又被称为AVL树。它具有以下性质：

• 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1

• 并且左右两个子树都是一棵平衡二叉树。如：

• 某节点的左子树与右子树的高度(深度)差即为该节点的平衡因子（BF,Balance Factor）平衡因子的取值只能为0、-1、1。

• 最小不平衡子树：距离插入结点最近的，且以平衡因子的绝对值大于1的结点为根结点的子树。

下面这棵树就是一个不平衡二叉数：

平衡二叉树调整

平衡二叉树的失衡调整主要是通过 旋转最小失衡子树来实现的 。根据旋转的方向有两种处理方式，左旋 与 右旋 。

旋转的目的就是减少高度，通过降低整棵树的高度来平衡。哪边的树高，就把那边的树向上旋转。

旋转过程

• （LL）当最小不平衡子树根结点的平衡因子大于1时，该子树右旋。
  
• （RR）当最小不平衡子树根结点的平衡因子小于-1时，该子树左旋。
  
• （RL / LR）插入结点后，最小不平衡子树的平衡因子与它的子树的平衡因子符号相反时，需要对它的子树先进行一次旋转，再对它本身反向旋转一次才能完成平衡操作。
  

代码实现

import java.util.ArrayList;

public class AVLTree<K extends Comparable<K>, V> {

    private class Node{
        public K key;
        public V value;
        public Node left, right;
        public int height;

        public Node(K key, V value){
            this.key = key;
            this.value = value;
            left = null;
            right = null;
            height = 1;
        }
    }

    private Node root;
    private int size;

    public AVLTree(){
        root = null;
        size = 0;
    }

    public int getSize(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    // 判断该二叉树是否是一棵二分搜索树
    public boolean isBST(){

        ArrayList<K> keys = new ArrayList<>();
        inOrder(root, keys);
        for(int i = 1 ; i < keys.size() ; i ++)
            if(keys.get(i - 1).compareTo(keys.get(i)) > 0)
                return false;
        return true;
    }

    private void inOrder(Node node, ArrayList<K> keys){

        if(node == null)
            return;

        inOrder(node.left, keys);
        keys.add(node.key);
        inOrder(node.right, keys);
    }

    // 判断该二叉树是否是一棵平衡二叉树
    public boolean isBalanced(){
        return isBalanced(root);
    }

    // 判断以Node为根的二叉树是否是一棵平衡二叉树，递归算法
    private boolean isBalanced(Node node){

        if(node == null)
            return true;

        int balanceFactor = getBalanceFactor(node);
        if(Math.abs(balanceFactor) > 1)
            return false;
        return isBalanced(node.left) && isBalanced(node.right);
    }

    // 获得节点node的高度
    private int getHeight(Node node){
        if(node == null)
            return 0;
        return node.height;
    }

    // 获得节点node的平衡因子
    private int getBalanceFactor(Node node){
        if(node == null)
            return 0;
        return getHeight(node.left) - getHeight(node.right);
    }

    // 对节点y进行向右旋转操作，返回旋转后新的根节点x
    //        y                              x
    //       / \                           /   \
    //      x   T4     向右旋转 (y)        z     y
    //     / \       - - - - - - - ->    / \   / \
    //    z   T3                       T1  T2 T3 T4
    //   / \
    // T1   T2
    private Node rightRotate(Node y) {
        Node x = y.left;
        Node T3 = x.right;

        // 向右旋转过程
        x.right = y;
        y.left = T3;

        // 更新height
        y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
        x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;

        return x;
    }

    // 对节点y进行向左旋转操作，返回旋转后新的根节点x
    //    y                             x
    //  /  \                          /   \
    // T1   x      向左旋转 (y)       y     z
    //     / \   - - - - - - - ->   / \   / \
    //   T2  z                     T1 T2 T3 T4
    //      / \
    //     T3 T4
    private Node leftRotate(Node y) {
        Node x = y.right;
        Node T2 = x.left;

        // 向左旋转过程
        x.left = y;
        y.right = T2;

        // 更新height
        y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
        x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;

        return x;
    }

    // 向二分搜索树中添加新的元素(key, value)
    public void add(K key, V value){
        root = add(root, key, value);
    }

    // 向以node为根的二分搜索树中插入元素(key, value)，递归算法
    // 返回插入新节点后二分搜索树的根
    private Node add(Node node, K key, V value){

        if(node == null){
            size ++;
            return new Node(key, value);
        }

        if(key.compareTo(node.key) < 0)
            node.left = add(node.left, key, value);
        else if(key.compareTo(node.key) > 0)
            node.right = add(node.right, key, value);
        else // key.compareTo(node.key) == 0
            node.value = value;

        // 更新height
        node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));

        // 计算平衡因子
        int balanceFactor = getBalanceFactor(node);

        // 平衡维护
        // LL
        if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0)
            return rightRotate(node);

        // RR
        if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0)
            return leftRotate(node);

        // LR
        if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // RL
        if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        return node;
    }

    // 返回以node为根节点的二分搜索树中，key所在的节点
    private Node getNode(Node node, K key){

        if(node == null)
            return null;

        if(key.equals(node.key))
            return node;
        else if(key.compareTo(node.key) < 0)
            return getNode(node.left, key);
        else // if(key.compareTo(node.key) > 0)
            return getNode(node.right, key);
    }

    public boolean contains(K key){
        return getNode(root, key) != null;
    }

    public V get(K key){

        Node node = getNode(root, key);
        return node == null ? null : node.value;
    }

    public void set(K key, V newValue){
        Node node = getNode(root, key);
        if(node == null)
            throw new IllegalArgumentException(key + " doesn't exist!");

        node.value = newValue;
    }

    // 返回以node为根的二分搜索树的最小值所在的节点
    private Node minimum(Node node){
        if(node.left == null)
            return node;
        return minimum(node.left);
    }

    // 从二分搜索树中删除键为key的节点
    public V remove(K key){

        Node node = getNode(root, key);
        if(node != null){
            root = remove(root, key);
            return node.value;
        }
        return null;
    }

    private Node remove(Node node, K key){

        if( node == null )
            return null;

        Node retNode;
        if( key.compareTo(node.key) < 0 ){
            node.left = remove(node.left , key);
            // return node;
            retNode = node;
        }
        else if(key.compareTo(node.key) > 0 ){
            node.right = remove(node.right, key);
            // return node;
            retNode = node;
        }
        else{   // key.compareTo(node.key) == 0

            // 待删除节点左子树为空的情况
            if(node.left == null){
                Node rightNode = node.right;
                node.right = null;
                size --;
                // return rightNode;
                retNode = rightNode;
            }

            // 待删除节点右子树为空的情况
            else if(node.right == null){
                Node leftNode = node.left;
                node.left = null;
                size --;
                // return leftNode;
                retNode = leftNode;
            }

            // 待删除节点左右子树均不为空的情况
            else{
                // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
                // 用这个节点顶替待删除节点的位置
                Node successor = minimum(node.right);
                //successor.right = removeMin(node.right);
                successor.right = remove(node.right, successor.key);
                successor.left = node.left;

                node.left = node.right = null;

                // return successor;
                retNode = successor;
            }
        }

        if(retNode == null)
            return null;

        // 更新height
        retNode.height = 1 + Math.max(getHeight(retNode.left), getHeight(retNode.right));

        // 计算平衡因子
        int balanceFactor = getBalanceFactor(retNode);

        // 平衡维护
        // LL
        if (balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0)
            return rightRotate(retNode);

        // RR
        if (balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0)
            return leftRotate(retNode);

        // LR
        if (balanceFactor > 1 && getBalanceFactor(retNode.left) < 0) {
            retNode.left = leftRotate(retNode.left);
            return rightRotate(retNode);
        }

        // RL
        if (balanceFactor < -1 && getBalanceFactor(retNode.right) > 0) {
            retNode.right = rightRotate(retNode.right);
            return leftRotate(retNode);
        }

        return retNode;
    }
}

总结

二叉平衡树(AVL)是在二叉排序树的基础上进一步完善得到的，所以二叉平衡树首先是一棵二叉排序树，其次它每一个结点的左右子树的高度差最多为1。二叉平衡树平衡因子大于1时右旋，平衡因子小于-1时左旋，进而使树平衡。二叉平衡树查找的时间复杂度为O(logn)，其中n为二叉树结点个数。

2-3树

性质

• 满足二分搜索树的基本性质
• 节点可以存放一个元素或者两个元素
  
  每个节点有2个或者3个孩子一2-3树
• 是绝对平衡的（任意节点到它所有的叶子节点的深度都是相等的。）

例如：

2-3树的数字代表一个节点有2到3个子树。它也满足二分搜索树的基本性质，但它不属于二分搜索树。

2-3树查找元素

2-3树的查找类似二分搜索树的查找，根据元素的大小来决定查找的方向。要判断一个元素是否存在，我们先将待查找元素和根节点比较，如果它和其中任意一个相等，那查找命中；否则根据比较的结果来选择查找的方向。

2-3树插入元素

插入元素首先进行查找命中，若查找命中则不予插入此元素，如果需要支持重复的元素则将这个元素对象添加一个属性count。若查找未命中，则在叶子节点中插入这个元素。

空树的插入很简单，创建一个节点即可。如果不是空树，插入的情况分为4种：

1. 向2-节点中插入元素：
   如果未命中查找结束于2-节点，直接将2-节点替换为3-节点，并将待插入元素添加到其中。
   

2. 向一颗只含有一个3-节点的树中插入元素:
   如果命中查找结束于3-节点，先临时将其成为4-节点，把待插入元素添加到其中，然后将4-节点转化为3个2-节点，中间的节点成为左右节点的父节点。如果之前临时4-节点有父节点，就会变成向一个父节点为2-节点的3-节点中插入元素，中间节点与父节点为2-节点的合并。
   

3. 向一个父节点为3-节点的3-节点中插入元素
   插入元素后一直向上分解临时的4-节点，直到遇到2-节点的父节点变成3-节点不再分解。如果达到树根节点还是4-节点，则进行分解根节点，此时树高+1（只有分解根节点才会增加树高）
   

插入元素过程：

红黑树

红黑树也是一种二叉平衡树，它满足如下几个特性（根据算法中的定义）：

• 根节点是黑色的。
• 红链接均为左链接。
• 从任一节点到其可达叶子节点，经过的黑色节点数量一样（黑平衡）。
• 没有任何一个节点同时与两个红链接相连（如果一个节点是红色的，则它的子节点必须是黑色的。）。
• 每一个叶子结点（最后的空节点 NULL ）都是黑色的。

这个定义可能跟我们平常看到的不太一样，由于是以2-3树来理解红黑树，定义红链在左边，这样才能跟2-3树完全对应上。

将2-3树转换成红黑树

主要思想：3节点分裂成2节点。

将3节点的第一个元素，作为第二个元素的左节点，并用红色的线连接，此时红色线连接的节点就相当于红色。

红黑树和2-3树的等价性：

红黑树的添加元素操作（结合2-3树添加操作理解）

第一步: 将红黑树当作一颗二叉查找树，将节点插入。

第二步：将插入的节点着色为”红色”。

    根据被插入节点的父节点的情况，可以将”当节点 z 被着色为红色节点，并插入二叉树”划分为三种情况来处理。

1. 被插入的节点是根节点。
   处理方法：直接把此节点涂为黑色。

2. 被插入的节点的父节点是黑色。
   处理方法：什么也不需要做。节点被插入后，仍然是红黑树。

3. 被插入的节点的父节点是红色
   这种情况下，被插入节点是一定存在非空祖父节点的；进一步的讲，被插入节点也一定存在叔叔节点(即使叔叔节点为空，我们也视之为存在，空节点本身就是黑色节点)。理解这点之后，我们依据”叔叔节点的情况”，将这种情况进一步划分为 3种情况。

结合2-3树的理解，思考几个问题

1. 为什么红链规定在左边呢？
   我觉得是前人的一个约定，为了保持统一，简化处理，都放在左边。那都放右边是不是也可以呢？

2. 没有任何一个节点同时与两个红链接相连
   因为一个红链表示一个3节点，如果有2个红链相连，则表示为4节点，不符合2-3树定义。

3. 根节点为黑色
   只有3节点的左链才为红色。根节点没有父节点，不可能为红色。

根节点到叶子节点经过的黑色节点数目相同

因为2-3树是完美平衡的。红黑树中经过的黑节点数=其层数。