数据结构和算法之树

Scroll Down

什么是树,针对线性的查找往往访问时间会随着数据集的大小相关。所以在快速检索场景中不是很适合。树这种数据结构通常包含一个跟和若干个子树来构成,从跟到无子孙的子树(叶子节点)进过的边成为这棵树的高度。

二叉树

顾名思义二叉树就是这棵树的节点都最多只能有俩个子树(0-2)。
二叉树
二叉树的访问深度会比节点数要少得多,所以这一点也常被用来作为提神搜索速度,二叉搜索树的平均访问为对数阶$O(
)$。但是最差情况下则会退化为链表情况,所以这也是1.8HashMap拉链法 当链表过长之后的树化处理。毕竟最好的负载因子也无法解决链表过长的问题。

二叉搜索树

在二叉树的前提下,二叉搜索树的性质是比节点X大的节点均在X节点的右子树上,比节点X小的均在节点左子树上。让你来实现一颗二叉搜索树你需要考虑什么呢

  1. 需要抽象TreeNode。定义root。针对空树来讲root=null
  2. 递归构造树。
  3. 需要实现查找树,树中存放的元素需要实现比较器
  4. 删除数据 要保证当前树还维持二叉搜索树的性质
  5. 支持contains比较;
代码实现
  • 定义TreeNode节点
@Data
class MoodTreeNode<T extends Comparable< ? super T>> {
    T value;
    MoodTreeNode left;
    MoodTreeNode right;
}
  • 定义二叉检索树
/**
 * Mood 手刷二叉树系列 之 二叉搜索树
 * @param <T>
 */
public class MoodBinarySearchTree<T extends Comparable< ? super T>>{
    /**
     * 根节点
     */
    private  MoodTreeNode root;
}
  • 递归生成树
void insert(T t){
        root=insert(t,this.root);
    }
    MoodTreeNode insert(T t, MoodTreeNode treeNode){
        if (treeNode==null){
            return new MoodTreeNode(t,null,null);
        }
        int comparValue=treeNode.value.compareTo(t);
        if (comparValue>0){
            treeNode.left=insert(t,treeNode.left);
        }else if (comparValue<0){
            treeNode.right=insert(t,treeNode.right);
        }
        return treeNode;
    }
  • 删除节点
void remove(T t){
        root=remove(this.root,t);
    }

    MoodTreeNode remove(MoodTreeNode treeNode, T t) {
        if (treeNode == null) {
            return null;
        }
        int comparValue = t.compareTo((T)treeNode.value);
        if (comparValue > 0) {
            treeNode.right = remove(treeNode.right, t);
        } else if (comparValue < 0) {
            treeNode.left = remove(treeNode.left, t);
        } else if (treeNode.right != null && treeNode.left != null) {
            MoodTreeNode rightLeftMin = findMin(treeNode.right);
            treeNode.right = remove(treeNode.right, (T) rightLeftMin.value);
        } else {
            treeNode = treeNode.left != null ? treeNode.left : treeNode.right;
        }
        return treeNode;
    }
  • 查询数据
T findMin(){
        MoodTreeNode treeNode=findMin(root);
        if (null==treeNode){
            return null;
        }
        return (T) treeNode.value;
    }
    MoodTreeNode findMin(MoodTreeNode treeNode){
        if (treeNode==null){
          return null;
        } else if (treeNode.left==null){
            return treeNode;
        }else {
            return findMin(treeNode.left);
        }
    }

二叉搜索树和样本数据影响颇大,但是平均访问是不多,当极端的数据集,就会退化为单链表,例如我们插入1,2,3,4,5;当我们查找5这势必要便利整颗树。所以就有了平衡的引入,当我们保证该二叉搜索树在什么时候左右子树的高度都在1之内,那么检索效率会极大的提升。

平衡二叉搜索树(AVL)

WX20201226-165608@2x

AVL简介

AVL树就是平衡搜索二叉树 说了好像没说一样。关注下平衡条件吧:每个节点的左子树和右子树的高度最多相差为1 。和搜索二叉树的区别在于 所有的更改结构的操作需要考虑,操作完毕之后是否还回慢足平衡条件。处理的方式就是旋转

AVL实现平衡法则

当我们对树进行插入删除操作会改变树的结构。重新让树回归到平衡的过程成为旋转,主要方式有单旋转和双旋转。当新节点插入A节点的左子树或者右子树。此时会导致A节点的左右子树的高度为2.这样的不平衡就会出现如下4中场景

  • 对A的左子树的左子树插入 LL
  • 对A的左子树的右子树插入 LR
  • 对A的右子树的左子树插入 RL
  • 对A的右子树的右子树插入 RR
    对于外边来讲,一般需要进行单旋转,内边则需要进行双旋转。
外边单旋转平衡AVL

LL

内边双旋转AVL

RL

AVL代码实现

代码实现

public class AVLTree<T extends Comparable<? super T>> {

    AvlNode<T> root;
    /**
     * 默认负载因子1
     * 比较左右子树高度的绝对值abs(left.height-right.height)<=ALLOWED_IMBALANCE
     */
    private static final Integer ALLOWED_IMBALANCE=1;

    private static class AvlNode<T>{

        T t;
        AvlNode left;
        AvlNode right;
        int height;
        AtomicInteger atomicInteger;
        AvlNode(T t){
            this(t,null,null);
        }
        AvlNode(T t, AvlNode left, AvlNode right){
            this.t=t;
            this.left=left;
            this.right=right;
            height=0;
            atomicInteger=new AtomicInteger(0);
        }
        private void autoIncrement(){
            atomicInteger.incrementAndGet();
        }
        private int getTime(){
            return atomicInteger.get();
        }
    }
    private int getHeight(AvlNode<T> node){
        return node==null?-1:node.height;
    }

    public void insert(T t){
        root=insert(t,this.root);
    }
    public void remove(T t){
         remove(t,this.root);
    }
    /**
     * 平衡二叉树插入
     * @param t
     * @param node
     * @return
     */
    private AvlNode<T> insert(T t,AvlNode<T> node){
        if (node==null){
            node=new AvlNode<T>(t);
            return node;
        }
        int result=t.compareTo(node.t);
        if (result<0){
            node.left=insert(t,node.left);
        }else if (result>0){
            node.right=insert(t,node.right);
        }else {
            node.autoIncrement();
        }
        return balance(node);
    }
    /**
     * 平衡二叉树平衡算法
     * @param node
     * @return
     */
    private AvlNode<T> balance(AvlNode<T> node) {
        if (node==null){
            return node;
        }
        if (getHeight(node.left)-getHeight(node.right)>ALLOWED_IMBALANCE){
            //左边失去平衡
            if (getHeight(node.left.left)>=getHeight(node.left.right)){
                node=rotateWithLeft(node);
            }else {
                node=rotateWithLeftRight(node);
            }
        }else if (getHeight(node.right)-getHeight(node.left)>ALLOWED_IMBALANCE){
            //右边失去平衡
            if (getHeight(node.right.right)>=getHeight(node.right.left)){
                node=rotateWitRight(node);
            }else {
                node=rotateWitRightLeft(node);
            }
        }
        node.height=Math.max(getHeight(node.left),getHeight(node.right))+1;
        return node;
    }

    /**
     * 平衡二叉树 RL旋转
     * @param node
     * @return
     */
    private AvlNode<T> rotateWitRightLeft(AvlNode<T> node) {
        node.right=rotateWithLeft(node.right);
        return rotateWitRight(node);
    }
    /**
     * 平衡二叉树 RR旋转
     * @param node
     * @return
     */
    private AvlNode<T> rotateWitRight(AvlNode<T> node) {
        AvlNode<T> right=node.right;
        node.right=right.left;
        right.left=node;
        node.height=Math.max(getHeight(node.left),getHeight(node.right))+1;
        right.height=Math.max(getHeight(right.right),node.height)+1;
        return right;
    }
    /**
     * 平衡二叉树 LR旋转
     * @param node
     * @return
     */
    private AvlNode<T> rotateWithLeftRight(AvlNode<T> node) {
        node.left=rotateWitRight(node.left);
        return rotateWithLeft(node);
    }

    /**
     * 平衡二叉树 LL旋转
     * @param node
     * @return
     */
    private AvlNode<T> rotateWithLeft(AvlNode<T> node) {
        AvlNode<T> left=node.left;
        node.left=left.right;
        left.right=node;
        node.height=Math.max(getHeight(node.left),getHeight(node.right))+1;
        left.height=Math.max(getHeight(left.left),node.height)+1;
        return left;
    }
    public AvlNode<T> remove(T t,AvlNode<T> node){
        if (node==null){
            return node;
        }
        int result=t.compareTo(node.t);
        if (result<0){
            node.left=remove(t,node.left);
        }else if (result>0){
            node.right=remove(t,node.right);
        }else if(node.left!=null&&node.right!=null){
           node.t=findMin(node.right).t;
           node.right=remove(node.t,node.right);
        }else {
            node=node.left==null?node.left:node.right;
        }
        return balance(node);
    }

    private AvlNode<T> findMin(AvlNode node) {
        if (node==null){
            return node;
        }
        while(node.left!=null){
            node=node.left;
        }
        return node;
    }
    public static void main(String args[]){
        AVLTree<Integer> avlTree=new AVLTree<>();

        avlTree.insert(3);
        avlTree.insert(2);
        avlTree.insert(1);
        avlTree.insert(4);
        avlTree.insert(5);
        avlTree.insert(6);
        avlTree.insert(7);
        avlTree.insert(16);
        avlTree.insert(15);
        avlTree.insert(14);
        avlTree.insert(13);
        avlTree.insert(12);
        avlTree.insert(11);
        avlTree.insert(10);
        avlTree.insert(8);
        avlTree.insert(9);
        System.out.println(avlTree);
    }

}