数据结构和算法之树

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);
    }

}
前缀树🌲
前缀树🌲设计思路

Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较。Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
image.png

前缀树🌲代码实现
type TrieTree struct{
    Son []*TrieTree
    End bool
}
func  NewTrieTree() *TrieTree{
    return &TrieTree{
        Son:make([]*TrieTree,26),
    }
}
func (a *TrieTree) insert(word string){
    node := a
    for i:=0;i<len(word);i++{
        index:=word[i]-'a'
        if node.Son[index]==nil {
            node.Son[index]=NewTrieTree()
        }
        node=node.Son[index]
    }
    node.End=true
}
func (a *TrieTree) search(prefix string)bool{
    node:=a
    for i:=0;i<len(prefix);i++{
        index:=prefix[i]-'a'
        if node.Son[index]==nil{
            return false
        }
        node=node.Son[index]
    }
    return true
}