数据结构 玩转数据结构 7-3 集合类的复杂度分析

标签：node Node null return 复杂度 玩转 date 数据结构 public

0　　　　课程地址

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

 

1　　　　重点关注

1.1　　　　结论

使用二叉树实现集合Set性能优于使用链表实现集合Set.

 

1.2　　　　链表和二叉树实现 集合类复杂度分析

• 链表的时间复杂度为O(n),n为元素个数，

包含元素，contains方法时间复杂度为O(n),

增加元素，要首先用contains方法判断链表中是否有该元素，contains方法时间复杂度为O(n),

删除元素，while循环判断元素是否存在，存在则删除，所以复杂度也为O(n)

 

• 二叉树的时间复杂度为O(h),h为二叉树深度

包含元素，contains方法时间复杂度为O(h),每次基本上能过滤一半元素，时间复杂度为O(h),

增加元素，add方法递归调用，每次基本上能过滤一半元素，时间复杂度为O(h),

删除元素，每次基本上能过滤一半元素，时间复杂度为O(h),

 

• h和n的关系

满二叉树的情况，推导见1.3

n=2^h-1;

h = log2(n)

 

• 如果二叉树按照顺序排列，复杂度和链表复杂度一样，如何解决这种情况

使用平衡二叉树

 

1.3　　　　h和n的关系推导

 

 

 

 

 

 

 

 

 

2　　　　课程内容

 

3　　　　Coding

3.1　　　　链表和二叉树实现集合的性能测试

• 需求

分别使用链表和二叉树 实现的集合统计 傲慢与偏见 的英文词汇量,比较二者性能差异

 

• 结论：

二叉树性能要优于链表

 

• 链表类

package com.company;

/***
 * 链表
 * @author weidoudou
 * @date 2022/10/28 7:56
 **/
public class LinkedList<E> {

    /**
     * 1  内部类node
     * @author weidoudou
     * @date 2022/10/28 7:59
     * @return null
     **/
    private class Node{
        //Node 只有两个属性，下一个节点和本节点存储的元素
        private E e;
        private Node next;

        /**
         * 通用调用node方法
         * @author weidoudou
         * @date 2022/10/28 8:17
         * @param e 请添加参数描述
         * @param  next 请添加参数描述
         * @return null
         **/
        public Node(E e,Node next){
            this.e = e;
            this.next = next;
        }

        /**
         * node 无参构造
         * @author weidoudou
         * @date 2022/10/28 8:15
         * @return null
         **/
        public Node(){
            this(null,null);
        }

        /**
         * node 有参构造
         * @author weidoudou
         * @date 2022/10/28 8:16
         * @param e 请添加参数描述
         * @return null
         **/
        public Node(E e){
            this(e,null);
        }


        @Override
        public String toString() {
            return e.toString();
        }
    }

    //2 LinkedList 属性 链表头元素（火车头），大小
    private int size;
    private Node dummyHead;

    /**
     * 3    LikedList 无参
     * @author weidoudou
     * @date 2022/10/28 8:27
     * @return null
     **/
    public LinkedList() {
        this.dummyHead = new Node(null,null);
        this.size = 0;
    }

    /**
     * 4  getSize
     * @author weidoudou
     * @date 2022/10/28 8:23
     * @return null
     **/
    public int getSize(){
        return size;
    }

    /**
     * 5  isEmpyt
     * @author weidoudou
     * @date 2022/10/28 8:24
     * @return boolean
     **/
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 6  链表头部添加元素
     * @author weidoudou
     * @date 2022/10/28 8:37
     * @param e 请添加参数描述
     * @return void
     **/
    public void addFirst(E e){
        /*Node nodeNew = new Node(e);
        nodeNew.next = head;    //火车尾指向 上个尾巴
        this.head = nodeNew;    //火车尾 变成了当前的node*/

        //称之为优雅写法
        addElement(0,e);
    }

    /**
     * 7  链表尾部添加元素 认真分析下
     * @author weidoudou
     * @date 2022/10/28 18:11
     * @param e 请添加参数描述
     * @return void
     **/
    public void addLast(E e){
        addElement(size,e);
    }

    /**
     * 8  链表添加元素(链表通常不在中间添加元素，编写此段代码完全是为了后续便于理解和二叉树相关知识做铺垫)
     * @author weidoudou
     * @date 2022/10/28 8:45
     * @param index 请添加参数描述
     * @param  e 请添加参数描述
     * @return void
     **/
    public void addElement(int index,E e){
        if(index<0||index>size){
            throw new IllegalArgumentException("索引不正确");
        }


        Node pre = dummyHead;
        for(int i = 0;i<index;i++){
            pre = pre.next;
        }

        /*Node nodeNew = new Node(e);
        nodeNew.next = pre.next;
        pre.next = nodeNew;*/

        //优雅写法
        pre.next = new Node(e,pre.next);
        size++;
    }

    /**
     * 9    查询
     * @author weidoudou
     * @date 2022/10/29 11:18
     * @param index 请添加参数描述
     * @return E
     **/
    public E findByIndex(int index){
        if(index<0||index>size-1){
            throw new IllegalArgumentException("索引越界");
        }

        Node cur = dummyHead.next;
        for(int i = 0;i<index;i++){
            cur = cur.next;
        }
        return cur.e;
    }

    /**
     * A     查询首个元素
     * @author weidoudou
     * @date 2022/10/29 11:27
     * @return E
     **/
    public E findByFirst(){
        return findByIndex(0);
    }

    /**
     * B     查询最后一个元素
     * @author weidoudou
     * @date 2022/10/29 11:27
     * @return E
     **/
    public E findByLast(){
        return findByIndex(size-1);
    }

    /**
     * C     修改
     * @author weidoudou
     * @date 2022/10/29 11:29
     * @param index 请添加参数描述
     * @param  e 请添加参数描述
     * @return void
     **/
    public void update(int index,E e){
        if(index<0||index>size-1){
            throw new IllegalArgumentException("索引越界");
        }

        Node cur = dummyHead.next;
        for(int i = 0;i<index;i++){
            cur = cur.next;
        }
        cur.e = e;

    }

    /**
     * D     修改第一个元素
     * @author weidoudou
     * @date 2022/10/29 11:31
     * @param e 请添加参数描述
     * @return void
     **/
    public void updateFirst(E e){
        update(0,e);
    }

    /**
     * E    修改最后一个元素
     * @author weidoudou
     * @date 2022/10/29 11:31
     * @param e 请添加参数描述
     * @return void
     **/
    public void updateLast(E e){
        update(size-1,e);
    }

    /**
     * F     查询链表是否包含元素
     * @author weidoudou
     * @date 2022/10/29 13:04
     * @param e 请添加参数描述
     * @return boolean
     **/
    public boolean contains(E e){
        boolean flag;

        for(Node cur = dummyHead.next;cur!=null;cur=cur.next){
            if(e.equals(cur.e)){
                return true;
            }
        }
        return false;
    }

    /**
     * G      toString
     * @author weidoudou
     * @date 2022/10/29 13:06
     * @return java.lang.String
     **/
    @Override
    public String toString() {

        StringBuilder sb = new StringBuilder();
        for(Node cur = dummyHead.next;cur!=null;cur=cur.next){
            sb.append(cur+"->");
        }
        sb.append("Null");
        return sb.toString();
    }

    /**
     * H        删除索引为index的元素
     * @author weidoudou
     * @date 2022/10/29 19:40
     * @param index 请添加参数描述
     * @return E
     **/
    public E remove(int index){
        if(index<0||index>size-1){
            throw new IllegalArgumentException("索引越界");
        }

        Node pre = dummyHead;
        for(int i = 0;i<index;i++){
            pre = pre.next;
        }

        Node ret = pre.next;
        pre.next = ret.next;
        ret.next = null;
        size--;

        return ret.e;
    }

    /**
     * 删除第一个元素
     * @author weidoudou
     * @date 2022/10/30 14:56
     * @return E
     **/
    public E removFirst(){
        return remove(0);
    }

    /**
     * 删除最后一个元素
     * @author weidoudou
     * @date 2022/10/30 14:56
     * @return E
     **/
    public  E removLast(){
        return remove(size-1);
    }


    // 从链表中删除元素e
    public void removeElement(E e){

        Node prev = dummyHead;
        while(prev.next != null){
            if(prev.next.e.equals(e))
                break;
            prev = prev.next;
        }

        if(prev.next != null){
            Node delNode = prev.next;
            prev.next = delNode.next;
            delNode.next = null;
            size --;
        }
    }

}

 

• 二叉树类

package com.company;

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

public class BST<E extends Comparable> {

    //1     内部类
    private class Node{
        //二叉树特有属性
        private Node left,right;
        private E e;
        private Node(E e){
            this.e = e;
            this.left = null;
            this.right = null;
        }
    }

    private int size;
    private Node root;

    public BST(){
        this.size = 0;
        this.root = null;
    }

    /**
     * 定义基本方法 getSize
     * @author weidoudou
     * @date 2022/11/3 12:57
     * @return int
     **/
    public int getSize(){
        return size;
    }

    /**
     *查询是否为空
     * @author weidoudou
     * @date 2022/11/3 12:58
     * @return boolean
     **/
    public boolean isEmpty(){
        return size == 0;
    }

    //2     循环添加元素,把null也看作节点
    public void add(E e){
        root = add(e,root);
    }

    //3     递归，添加元素
    public Node add(E e,Node root){
        //3.1   终止条件
        if(root==null){
            size++;
            return new Node(e);
        }

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

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

        //点睛之笔
        return root;
    }

    /**
     * 二分搜索树 是否包含元素e
     * @author weidoudou
     * @date 2022/11/4 9:55
     * @param e 请添加参数描述
     * @return boolean
     **/
    public boolean contains(E e){
        return contains(e,root);
    }

    /**
     * 二分搜索树查询 递归
     * @author weidoudou
     * @date 2022/11/4 9:57
     * @param e 请添加参数描述
     * @param  node 请添加参数描述
     * @return boolean
     **/
    private boolean contains(E e,Node node){
        //终止条件
        if(node == null){
            return false;
        }
        if(e.compareTo(node.e)==0){
            return true;
        }

        //递归条件
        if(e.compareTo(node.e)<0){
            return contains(e,node.left);
        }else{
            return contains(e,node.right);
        }

    }

    /**
     * 4     二分搜索树，前序遍历 顾名思义，先遍历根节点，再遍历左节点，最后遍历右节点
     * @author weidoudou
     * @date 2022/11/5 14:54
     * @return null
     **/
    public boolean preOrder(){
        preOrder(root);
        return false;
    }

    //前序遍历 递归
    private void preOrder(Node node){
        //终止条件
        if(node==null){
            return;
        }

        //递归
        System.out.println(node.e);//1
        preOrder(node.left);
        preOrder(node.right);
    }

    /**
     *  前序遍历非递归写法 用栈的方法实现 while 代替递归
     * @author weidoudou
     * @date 2022/11/8 9:57
     *
     * @return*/
    public boolean preOrderNR(){
        Stack<Node> stack = new Stack<>();
        stack.push(root);

        while(!stack.isEmpty()){
            Node cur = stack.peek();
            stack.pop();
            System.out.println(cur.e);
            if(cur.right!=null){
                stack.push(cur.right);
            }

            if(cur.left!=null){
                stack.push(cur.left);
            }
        }
        return false;
    }

    /**
     * 二分搜索树广度遍历
     * @author weidoudou
     * @date 2022/11/8 11:23
     * @return boolean
     **/
    public boolean levelOrder(){
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        while (queue.peek()!=null){
            Node cur = queue.peek();
            System.out.println(cur.e);
            queue.remove();
            if(cur.left!=null){
                queue.add(cur.left);
            }
            if(cur.right!=null){
                queue.add(cur.right);
            }
        }
        return false;
    }


    /**
     * 5     二分搜索树，中序遍历 顾名思义，先遍历左节点，再遍历根节点，最后遍历右节点
     * @author weidoudou
     * @date 2022/11/5 14:54
     * @return null
     **/
    public boolean inOrder(){
        inOrder(root);
        return false;
    }

    //前序遍历 递归
    private void inOrder(Node node){
        //终止条件
        if(node==null){
            return;
        }

        //递归
        inOrder(node.left);
        System.out.println(node.e);//1
        inOrder(node.right);
    }

    /**
     * 6     二分搜索树，后序遍历 顾名思义，先遍历左节点，再遍历右节点，最后遍历根节点
     * @author weidoudou
     * @date 2022/11/5 14:54
     * @return null
     **/
    public boolean postOrder(){
        postOrder(root);
        return false;
    }

    //前序遍历 递归
    private void postOrder(Node node){
        //终止条件
        if(node==null){
            return;
        }

        //递归
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.e);//1

    }



    /**
     * 基于前序遍历完成toString打印
     * @author weidoudou
     * @date 2022/11/5 15:20
     * @return java.lang.String
     **/
    @Override
    public String toString() {
        final StringBuffer sb = new StringBuffer();
        generate(root,0);
        return sb.toString();
    }

    private void generate(Node node, int depth){
        generate(depth);
        //1     终止条件
        if(node==null){
            System.out.println("null");
            return;
        }

        //2     递归条件
        System.out.println(node.e);
        depth++;
        generate(node.left,depth);
        generate(node.right,depth);
    }

    private void generate(int depth){
        for(int i = 0;i<depth;i++){
            System.out.print("==");
        }
    }

    /**
     * 7.1    查询最小的元素
     * @author weidoudou
     * @date 2022/11/8 14:30
     * @return E
     **/
    public E findMin(){
        if(size==0){
            throw new IllegalArgumentException("二叉树为空，无最小元素");
        }
        return findMin(root).e;
    }

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

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

    /**
     * 7.2      查询最大的元素
     * @author weidoudou
     * @date 2022/11/8 14:30
     * @return E
     **/
    public E findMax(){
        if(size==0){
            throw new IllegalArgumentException("二叉树为空，无最大元素");
        }
        return findMax(root);
    }

    private E findMax(Node node){
        //1     终止条件
        if(node.right==null){
            return node.e;
        }

        //2     递归
        return findMax(node.right);
    }

    /**
     * 7.3      删除最小元素
     * @author weidoudou
     * @date 2022/11/8 15:43
     * @return void
     **/
    public E removMin(){
        E e = findMin();
        //这里好好思考下，为什么要加上root =
        //因为极端情况，最小值为根节点，不加这个的话，导致第一次删除后root不变，详见本节代码草图
        root = removMin(root);
        return e;
    }

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

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

    /**
     * 7.4      删除最大元素
     * @author weidoudou
     * @date 2022/11/8 15:43
     * @return void
     **/
    public E removMax(){
        E e = findMax();
        removMax(root);
        return e;
    }

    private Node removMax(Node node){
        //终止条件
        if(node.right==null){
            Node leftNode = node.left;
            node.left = null;
            size--;
            return leftNode;
        }

        //递归
        node.right = removMax(node.right);
        return node;
    }

    /**
     * 删除任意元素 若删除元素节点下只有一个节点直接接上即可，若有两个节点，则找前驱或后继，本节找前驱
     * @author weidoudou
     * @date 2022/11/18 7:37
     * @return void
     **/
    public void remove(E e){
        remove(root,e);
    }

    private Node remove(Node node,E e){
        //终止条件1
        if(node==null){
            return null;
        }

        //递归
        if(e.compareTo(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;
        }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 = removMax(node.right);//这块一箭双雕，既把后继节点问题解决了，也把后继删除了
                nodeMain.left = node.left;
                node.left = node.right = null;
                return node;
            }
        }
    }


}

 

• Set接口

package com.company;

/**
 *  集合接口
 * @author weidoudou
 * @date 2022/12/14 8:14
 * @return null
 **/
public interface Set<E> {

    /**
     *  是否包含
     * @author weidoudou
     * @date 2022/12/14 8:17
     * @param e 请添加参数描述
     * @return boolean
     **/
    boolean contails(E e);

    /**
     *  是否为空
     * @author weidoudou
     * @date 2022/12/14 8:18
     * @return boolean
     **/
    boolean isEmpty();

    /**
     * 获取个数
     * @author weidoudou
     * @date 2022/12/14 8:19
     * @return int
     **/
    int getSize();

    /**
     * 添加方法
     * @author weidoudou
     * @date 2022/12/14 8:19
     * @param e 请添加参数描述
     * @return void
     **/
    void add(E e);

    /**
     * 删除方法
     * @author weidoudou
     * @date 2022/12/14 8:20
     * @param e 请添加参数描述
     * @return void
     **/
    void remove(E e);

}

 

• LinkedList Set

package com.company;

public class LinkedListSet<E> implements Set<E>{

    private LinkedList<E> linkedList;

    public LinkedListSet(){
        linkedList = new LinkedList<>();
    }

    @Override
    public boolean contails(E e) {
        return linkedList.contains(e);
    }

    @Override
    public boolean isEmpty() {
        return linkedList.isEmpty();
    }

    @Override
    public int getSize() {
        return linkedList.getSize();
    }

    @Override
    public void add(E e) {
        if(!linkedList.contains(e)){
            linkedList.addFirst(e);
        }
    }

    @Override
    public void remove(E e) {
        if(linkedList.contains(e)){
            linkedList.removeElement(e);

        }
    }
}

 

• 二叉树Set

package com.company;

/**
 * 因为集合是只能添加不重复的数据，所以二叉树是实现集合的天然选择
 * @author weidoudou
 * @date 2022/12/14 8:22
 **/
public class BSTSet<E extends Comparable> implements Set<E> {

    private BST<E> bst;

    public BSTSet(){
        bst = new BST<>();
    }

    @Override
    public boolean contails(E e) {
        return bst.contains(e);
    }

    @Override
    public boolean isEmpty() {
        return bst.isEmpty();
    }

    @Override
    public int getSize() {
        return bst.getSize();
    }

    @Override
    public void add(E e) {
        bst.add(e);
    }

    @Override
    public void remove(E e) {
        bst.remove(e);
    }
}

 

• 文件处理类：

package com.company;

import java.io.FileInputStream;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Locale;
import java.io.File;
import java.io.BufferedInputStream;
import java.io.IOException;

// 文件相关操作
public class FileOperation {

    // 读取文件名称为filename中的内容，并将其中包含的所有词语放进words中
    public static boolean readFile(String filename, ArrayList<String> words){

        if (filename == null || words == null){
            System.out.println("filename is null or words is null");
            return false;
        }

        // 文件读取
        Scanner scanner;

        try {
            File file = new File(filename);
            if(file.exists()){
                FileInputStream fis = new FileInputStream(file);
                scanner = new Scanner(new BufferedInputStream(fis), "UTF-8");
                scanner.useLocale(Locale.ENGLISH);
            }
            else
                return false;
        }
        catch(IOException ioe){
            System.out.println("Cannot open " + filename);
            return false;
        }

        // 简单分词
        // 这个分词方式相对简陋, 没有考虑很多文本处理中的特殊问题
        // 在这里只做demo展示用
        if (scanner.hasNextLine()) {

            String contents = scanner.useDelimiter("\\A").next();

            int start = firstCharacterIndex(contents, 0);
            for (int i = start + 1; i <= contents.length(); )
                if (i == contents.length() || !Character.isLetter(contents.charAt(i))) {
                    String word = contents.substring(start, i).toLowerCase();
                    words.add(word);
                    start = firstCharacterIndex(contents, i);
                    i = start + 1;
                } else
                    i++;
        }

        return true;
    }

    // 寻找字符串s中，从start的位置开始的第一个字母字符的位置
    private static int firstCharacterIndex(String s, int start){

        for( int i = start ; i < s.length() ; i ++ )
            if( Character.isLetter(s.charAt(i)) )
                return i;
        return s.length();
    }
}

 

• 测试类：

/**
     * 二叉树集合和链表集合的性能差异
     * @author weidoudou
     * @date 2022/12/19 7:39
     * @param set 请添加参数描述
     * @param  fileName 请添加参数描述
     * @return double
     **/
    public static double getTime(Set set,String fileName){
        long startTime = System.nanoTime();

        ArrayList<String> words1  = new ArrayList<>();
        FileOperation.readFile(fileName,words1);
        System.out.println("Total words:"+words1.size());

        words1.stream().map(e->{
            set.add(e);
            return e;
        }).collect(Collectors.toSet());
        System.out.println("Total different words:"+set.getSize());


        long endTime = System.nanoTime();

        double useTime = (endTime-startTime)/1000000000.0;
        return useTime;
    }

    public static void main(String[] args) {
        String fileName = "pride-and-prejudice.txt";

        Double time1 = getTime(new BSTSet(),fileName);
        System.out.println("Main->getTime->end1->:"+time1);

        Double time2 = getTime(new LinkedListSet(),fileName);
        System.out.println("Main->getTime->end2->:"+time2);

    }

 

• 测试结果：

---- IntelliJ IDEA coverage runner ---- 
sampling ...
include patterns:
exclude patterns:
Total words:125901
Total different words:6530
Main->getTime->end1->:0.1765736
Total words:125901
Total different words:6530
Main->getTime->end2->:2.4274472
Class transformation time: 0.0296374s for 392 classes or 7.560561224489796E-5s per class

Process finished with exit code 0

 

标签：node,Node,null,return,复杂度,玩转,date,数据结构,public
From： https://www.cnblogs.com/1446358788-qq/p/16991403.html