评论网头条:二分搜索树看这篇就足够了

2020-05-08 4 views 0

扫一扫用手机浏览

二分搜索树(BST):中序遍历效果为递增序列

BST是一种特殊的二叉树,其界说如下:

BST :在二叉树的基础上,随便一个节点知足大于左子树中的所有节点,小于右子树中的所有节点。

注重点:

  • BST的界说中没有等号,后续代码中可以看到,在插入时,相等的元素会被忽略掉。
  • BST的中序遍历效果为递增序列(应用很广),证实:L<node<R;
  • BST是动态数据结构,即容量会自动扩缩(插入,删除)。

插入历程:切记BST的界说,为null时才插入。

private Node add(Node node,E e):向以node为根节点的BST中插入新的元素e,并返回新的根节点。

private Node add(Node node,E e){
    if(node==null){
        return new Node(e);
    }
    if(e.compareTo(node.e)<0){//左边插入。其余稳定
        node.left=add(node.left,e);
    }else if(e.compareTo(node.e)){
        node.right=add(node.right,e);
    }
    //相等,忽略。
    return node;
}
public void add(E e){//从根节点最先找。
    
    root=add(root,e);
}

删除历程(最庞大):切记BST的界说,找到时才删除。

  1. BST的最小值:左子树的终点,纷歧定是叶子节点。
  2. BST的最大值:右子树的终点,纷歧定是叶子节点。
删除最小或者最大节点

最小值位于节点内部时,厥后是一个右子树,此时删除节点后,将剩余子树接到删除节点父节点位置,作为他的左子树。(删除最大值同理)--知足BST性子。

private Node removeMin(Node node)删除已node为根节点的BST的最小节点,并返回删除节点后新的BST的根节点。

public E removeMin(){
    E min=getMin();
    root=removeMin(root);
    return min;
}
private Node removeMin(Node node){
    //found it,左子树的终点
    if(node.left==null){
        Node rightNode=node.right;
        size--;
        return rightNode;
    }
    node.left=removeMin(node.left);
    return node;    
}
    
删除随便元素
  • 删除的节点只有右孩子 :删除当前节点,然后把右子树放置到当前节点的位置,相当于delMin

  • 删除节点只有左孩子:删除当前节点,然后把左子树放置到当前节点的位置,相等于deMax

  • 待删除元素左右孩子都有:找到比待删除节点大的最小节点(BST性子),用这个节点顶替换删除节点的位置。

//删除已node为根的BST中值为e的节点,并返回删除之后新的BST的根。
private Node remove(Node node,E e){
    if(node==null)return null;
    if(e.comapreTo(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;
    }
    //找到待删除元素(e.compareTo(node.e)==0),体会函数执行到这儿的寄义。
    else{
        //待删除节点左子树为null
        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;      
        }
        //双方都不为null。
        Node successor=minimum(node.right);
        sussessor.right=removeMin(node.right);//右边最小的。
        sussessor.left=node.right;
        return sussessor;
        
    }
    
}

public void remove(E e) {
    root = remove(root, e);
}

查找元素:BST性子

private boolean contains(Node node,E e){
    if(node==null) return false;
    if(e.compareTo(node.e)<0){
        return contains(node.left,e);
    }else if(e.compareTo(node.e)>0){
        return contains(node.right,e);
    }else{//先找到,这点和删除的逻辑很像 
        return true;
    }
}
public boolean contains(E e){
    return contains(root,e);
}

BST的完整源码请点击这儿

BST瑕玷:

  • 当插入元素有序时,BST退化为单链表。

AVL树:有序性+平衡性

AVL树在BST的基础上增加了平衡性约束。新增的操作(旋转与高度更新)都是为了知足平衡性约束

AVL树中平衡性的界说:

对于随便一个节点,左子树与右子树的高度差不能超过1

平衡二叉树中平衡的意义:

为了保证树的高度与与节点总数成logN的关系,而一样平常的操作(add,delete,contains)都与树的高度有关,例如,堆是完全二叉树也是平衡二叉树,对堆的种种操作,时间庞大度都是log(N)

插入:关注第一个不平衡的节点,调整原则是有序性+平衡性

插入就是在失败的查找的基础上再操作,插入历程中维持有序性和平衡性的焦点操作:旋转

我们只需要关注第一个不平衡的节点,然后再递归检查就OK,此时,只需要考察该节点与其孩子节点,其孩子的孩子节点(三代)的关系,由于这是导致不平衡的最小单元。

不平衡情形之一:LL

在节点的左孩子的左侧,插入新节点,导致节点失衡,LL,此时通过右旋转来解决,以中央节点为中央,旋转,这样能够同时知足有顺序性和平衡性。

//y:第一个不平衡的节点,返回旋转后的根节点x
private Node rotateRight(Node y ){
    Node x=y.left;
    Node T3=x.right;
    x.right=y;
    y.left=T3;
    //对x和y的位置举行调整,响应的高度也需要更新!!
    y.height=calHeight(y);
    x.height=calHeight(x);
    return x;
}
private Node add(Node node,K key, V va){
    //LL:在node的左侧的左侧添加的节点导致node不平衡。
    if(balance>1&&calBalance(node,left)>=0){//calBalance:left的高度-right高度
 		return rotateRight(node);       
    }
}
不平衡情形之二:RR

在节点的右侧的右侧加入新节点,导致节点失衡,RR,接纳左旋转解决,旋转中央为中央节点x.

sunbet  第1张
//y是第一个失衡的节点,返回旋转后的根节点
private Node rotateLeft(Node y){
    Node x=y.right;
    Node T3=x.left;
    x.left=y;
    y.right=T3;
    //更新高度
    x.height=calHeight(x);
    y.height=calHeight(y);
    return x;   
}
private Node add(Node node, K key,V val){
    //....
    if(balance<-1&&calBalance(node.right)<=0){//balance的界说L-R
        return rotateLeft(node);
    }
}
不平衡情形三:LR

在节点左孩子的右侧加入新节点(LR),导致AVL树失衡,调整方式:先左旋转(LL)后右旋转

sunbet  第2张
private Node add(Node node,K key ,V val){//切记要知足有序性+平衡性
    //....
    if(balance>1&&calBalance(node.left)<0){//以Z为中央。
        node.left=rotateLeft(node.left);
        return rotateRight(node);
    }
    //....
}
不平衡情形三:RL(上一种情形的对称)

在节点右孩子的左侧插入新节点导致树失衡,RL.调整方式:先右旋转(RR)后左选择.

sunbet  第3张
private Node add(Node node,K key ,V val){
    //*...
    if(balance<-1&&calBalance(Node.right)>0){
        node.right=rotateRight(node.right);//z为中央。
        return rotateLeft(node);
    }
    //....
}

删除:在BST(有序)的基础上再加入旋转操作。

BST的删除操作已经保证有序性了,再此基础上还需要思量LL,LR,RR,RL着四种不平衡状态。

public V remove(K key){
    Node node=getNode(root,key);
    if(node!=null){
        root=reomve(root,key);
        return node.val;
    }
    return null;
}
private Node remove(Node node , K key){
//代码与BST的删除逻辑完全一样,只是为了调整平衡性,用retNode来保留删除后的头结点。
    
    return rotateToReBalance(retNode);
}

//判断当前节点是否需要旋转,并执行响应的旋转操作。
private Node rotateToReBalance(Node node){
    if(node==null) return null;
    node.height=calHeight(node);
    int blc=calBalance(node);
    if(blc>1&&calBlanece(node.left)>=0){
        return rotateRight(node);
    }
    if(blc<-1&&calBalance(node.right)<=0){
        return rotateLeft(node);
    }
    if(blc>1&&calBalance(node.left)<0){
        node.left=rotateLeft(node.left);
        return rotateRight(node);
    }
    if(blc<-1&&calBalance(node.right)>0){
        node.right=rotateRight(node.right);
        return rotateLeft(node);
    }
    //不需要维护平衡,
    return node;
}

AVL树的完整源码请点击这儿

AVL树瑕玷

  • 平衡条件过于苛刻。
  • 插入和删除的历程都需要验证平衡性(LL,RR,LR,RL)

基于AVL树的Set和Map。

红黑树:与2-3树是等价的

界说:

  • 每个节点或者为红色、或者为玄色。
  • 根节点为玄色。
  • 每个叶子节点(最后的空节点)是玄色的,即null是玄色的,空树也是红黑树。
  • 若是一个节点是红色的,那么他的孩子节点都是玄色的
  • 从随便一个节点到叶子节点,经由的玄色节点数相同

2-3树,一种特殊的B树,即m=3.

2-3树知足BST的基本性子(有序性),节点可以存放一个元素(二节点),也可以存放两个元素(三节点)。

性子:2-3树是一颗绝对平衡的树。从根节点到随便叶子节点之间具有相同的节点数。

sunbet  第4张
2-3的插入:与最后找到的叶子节点举行融合。

2-3树的插入历程就是不停形成3节点(则原来是2节点)、4节点(有4个分叉,即3个元素)的历程,然后拆分4节点为三个2节点的历程。目的:知足2-3绝对平衡的性子。

sunbet  第5张

2-3树与红黑树的等价性

  • 用单个玄色节点示意2-3树中的2节点
  • 用红节点+父节点(颜色为黑)表示意2-3树的3节点,每个3节点会对应一个红节点,红色节点左倾。
sunbet  第6张

红黑树的插入(与2-3树类比)

当向2节点插入时,带插入位置是左节点,则不调整,是右节点则需要左旋转+颜色翻转,以知足红黑树的界说。

sunbet  第7张

左旋转历程如下

sunbet  第8张
private Node rotateLeft(Node node) {
    // 暂存节点
    Node x = node.right;
    // 左旋转
    node.right = x.left;
    x.left = node;
    // 更新颜色
    x.color = node.color;
    node.color = RED;
    return x;
}
sunbet  第9张
private Node rotateRight(Node node) {
    // 暂存节点
    Node x = node.left;
    Node T1 = x.right;
    // 右旋转
    node.left = T1;
    x.right = node;
    // 颜色更新
    x.color = node.color;
    node.color = RED;
    return x;
}

当向3节点插入时,需要依次经由左旋转,右旋转,颜色翻转等历程。
红黑树的源码请点击这儿

sunbet  第10张

红黑树的统计性能更优

综合增删改查所有的操作,红黑树是平均性能最好的。AVL树的插入和删除过于庞大,查询较多时,AVL树对照合适。通俗的BST对于有序数据就退化为链表。

红黑树更多

  • 舒展树:思量局部性原理的BST。
  • JDK中的TreeMap和TreeSet就是基于红黑树实现的
,

Sunbet

Sunbet www.6358917.com Sunbet(www.sunbet.in)是进入Sunbet的主力站点。Sunbet开放Sunbet会员开户网址、Sunbet代理开户、Sunbet手机版下载、Sunbet电脑客户端下载等业务。

Sunbet内容转载自互联网,如有侵权,联系Sunbet删除。

本文链接地址:http://www.18hao-soso.com/post/1302.html

相关文章