查找-树

1. 树的基本概念

• 度： 结点拥有的子树数称为结点的度
• 节点分类：
  • 叶结点（终端结点） 度为0的结点
  • 非终端结点（分支结点） 度不为0
    • 根节点
    • 内部节点

2. 二叉树

• 定义： 每个结点最多有两棵子树，左子树和右子树是有顺序的。

2.1 特殊二叉树

• 斜树
  • 所有的结点都只有左子树的二叉树叫左斜树
  • 所有结点都是只有右子树的二叉树叫右斜树
  • 斜树
• 满二叉树
  • 定义： 在二叉树中，所有节点非空，并且所有叶子都在同一层上
• 完全二叉树
  • 定义： 对一棵具有n个结点的二叉树按层序编号，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置相同，则这棵二叉树称为完全二叉树

2.2 二叉树性质

• 在二叉树的第n层上至多有 2^(i-1)个结点（n≥1）
• 深度为k的二叉树至多有2^k-1个结点
• 对任何一棵二叉树T，如果其叶子结点数为n0 ，度为2的结点数为n2 ，则n0 =n2 + 1
• 具有n个结点的完全二叉树的深度为 |log2(n+1)|（|x|表示不大于x的最大整数）
• 如果对一棵有n个结点的完全二叉树（其深度为）的结点按层序编号（从第1层到第层，每层从左到右），对任一结点i（1≤i≤n）有：
  • 如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点。
  • 如果2*i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。
  • 如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1。

2.3 二叉树遍历原理

• 前序遍历
  • 树为空返回空， 非空，根结点,左子树，右子树
• 中序遍历
  • 树为空返回空， 非空，左子树,根结点，右子树
• 后序遍历
  • 树为空返回空， 非空，左子树,右子树，根结点
• 层序遍历
  • 树为空返回空， 非空，从树的第一层，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。

3. 二叉排序树/二叉查找树

• 定义：

  • 左子树不空，则左子树上所有结点的值都小于跟节点值
  • 右子树不空，则右子树上所有节点的值都大于跟节点值
  • 左、右子树也分别为二叉排序树

• 插入

  • 根据二叉树定义，找到对应节点，插入到适合位置

• 删除

  • 叶子节点
    • 直接删除，树结构不受影响
  • 仅有左或右子树的结点
    • 父节点之间继承删除节点左子树或者右子树
  • 左右子树都有的结点
    • 找待删除结点的前驱或者后继节点替换位置，然后删除前驱或者后继节点。
      • 前驱节点 删除节点左孩子最右一个（肯定没有右孩子 满足第二次情况）。
      • 后继节点 删除节点右孩子最左一个（肯定没有左孩子 满足第二次情况）。

• 代码

package com.datastructure.tree;

/**
 * BinaryTree class
 *
 * @author 格林
 * @date 2020/3/25
 */
public class BinarySearchTree<E extends Comparable<E>> {

    private Node root;
    private int size;

    public E  remove(E e) {
        return remove(root, null, e,true);
    }

    /**
     *  三种情况
     *      node 是叶子节点
     *      node 左子树为空 或者 node 右子树为空
     *      node 左右子树都不为空
     * @param node
     * @param parent
     * @param e
     * @param isleft
     * @return
     */
    private E remove(Node node, Node parent, E e,boolean isleft) {
        if(node == null) {
            return null;
        }
        if(e.compareTo(node.e) > 0) {
           return  remove(node.right,node,e,false);
        } else if(e.compareTo(node.e) < 0) {
           return  remove(node.left,node,e,true);
        } else {
            E returnE = node.e;
            // 假如 左右子树都不为空
            if(node.left != null && node.right != null) {
                //转左，然后向右到尽头(找待删结点的前驱)
                Node s = node.left;
                Node q = node;
                while (s.right != null) {
                    q = s;
                    s = s.right;
                }
                //  s 指向被删除节点
                node.e = s.e;
                if(q != node) {
                    q.right = s.left;
                // 转左 节点没有右了
                } else {
                    q.left = s.left;
                }
            // 删除的是跟节点，并且只有一个子树。 我是通过父节点删除，先解决这种可能导致后面出现null的问题情况。
            }else if(parent == null ) {
                root = root.left != null ? root.left : root.right;
                // 删除节点左节点为空
            } else if(node.left == null) {
                if(isleft) {
                    parent.left = node.right;
                } else {
                    parent.right = node.right;
                }
                // 删除节点右节点为空
            } else if(node.right == null) {
                if(isleft) {
                    parent.left = node.left;
                } else {
                    parent.right = node.left;
                }
            }
            return returnE;
        }
    }

    public void add( E e) {
        add(root,null, e);
    }

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


    public boolean contains(E e) {
        return contains(root,e);
    }

    private boolean contains(Node node,E e){
        if(node == null){
            return false;
        }
        if(e.compareTo(node.e) == 0){
            return true;
        }else if(e.compareTo(node.e) < 0){
            return contains(node.left,e);
        }else {
            return contains(node.right,e);
        }
    }


    private class Node {
        E e;
        Node left,right;
        public void add(){

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

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        return inTraverse(root,stringBuilder);
    }

    /**
     * 中序遍历
     * @param node
     * @param stringBuilder
     * @return
     */
    public String inTraverse(Node node, StringBuilder stringBuilder ){
            if(node == null ) {
                return null;
            }
            inTraverse(node.left,stringBuilder);
            stringBuilder.append(" " + node.e);
            inTraverse(node.right,stringBuilder);
            return stringBuilder.toString();

    }
}

package com.datastructure.tree;
/**
 * Main class
 *
 * @author 格林
 * @date 2020/3/28
 */
public class Main {
    public static void main(String[] args) {
        int[] nums = new int[]{5,4,2,3,6,12,2131,12321,21};
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        for(int i : nums) {
            binarySearchTree.add(i);
        }
        System.out.println(binarySearchTree);
        binarySearchTree.remove(2);
        System.out.println(binarySearchTree);
        binarySearchTree.remove(100);
        System.out.println(binarySearchTree);
        binarySearchTree.remove(12321);
        System.out.println(binarySearchTree);

    }
}

//控制台输出
 2 3 4 5 6 12 21 2131 12321
 3 4 5 6 12 21 2131 12321
 3 4 5 6 12 21 2131 12321
 3 4 5 6 12 21 2131

• 总结
  1. 二叉排序树的查找性能取决于二叉排序树的形状。可问题就在于，二叉排序树的形状是不确定的。
  2. 对于二叉排序树的查找，走的就是从根结点到要查找的结点的路径，其比较次数等于给定值的结点在二叉排序树的层数
  3. 最好情况 深度与完全二叉树相同，那么查找的时间复杂也就为O(logn)
  4. 最坏情况 斜树，查找时间复杂度为O(n)，这等同于顺序查找

4. 平衡二叉树/AVL树

• 定义 是一种二叉排序树，其中每一个节点的左子树和右子树的高度差绝对值不超过1
• 优点 二叉树结构更好，从而提供了查找的速度
• 缺点 插入和删除操作复杂化，降低了插入和删除操作的速度。
• 适合场景 建立就很少进行插入和删除操作，主要用于查询。

5. B树/B-树

• 一个m阶的B树具有如下属性

  • 如果根结点不是叶结点，则其至少有两棵子树。
  • 每个非根的分支结点都有k-1个元素和k个孩子，其中[m/2]<=k<=m，每个叶子节点都有k-1个元素。
  • 所有叶子结点都位于同一层次。
  • 所有分支结点，包含n 和n个关键字 n+1个孩子。每个关键字左边孩子小于关键字，关键字右边孩子大于关键字
    • image.png

• 场景

  • 内外存的数据交互
    • 内存与外存交换数据次数频繁，会造成了时间效率上的瓶颈，那么B树结构怎么就可以做到减少次数呢
      • 当要处理的外存 如硬盘(是将所有的信息分割成相等大小的页面，每次硬盘读写的都是一个或多个完整的页面，对于一个硬盘来说，一页的长度可能是211到214个字节。)数据量很大，因此无法一次全部装入内存。我们会对B树进行调整，使得使得B树的阶数（或结点的元素）与硬盘存储的页面大小相匹配
        • 比如说一棵B树的阶为1001（即1个结点包含1000个关键字），高度为2，它可以储存超过10亿个关键字，我们只要让根结点持久地保留在内存中，那么在这棵树上，寻找某一个关键字至多需要两次硬盘的读取即可

• n个关键字的m阶B树，最坏情况是要查找几次

  • image.png

• B树不足

  • B树结构，通过中序遍历来顺序查找树中的元素，这一切都是在内存中进行，可是在B树结构中，往返于每个结点之间也就意味着，我们必须得在硬盘的页面之间进行多次访问
    • 如 image.png

    • 中序遍历所有的元素，页面2→页面1→页面3→页面1→页面4→页面1→页面5

5.1 2-3树（3阶B树）

• 定义
  • 其中的每一个结点都具有两个孩子（我们称它为2结点）或三个孩子（我们称它为3结点）
  • 一个2结点包含一个元素和两个孩子（或没有孩子），左子树包含的元素小于该元素，右子树包含的元素大于该元素。
  • 一个3结点包含一小一大两个元素和三个孩子（或没有孩子），左子树包含小于较小元素的元素，右子树包含大于较大元素的元素，中间子树包含介于两元素之间的元素。

6. B+树

• 一棵m阶的B+树和m阶的B树的差异在于

  • 有n棵子树的结点中包含有n个关键字
  • 所有的叶子结点包含全部关键字的信息，及指向含这些关键字记录的指针，叶子结点本身依关键字的大小自小而大顺序链接
  • 所有分支结点可以看成是索引，结点中仅含有其子树中的最大（或最小）关键字

• 场景

  • 文件系统所需而出的一种B树的变形树
  • 带有范围的查找

• 效率稳定

  • 非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

7. 红黑树

• 定义
  • 每个节点或黑色或红色
  • 根节点是黑色的
  • 每个叶子节点是黑色的
  • 如果也一个节点是红色的，则它的两个子节点都是黑色的
  • 对于每个节点，从该节点到其所有后代节点的简单路径上，均包含相同数目的黑节点。
• 与平衡二叉树比较
  • 查找 查询性能略微逊色于AVL树
  • 插入和删除 avl树每次插入删除会进行大量的平衡度计算，平衡二叉树任何不平衡都会在三次旋转之内解决，较于avl树为了维持平衡的开销要小得多。

7.1 左偏红黑树

• 定义
  • 对红黑树进行了进一步的限制，一个黑色节点左右儿子
    • 要么全是黑色
    • 要么左儿子是红色，右儿子是黑色。
  • 等价定义
    • 红连接均为左链接
    • 没有任何一个节点同时和两条红链接相连
    • 任何一个节点向下遍历到其子孙的叶子节点，所经过的黑节点个数相等
      -左偏红黑树 与 2-3树 关系
  • 如果一颗红黑树的红链接画平，红链接相连的节点合并，得到的就是一颗2-3 树。
  • 将红链接画平，一颗红黑树就是一颗2-3树

• 情况分析与代码

  • 颜色修正操

    • 左旋
      • 左旋H
    • 右旋
      • 右旋H
    • 颜色转换
      • H节点变红，H左右子节点变黑

  • 插入 X

    • 情况分析
      • 插入位置是 2节点
        • 小于 新增红色节点
        • 大于 产生红色右连接，X父节点 左旋
      • 插入位置是 3节点
        • 大于原树两个键 新增红色节点 产生两个子节点都是红色，颜色转换
        • 小于原树两个键 产生两条连续的红链接 X父节点 右旋，变成第一种情况
        • 两个键之间 产生红色右链接，并且父节点也是红色 X父节点 左旋，变成第二种情况
      • 总结
        • 如果右子节点是红色，左子节点是黑色， 左旋
        • 如果左子节点是红色，左子节点的左子节点也是红色， 右旋
        • 如果左子节点，右子节点都是红色，颜色转换

  • 删除 X

    • 删除最小键
      • 情况分析
        • 删除位置3节点 直接删除
        • 删除2节点 沿左链接向下进行变换，确保当前节点不是2节点（可能是3，临时4节点）
        • 跟节点两种情况
          • 跟是2节点，且它的两个子节点都是2节点，这个三个节点变成一个4节点
          • 保证跟节点左子节点不是2节点 必要的话，可以从右侧兄弟节点借。
      • 总结
        • 如果当前结点的左子节点不是2节点，完成
        • 左子节点是2节点，兄弟不是2节点，将左子节点的兄弟节点中一个键移动到左子节点中
        • 左子节点，兄弟都是2节点，将左子节点，父节点中的最小键，左子节点兄弟节点合并为一个4节点，使父节点由3节点变成2节点或者4节点变成3节点

  • 代码

package com.datastructure.tree.rbtree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * RedBlackTree class
 *
 * @author 格林
 * @date 2020/3/31
 */
public class RedBlackTree<Key extends Comparable<Key>, Value> {
    public static final boolean RED = true;
    public static final boolean BLACK =false;

    private  Node root;

    private class Node{
        boolean color;
        Key key;
        Value value;
        /**
         * 这颗树的结点总数
         */
        int N;
        Node left, right;

        public Node(boolean color, Key key, Value value, int n) {
            this.color = color;
            this.key = key;
            this.value = value;
            N = n;
        }

        @Override
        public String toString() {
            return key +" " + (color ? "Red" : "BLACK");
        }
    }

    public boolean isRed(Node node) {
        if(node == null) return false;
        return node.color == RED;
    }

    public void moveflipColors(Node node) {
        node.color = BLACK;
        node.left.color = RED;
        node.right.color = RED;
    }

    private Node balance(Node h){
        if (isRed(h.right)) h = rotateLeft(h);
        if (isRed(h.right) && !isRed(h.left)) h=rotateLeft(h);
        
        if (isRed(h.left) && isRed(h.left.left)) h=rotateRight(h);
        if (isRed(h.left) && isRed(h.right))    flipColors(h);
        h.N = size(h.left)+size(h.right)+1;
        return h;
    }


    public void deleteMin(){
        if(!isRed(root.left) && !isRed(root.right))
            root.color = RED;
        root = deleteMin(root);
        if(!isEmpty())
            root.color = BLACK;
    }

    private Node deleteMin(Node node) {
        if(node.left == null) {
            return null;
        }
        if(!isRed(node.left) && !isRed(node.right))
            node = moveRedLeft(node);
        node.left = deleteMin(node.left);
        return balance(node);
    }

    public void deleteMax() {
        if(!isRed(root.left) && !isRed(root.right))
            root.color = RED;
        root = deleteMax(root);
        if(!isEmpty())
            root.color = BLACK;
    }

    private Node deleteMax(Node h) {
        if(isRed(h.left))
            h = rotateRight(h);
        if(h.right == null)
            return null;
        if(!isRed(h.right) && !isRed(h.left))
            h = moveRedRight(h);
        h.right = deleteMax(h.right);
        return balance(h);
    }

    public void levelOrder() {
        Queue<Node> nodeQueue = new LinkedList<>();
        nodeQueue.add(root);
        while (!nodeQueue.isEmpty()) {
            Node node = nodeQueue.poll();
            System.out.println(node);
            if(node.left != null ) {
                nodeQueue.add(node.left);
            }
            if(node.right != null) {
                nodeQueue.add(node.right);
            }
        }
    }

    /**
     *

     *          \\
     *      4.5
     *    /   \
     *   3     6
     *  / \  //  \
     *   1   4   5    7
     *
     *          |
     *      4.5
     *   //   \\
     *   3     6
     *  / \  //  \
     *   1   4   5    7
     *
     *          |
     *      4.5
     *   //   \\
     *   3     5
     *  / \      \\
     *   1   4        6
     *                \
     *                 7
     *
     *        |
     *    5
     *  //  \\
     *    4.5   6
     *  //        \
     *  3         7
     * / \
     * 1   4
     * @param h
     * @return
     */
    private Node moveRedLeft(Node h){
        /**
         * 假设节点h为红色，左右子节点都是黑色
         * 将节点h.left 或者 h.left 的子节点之一变红
         * 如果该节点的右节点的左节点是红色节点，说明兄弟节点不是2-节点，可以从兄弟节点中借一个
         */
        moveflipColors(h);     // 从父节点中借一个
        if(isRed(h.right.left)){    // 判断兄弟节点，如果是非红节点，也从兄弟节点中借一个
            h.right = rotateRight(h.right);
            h = rotateLeft(h);
        }
        return h;
    }

    private Node moveRedRight(Node h){
        /**
         * 假设节点h为红色，左右子节点都是黑色
         *  将节点h.left 或者 h.left 的子节点之一变红
         */
        moveflipColors(h);
        if(isRed(h.left.left)){         // 在这里对于兄弟节点的判断都是.left，因为红色节点只会出现在左边
            h=rotateRight(h);
//            moveflipColors(h);
        }
        return h;
    }

    public void delete(Key key){
        if(!isRed(root.left)&& !isRed(root.right)){
            root.color = RED;
        }
        root = delete(root,key);
        if(root != null)
            root.color = BLACK;
    }

    private Node delete(Node h, Key key){
        if(key.compareTo(h.key) < 0){          // 当目标键小于当前键的时候，我们做类似于寻找最小是的操作，向树左边移动，合并父子结点来消除2-结点
            if(h.left == null){
                return null;
            }
            if(isRed(h.left) && !isRed(h.left.left)){
                h = moveRedLeft(h);
            }
            h.left = delete(h.left,key);
        }else{                  // 当目标键大于当前键的时候，我们向右移动，并做与deleteMax相同的操作，如果相同的话，我们使用和二叉树的删除一样的操作，获取当前键的右子树的最小健，然后交换，并将目标键删除
            if(isRed(h.left)){
                h = rotateRight(h);
            }
            if(key.compareTo(h.key) == 0 && (h.right == null) ){    // 我们没有找到目标键，我们将其删除
                return null;
            }
            if(!isRed(h.right) && isRed(h.right.left)){
                h = moveRedRight(h);
            }
            if(key.compareTo(h.key) == 0 ){
                h.value = get(h.right,min(h.right).key);
                h.key = min(h.right).key;
                h.right = deleteMin(h.right);
            }
            else h.right = delete(h.right,key);
        }
        return balance(h);
    }


    public Value get(Key key){
        return get(root, key);
    }
    private Value get(Node node, Key key){
        if(node == null)
            return  null;
        int cmp = key.compareTo(node.key);
        if(cmp < 0)
            return get(node.left, key);
        else if(cmp > 0)
            return get(node.right, key);
        else
            return node.value;
    }

    /**
     * 查找以node为根节点红黑树的最小节点
     * 深度优先遍历，递归实现
     *
     * @param node
     * @return BinarySearchTree<E>.Node
     * @author ronglexie
     * @version 2018/8/18
     */
    private Node min(Node node) {
        if(isEmpty()){
            throw new IllegalArgumentException("BinarySearchTree is empty !");
        }
        if(node.left == null){
            return node;
        }
        return min(node.left);
    }

    private boolean isEmpty() {
        return root == null;
    }

    public void flipColors(Node node) {
        node.color = RED;
        node.left.color = BLACK;
        node.right.color = BLACK;
    }
    //   node                     x
    //  /   \     左旋转         /  \
    // T1   x   --------->   node   T3
    //     / \              /   \
    //    T2 T3            T1   T2

    /**
     * 什么时候左旋 就是node节点是红的。
     * 通过左旋node变成左节点，符合红黑树定义
     * @param node
     * @return
     */
    Node rotateLeft(Node node) {
        Node t = node.right;
        node.right = t.left;
        t.left = node;
        t.color = node.color;
        node.color = RED;
        t.N = node.N;
        node.N = 1  + size(node.left) +size( node.right);
        return t;
    }

    /**
     *
     * @param node
     */
    //     node                   x
    //    /   \     右旋转       /  \
    //   x    T2   ------->   y   node
    //  / \                       /  \
    // y  T1                     T1  T2

    /**
     * 右旋 就是因为左边有两个连续的红节点
     * 通过右旋使得左边红节点x 红色传到右边
     * @param node
     */
    public Node rotateRight(Node node) {
        Node t = node.left;
        node.left = t.right;
        t.right = node;
        t.color = node.color;
        node.color = RED;
        t.N = node.N;
        node.N = 1  + size(node.left) +size( node.right);
        return t;
    }

    public int size() {
        return size(root);
    }
    public int size(Node node) {
        if(node == null) return 0;
        else return node.N;
    }

    public void put(Key key, Value value) {
        root = put(root, key, value);
        root.color = BLACK;
    }

    public Node put(Node node, Key key, Value value) {
        if(node == null)
            return new Node(RED,key,value,1);
        int cmp = key.compareTo(node.key);
        if(cmp < 0)
            node.left = put(node.left,key,value);
        else if(cmp > 0)
            node.right = put(node.right,key,value);
        else
            node.value = value;

        if(isRed(node.right) && !isRed(node.left)) node = rotateLeft(node);
        if(isRed(node.left) && isRed(node.left.left)) node = rotateRight(node);
        if(isRed(node.left) && isRed(node.right)) flipColors(node);

        node.N = size(node.left) + 1 + size(node.right);
        return node;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        return inTraverse(root,stringBuilder);
    }

    /**
     * 中序遍历
     * @param node
     * @param stringBuilder
     * @return
     */
    public String inTraverse(Node node, StringBuilder stringBuilder ){
        if(node == null ) {
            return null;
        }
        inTraverse(node.left,stringBuilder);
        stringBuilder.append(" " + node.key +  " color " + (node.color == true ? "red" : "black") +"|" );
        inTraverse(node.right,stringBuilder);
        return stringBuilder.toString();

    }

}

• 测试

public class Main {
    public static void main(String[] args) {

        RedBlackTree tree = new RedBlackTree<>();
        tree.put(2,"qmd");
        tree.put(1,"xxp");
        tree.put(4,"ddd");
        tree.put(3,"ycy");
        tree.put(3,"ycyycy");

        tree.levelOrder();
        System.out.println(tree.toString());
        tree.deleteMin();
        System.out.println(tree.toString());
        tree.deleteMax();
        System.out.println(tree.toString());
        tree.delete(3);
        System.out.println(tree.toString());

    }
}

// 输出
2 BLACK
1 BLACK
4 BLACK
3 Red
 1 color black| 2 color black| 3 color red| 4 color black|
 2 color black| 3 color black| 4 color black|
 2 color red| 3 color black|
 2 color black|

参考 算法第四版，大话数据结构