首页 > 其他分享 >数据结构 玩转数据结构 12-6 LR和RL的实现

数据结构 玩转数据结构 12-6 LR和RL的实现

时间:2023-04-16 11:11:32浏览次数:49  
标签:node Node 12 return null right LR key 数据结构

0    课程地址

https://coding.imooc.com/lesson/207.html#mid=14351

 

1    重点关注

1.1    破坏二分搜索树的四种情况

左左LL:新插入的节点导致不平衡,向上回溯找到第一个不平衡的节点在左孩子的左侧      

右右RR:新插入的节点导致不平衡,向上回溯找到第一个不平衡的节点在右孩子的右侧

左右LR:新插入的节点导致不平衡,向上回溯找到第一个不平衡的节点在左孩子的右侧

右左RL:新插入的节点导致不平衡,向上回溯找到第一个不平衡的节点在右孩子的左侧

 

 

1.2    LR解析和RL解析

  • LR

 

  • RL

 

 

1.3    LR和RL的解决

  • LR

左子树先左旋转,形成LL的情况,整棵树再右旋转,实现平衡

 

  • RL

右子树先右旋转,形成RR的情况,整棵树再左旋转,实现平衡


 

2    课程内容

2.1    LR和RL的不平衡情况分析

见1.2

 

2.2    LR和RL的实现平衡的解决思路

见1.3

 

2.3    LR和RL的实现平衡的代码实现

见3.1

 

2.4    实现自平衡的代码和退化成链表的二叉树性能差异测试

见3.1

 

3    Coding

3.1    coding

案例:傲慢与偏见 统计单词

 

  • 关键代码
 //左左情况
        if(balanceFactor>1&&getBalanceFactor(node.left)>=0){
            return rightRotate(node);
            //右右情况
        }else if(balanceFactor<-1&&getBalanceFactor(node.right)<=0){
            return leftRotate(node);
            //左右情况
        }else if(balanceFactor>1&&getBalanceFactor(node.left)<0){
            //先对左子节点左旋转,然后整体右旋转
            node.left = leftRotate(node.left);
            return rightRotate(node);
            //右左情况
        }else if(balanceFactor<-1&&getBalanceFactor(node.right)>0){
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

 

  •  主类AVLTree:
package com.company;

import java.util.ArrayList;
import java.util.List;

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


    //1     定义Node
    class Node{
        private K key;
        private V value;
        private Node left,right;
        private int height;

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

        @Override
        public String toString() {
            final StringBuffer sb = new StringBuffer("Node{");
            sb.append("key=").append(key);
            sb.append(", value=").append(value);
            sb.append('}');
            return sb.toString();
        }
    }

    //2     定义属性
    private int size;
    private Node root;

    /**
     * getHeight
     * @author weidoudou
     * @date 2023/4/1 11:34
     * @param node 请添加参数描述
     * @return int
     **/
    private int getHeight(Node node){
        if(null==node){
            return 0;
        }
        return node.height;
    }

    /**
     * getBalanceFactor
     * @author weidoudou
     * @date 2023/4/1 11:36
     * @param node 请添加参数描述
     * @return int
     **/
    private int getBalanceFactor(Node node){
        if(null==node){
            return 0;
        }
        return getHeight(node.left) - getHeight(node.right);
    }

    /**
     * 无参构造函数
     * @author weidoudou
     * @date 2023/1/1 11:09
     * @return null
     **/
    public AVLTree(){
        this.size = 0;
        this.root = null;
    }



    public boolean isEmpty() {
        return size==0?true:false;
    }

    public int getSize() {
        return size;
    }

    //3     定义包含函数
    private Node containsKey(K key,Node node){
        //结束条件
        if(null==node){
            return null;
        }

        //循环条件
        if(key.compareTo(node.key)<0){
            return containsKey(key,node.left);
        }else if(key.compareTo(node.key)>0){
            return containsKey(key, node.right);
        }else{//key.compareTo(node.key)=0 其实这个也是结束条件
            return node;
        }
    }

    public boolean contains(K key) {
        return containsKey(key,root)==null?false:true;
    }

    public V get(K key) {
        Node node = containsKey(key,root);
        if(null!=node){
            return node.value;
        }
        return null;
    }


    //3     递归,添加元素
    public Node add(K key,V value,Node node){
        //3.1   终止条件
        //3.1.1 要插入的元素和二叉树原有节点相同,这个不用判断,因为已经调了containsKey方法判断了
        if(node==null){
            size++;
            return new Node(key,value);
        }

        //3.1.2 最终插入左孩子
        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{
            node.value = value;
        }

        node.height = 1+Math.max(getHeight(node.left),getHeight(node.right));
        int balanceFactor = getBalanceFactor(node);
        /*if(Math.abs(balanceFactor)>1){
            System.out.println("unbalanced:"+balanceFactor);
        }*/

        //左左情况
        if(balanceFactor>1&&getBalanceFactor(node.left)>=0){
            return rightRotate(node);
            //右右情况
        }else if(balanceFactor<-1&&getBalanceFactor(node.right)<=0){
            return leftRotate(node);
            //左右情况
        }else if(balanceFactor>1&&getBalanceFactor(node.left)<0){
            //先对左子节点左旋转,然后整体右旋转
            node.left = leftRotate(node.left);
            return rightRotate(node);
            //右左情况
        }else if(balanceFactor<-1&&getBalanceFactor(node.right)>0){
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
        return node;
    }



    // 对节点y进行向右旋转操作,返回旋转后新的根节点x
    //        y                              x
    //       / \                           /   \
    //      x   T4     向右旋转 (y)        z     y
    //     / \       - - - - - - - ->    / \   / \
    //    z   T3                       T1  T2 T3 T4
    //   / \
    // T1   T2
    /**
     * 右旋转
     * 1    旋转
     * 2    变更高度
     * @author weidoudou
     * @date 2023/4/14 7:27
     * @param y 请添加参数描述
     * @return com.company.AVLTree<K,V>.Node
     **/
    private Node rightRotate(Node y){
        //1 右旋转
        Node x = y.left;
        Node T3 = x.right;
        x.right = y;
        y.left = T3;

        //2 变更高度
        y.height = Math.max(getHeight(y.left),getHeight(y.right))+1;
        x.height = Math.max(getHeight(x.left),getHeight(x.left))+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;
    }

    public void add(K key, V value) {
        root = add(key,value,root);
        /*Node node = containsKey(key,root);
        //未找到,插值
        if(node==null){
            //2.1   考虑特殊情况,如果是第一次调用,root为null
            if(root==null){
                root = new Node(key,value);
                size++;
            }else{
                //2.2   添加递归方法
                add(key,value,root);
            }
        }else{
            node.value = value;
        }*/
        //找到后,更新值
    }

    public void set(K key, V value) {
        Node node = containsKey(key,root);
        if(node == null){
            throw new IllegalArgumentException("要修改的值不存在");
        }
        node.value = value;
    }

    private Node remove(Node node,K key){
        //终止条件1 基本判断不到,因为已经判断了containskey
        /*if(node==null){
            return null;
        }*/

        //递归
        if(key.compareTo(node.key)<0){
            node.left = remove(node.left,key);
            return node;
        }else if(key.compareTo(node.key)>0){
            node.right = remove(node.right,key);
            return node;
        }else{
            //已找到要删除的元素
            //1 如果只有左子节点或只有右子节点,则直接将子节点替换
            if(node.left==null){
                return node.right;
            }else if(node.right==null){
                return node.left;
            }else{
                //2 如果有左子节点和右子节点,则寻找前驱或后继 对当前节点替换掉
                Node nodeMain = findMin(node.right);
                nodeMain.right = removMin(node.right);//这块一箭双雕,既把后继节点问题解决了,也把后继删除了
                nodeMain.left = node.left;
                node.left = node.right = null;
                return node;
            }
        }
    }

    private Node findMin(Node node){
        //1     终止条件
        if(node.left==null){
            return node;
        }

        //2     递归
        return findMin(node.left);
    }

    private Node removMin(Node node){
        //终止条件
        if(node.left==null){
            Node rightNode = node.right;
            node.right = null;
            return rightNode;
        }

        //递归
        node.left = removMin(node.left);
        return node;
    }

    /**
     * 删除任意元素 若删除元素节点下只有一个节点直接接上即可,若有两个节点,则找前驱或后继,本节找前驱
     * @author weidoudou
     * @date 2023/1/1 11:52
     * @param key 请添加参数描述
     * @return V
     **/
    public V remove(K key) {
        Node node = containsKey(key,root);
        if(node == null){
            throw new IllegalArgumentException("要修改的值不存在");
        }
        size--;
        return remove(root, key).value;
    }

    //1     校验二分搜索树(中序遍历参考之前的中序遍历一节)
    public boolean judgeBST(){
        List<K> list = new ArrayList<>();
        inOrder(root,list);
        for(int i=1;i<list.size();i++){
            if(list.get(i-1).compareTo(list.get(i))>0){
                return false;
            }
        }
        return true;
    }

    private void inOrder(Node node, List<K> list){
        if(node==null){
            return;
        }
        inOrder(node.left,list);
        list.add(node.key);
        inOrder(node.right,list);
    }


    //2     校验平衡二叉树
    public boolean judgeBalance(){
        return judgeBalance(root);
    }

    private boolean judgeBalance(Node node){
        if(node == null){
            return true;
        }
        int balanceFactor = getBalanceFactor(node);
        if(Math.abs(balanceFactor)>1){
            return false;
        }
        return judgeBalance(node.left)&&judgeBalance(node.right);
    }




    public static void main(String[] args) {
        System.out.println("Pride and Prejudice");
        ArrayList<String> words = new ArrayList<>();

        if(FileOperation.readFile("pride-and-prejudice.txt",words)){
            System.out.println("Total words: "+words.size());
            AVLTree<String,Integer> avlTree = new AVLTree<>();
            for(String word:words){
                if(avlTree.contains(word)){
                    avlTree.set(word,avlTree.get(word)+1);
                }else{
                    avlTree.add(word,1);
                }
            }
            System.out.println("Total different words:"+avlTree.getSize());
            System.out.println("judge BST:"+avlTree.judgeBST());
            System.out.println("judge Balance:"+avlTree.judgeBalance());
        }
    }


}

 

  • 对照类BST:
package com.company;

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

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


    //1     定义Node
    class Node{
        private K key;
        private V value;
        private Node left,right;

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

        @Override
        public String toString() {
            final StringBuffer sb = new StringBuffer("Node{");
            sb.append("key=").append(key);
            sb.append(", value=").append(value);
            sb.append('}');
            return sb.toString();
        }
    }

    //2     定义属性
    private int size;
    private Node root;

    /**
     * 无参构造函数
     * @author weidoudou
     * @date 2023/1/1 11:09
     * @return null
     **/
    public BST(){
        this.size = 0;
        this.root = null;
    }

    public boolean isEmpty() {
        return size==0?true:false;
    }

    public int getSize() {
        return size;
    }

    //3     定义包含函数
    private Node containsKey(K key,Node node){
        //结束条件
        if(null==node){
            return null;
        }

        //循环条件
        if(key.compareTo(node.key)<0){
            return containsKey(key,node.left);
        }else if(key.compareTo(node.key)>0){
            return containsKey(key, node.right);
        }else{//key.compareTo(node.key)=0 其实这个也是结束条件
            return node;
        }
    }

    public boolean contains(K key) {
        return containsKey(key,root)==null?false:true;
    }

    public V get(K key) {
        Node node = containsKey(key,root);
        if(null!=node){
            return node.value;
        }
        return null;
    }


    //3     递归,添加元素
    public void add(K key,V value,Node root){
        //3.1   终止条件
        //3.1.1 要插入的元素和二叉树原有节点相同,这个不用判断,因为已经调了containsKey方法判断了
        /*if(key.equals(root.e)){
            return;
        }*/

        //3.1.2 最终插入左孩子
        if(key.compareTo(root.key)<0 && root.left==null){
            root.left = new Node(key,value);
            size++;
            return;
        }

        //3.1.2 最终插入右孩子
        if(key.compareTo(root.key)>0 && root.right == null){
            root.right = new Node(key,value);
            size++;
            return;
        }

        //3.2   递归
        //3.2.1 递归左孩子
        if(key.compareTo(root.key)<0){
            add(key,value,root.left);
        }

        //3.2.2 递归右孩子
        if(key.compareTo(root.key)>0){
            add(key,value,root.right);
        }
    }

    public void add(K key, V value) {
        Node node = containsKey(key,root);
        //未找到,插值
        if(node==null){
            //2.1   考虑特殊情况,如果是第一次调用,root为null
            if(root==null){
                root = new Node(key,value);
                size++;
            }else{
                //2.2   添加递归方法
                add(key,value,root);
            }
        }else{
            node.value = value;
        }
        //找到后,更新值
    }

    public void set(K key, V value) {
        Node node = containsKey(key,root);
        if(node == null){
            throw new IllegalArgumentException("要修改的值不存在");
        }
        node.value = value;
    }

    private Node remove(Node node,K key){
        //终止条件1 基本判断不到,因为已经判断了containskey
        /*if(node==null){
            return null;
        }*/

        //递归
        if(key.compareTo(node.key)<0){
            node.left = remove(node.left,key);
            return node;
        }else if(key.compareTo(node.key)>0){
            node.right = remove(node.right,key);
            return node;
        }else{
            //已找到要删除的元素
            //1 如果只有左子节点或只有右子节点,则直接将子节点替换
            if(node.left==null){
                return node.right;
            }else if(node.right==null){
                return node.left;
            }else{
                //2 如果有左子节点和右子节点,则寻找前驱或后继 对当前节点替换掉
                Node nodeMain = findMin(node.right);
                nodeMain.right = removMin(node.right);//这块一箭双雕,既把后继节点问题解决了,也把后继删除了
                nodeMain.left = node.left;
                node.left = node.right = null;
                return node;
            }
        }
    }

    private Node findMin(Node node){
        //1     终止条件
        if(node.left==null){
            return node;
        }

        //2     递归
        return findMin(node.left);
    }

    private Node removMin(Node node){
        //终止条件
        if(node.left==null){
            Node rightNode = node.right;
            node.right = null;
            return rightNode;
        }

        //递归
        node.left = removMin(node.left);
        return node;
    }

    /**
     * 删除任意元素 若删除元素节点下只有一个节点直接接上即可,若有两个节点,则找前驱或后继,本节找前驱
     * @author weidoudou
     * @date 2023/1/1 11:52
     * @param key 请添加参数描述
     * @return V
     **/
    public V remove(K key) {
        Node node = containsKey(key,root);
        if(node == null){
            throw new IllegalArgumentException("要修改的值不存在");
        }
        size--;
        return remove(root, key).value;
    }


}

 

  • 测试类:
package com.company;

import java.util.ArrayList;
import java.util.Collections;
import java.util.stream.Collectors;

public class Main {


    public static void main(String[] args) {

        //1     先把字数全部放进list
        ArrayList<String> list1 = new ArrayList<>();
        if(FileOperation.readFile("pride-and-prejudice.txt",list1)){
            Collections.sort(list1);
            BST<String,Integer>  bst = new BST();

            //2.1       测试BST
            long startTime1 = System.nanoTime();
            for(int i = 0;i<list1.size();i++){
                if(bst.contains(list1.get(i))){
                    bst.set(list1.get(i),bst.get(list1.get(i))+1);
                }else{
                    bst.add(list1.get(i),1);
                }
            }
            for(String key: list1){
                bst.contains(key);
            }
            long endTime1 = System.nanoTime();
            System.out.println("BST USE TIME ="+(endTime1-startTime1)/100000000.0);


            //2.2   测试AVLTree
            long startTime2 = System.nanoTime();
            AVLTree<String,Integer> avlTree = new AVLTree<>();
            for(int i = 0;i<list1.size();i++){
                if(avlTree.contains(list1.get(i))){
                    avlTree.set(list1.get(i),avlTree.get(list1.get(i))+1);
                }else{
                    avlTree.add(list1.get(i),1);
                }
            }

            for(String key: list1){
                avlTree.contains(key);
            }
            long endTime2 = System.nanoTime();
            System.out.println("AVLTREE USE TIME ="+(endTime2-startTime2)/100000000.0);

        }

    }



}

 

  • 测试结果:
BST USE TIME =103.097125
AVLTREE USE TIME =0.434623

Process finished with exit code 0

 

标签:node,Node,12,return,null,right,LR,key,数据结构
From: https://www.cnblogs.com/1446358788-qq/p/17322694.html

相关文章

  • P1283 平板涂色
    题目传送门一看数据,是可以爆搜的。思路我们看,当要涂一个矩形的时候,他上面的矩形就都要涂掉于是我们就可以自然而然的想到拓扑或者说我们把整个平板抽象成一个有向图,每个矩形就是一个点,他的限制就是边比如样例:就可以抽象成建图就可以暴力建,才100*100的数据然后就在图上......
  • Python之带参装饰器(12)
    一、文档字符串无参装饰器和带参装饰器有什么区别呢?我们先来看文档字符串文档字符串是什么东西呢?文档字符串. ●Python文档字符串DocumentationStrings ●在函数(类、模块)语句块的第一行,且习惯是多行的文本,所以多使用三引号 ●文档字符串也算是合法的一条语句 ●惯例是首字母......
  • 【CVE-2017-12615】Tomcat 远程代码执行漏洞复现
    0x00环境搭建用vulhub的环境查看配置文件conf/web.xml中readonly的设置0x01漏洞复现访问主页,抓包后修改数据包可通过PUT方式创建一个JSP文件。虽然Tomcat对文件后缀有一定检测(不能直接写jsp),但我们使用一些文件系统的特性(如Linux下可用/)来绕过了限制。改完包的时候......
  • 数据结构之哈夫曼树与哈夫曼编码
    一、背景编码是信息处理的基础(重新表示信息)。普通的编码是等长编码,例如7位的ASCIL编码,对出现频率不同的字符都使用相同的编码长度。但其在传输和存储等情况下编码效率不高。可使用不等长编码,来压缩编码:高频字符编码长度更短,低频字符编码长度更长。 [例]将百分制的考试成......
  • kuangbin专题一 简单搜索 石油储备(HDU-1241)
    OilDepositsTimeLimit:2000/1000MS(Java/Others)MemoryLimit:65536/32768K(Java/Others)ProblemDescriptionTheGeoSurvCompgeologicsurveycompanyisresponsiblefordetectingundergroundoildeposits.GeoSurvCompworkswithonelargerectangula......
  • Oracle12C 调整 sga pga 调优记录
    3.2oracle参数调优查询oracle当前参数配置情况(processs=500;sessions=2280)1)以dba身份登录查看sga和pga情况SGA:SystemGlobalArea是OracleInstance的基本组成部分,在实例启动时分配;系统全局域SGA主要由三部分构成:共享池、数据缓冲区、日志缓冲区。SQL>showparametersga;NA......
  • 12 Geometry
    关键点MeshSubdivision(LoopSubdivision,Catmull-ClarkSubdivision)MeshSimplification(EdgeCollapsing)MeshRegularization1.MeshOperarions1.1MeshSubdivision--Upsampling细分细分:把三角形数量增多调整:改变三角形的位置1.1.1LoopSubdivision每个三角形......
  • 类的继承12
    #include<iostream>usingnamespacestd; classDog{public:    voidsetdata()    {        cin>>name>>age>>sex>>weight;    }    voidGetName()    {        cout<<"它的名字叫"<<name<<......
  • 数据结构-->二叉树_02
    今天,接着上一期的博文,继续推进!!请看下面的的代码:>求一棵树的高度,为何需要存储起来呢?解答这个问题之前,需要稍微改动一下,上述的代码!会发现上述代码有很大的好处!//二叉树的高度intTreeHight(BTNode*root){ if(root==NULL){ return0;}returnTreeHight(root->l......
  • 「解题报告」CF1129D Isolation
    水题,但是调了好久qwq显然是DP,出现次数显然分块,那就数据结构优化DP呗。我们可以维护出当前点到每个点这段区间内有多少个出现次数为\(1\)的数,这个右端点每拓展一位修改的左端点一定是连续的区间。分块维护这个东西,如果是散块暴力重构暴力加,如果是整块那给整块打个加标记。......