纯净、安全、绿色的下载网站

首页|软件分类|下载排行|最新软件|IT学院

当前位置:首页IT学院IT技术

Java数据结构 详解Java集合中的基本数据结构

Liziba   2021-06-04 我要评论
想了解详解Java集合中的基本数据结构的相关内容吗,Liziba在本文为您仔细讲解Java数据结构的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:Java数据结构,java集合,下面大家一起来学习吧。

集合中三大数据结构

在这里插入图片描述

数组

  • 内存地址连续
  • 可以通过下标的成员访问,下标访问的性能高
  • 增删操作有较大的性能消耗(需要动态扩容)

在这里插入图片描述

链表(双向链表)

  • 灵活的空间要求,存储空间不要求连续
  • 不支持下标访问,支持顺序遍历搜索
  • 针对增删操作找到对应的节点改变链表的头尾指针指向即可,无需移动元数据存储位置

在这里插入图片描述

树(Java中二叉树特性)

  • 某节点的左子树节点仅包含小于该节点的值
  • 某节点的右子树节点仅包含大于该节点的值
  • 节点必须是二叉树
  • 顺序排列

在这里插入图片描述

存在问题:树可以认为是介于数组和链表二者之间的一种数据结构,拥有较快的查询速度同时拥有较快的插入和删除速度。但是在树出现极端或严重的不平衡情况下会导致效率低下

在这里插入图片描述

基于红黑树折中解决二叉树不平衡带来的效率低下问题

红黑树

  • 红黑树,Red-Black Tree [RBT]是一个自平衡(不是绝对平衡)的二叉查找树(BST),树上的每个节点需要遵循下面的规则
  • 每个节点要么是黑色,要么是红色
  • 根节点为黑色
  • 每个叶子节点(NIL)是黑色
  • 不能存在两个连续的红色节点(红色节点的两个子节点必须是黑色)
  • 任一节点到叶子节点的路径包含相同数量的黑节点

在这里插入图片描述

红黑树通过什么自平衡

左旋:以某个节点作为支点(旋转节点),其右子节点变为旋转节点的父节点,右子节点的左节点变为旋转节点的右子节点,左子节点保持不变

在这里插入图片描述

右旋:以某个节点作为支点(旋转节点),其左子节点变为旋转节点的父节点,左子节点的右子节点变为旋转节点的左子节点,右子节点保持不变

在这里插入图片描述

变色:节点的颜色由红色变为黑色或者黑色变为红色

在这里插入图片描述

红黑树插入场景

1、红黑树为空

1.1 插入节点作为根节点并把节点设置为黑色

2、插入节点的父节点为黑节点\

2.1 直接插入

3、插入节点的父节点为红节点

3.1 叔叔节点存在且为红节点

  • 1、P节点和S节点设置为黑色
  • 2、PP节点设置为红色
  • 3、PP设置为当前插入节点
  • 4、再次重复上述步骤

3.2 叔叔节点不存在或者叔叔节点为黑色

3.2.1 P节点是PP节点的左节点

3.2.1.1 插入节点是P节点的左节点

  • 1、P设置为黑色
  • 2、PP节点设置为红色
  • 3、PP节点右旋

3.2.1.2 插入节点是P节点的右节点

  • 1、P节点左旋
  • 2、把P设置为插入节点(此时等于上面的场景)
  • 3、PP节点右旋

3.2.2 P节点是PP节点的右节点

3.2.2.1 插入节点是P节点的右节点

  • 1、P节点设置为黑色
  • 2、PP节点设置为红色
  • 3、PP节点左旋

3.2.2.2 插入节点是P节点的左节点

  • 1、P节点右旋
  • 2、将P设置为插入节点(此时等于上面场景)
  • 3、PP节点左旋

PP节点左旋

3.2.2.2 插入节点是P节点的左节点

  • ​ 1、P节点右旋
  • ​ 2、将P设置为插入节点(此时等于上面场景)
  • ​ 3、PP节点左旋

在这里插入图片描述


相关文章

猜您喜欢

  • mybatis plus雪花算法原理 mybatis-plus雪花算法自动生成机器id原理及源码

    想了解mybatis-plus雪花算法自动生成机器id原理及源码的相关内容吗,叁滴水在本文为您仔细讲解mybatis plus雪花算法原理的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:mybatis,plus雪花id,mybatis,plus自动生成机器id,mybatis,plus雪花算法原理,下面大家一起来学习吧。..
  • SpringBoot的配置原理 java进阶之了解SpringBoot的配置原理

    想了解java进阶之了解SpringBoot的配置原理的相关内容吗,梦里一明月在本文为您仔细讲解SpringBoot的配置原理的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:SpringBoot的配置原理,java,SpringBoot,下面大家一起来学习吧。..

网友评论

Copyright 2020 www.moon-script.com 【月光下载】 版权所有 软件发布

声明:所有软件和文章来自软件开发商或者作者 如有异议 请与本站联系 点此查看联系方式