dede仿手机网站模板,合肥集团网站建设哪个好,建站哪家好用兴田德润,站长之家的作用数据结构概述
数据结构是计算机底层存储、组织数据的方式#xff0c;是指数据相互之间是以什么方式排列在一起的。 通常情况下#xff0c;精心选择的数据结构可以带来更高的运行或者存储效率。
栈
栈数据结构的执行特点#xff1a;后进先出#xff0c;先进后出。
栈模型…数据结构概述
数据结构是计算机底层存储、组织数据的方式是指数据相互之间是以什么方式排列在一起的。 通常情况下精心选择的数据结构可以带来更高的运行或者存储效率。
栈
栈数据结构的执行特点后进先出先进后出。
栈模型 压栈 弹栈 队列
队列执行特点先进先出后进后出
队列模型 数据从后端进入队列模型的过程称为入队列。
数据从前端离开队列模型的过程称为出队列。
数组
元素在内存中是连续存储的。
获取数据速度快元素地址基地址值索引*每个元素的存储大小获取任意数据耗时相同。
删除效率低要将原始数据删除同时后面每个数据前移。
添加效率极低添加位置后的每个数据后移再添加元素。
链表
特点
链表中的元素是在内存中不连续存储的每个元素节点包含数据值和下一个元素的地址。
链表获取数据慢无论获取哪个数据都要从头开始找。 (对比数组
链表增删相对快。(对比数组
结点的存储结构 添加一个链表添加一个数据A再添加c再添加D。 在AC之间添加一个数据 删除C 链表的种类 二叉树
二叉树概述 特点
只能有一个根节点每个节点最多支持2个直接子节点。
节点的度 节点拥有的子树的个数二叉树的度不大于2 叶子节点是度为0的节点也称之为终端结点。
高度叶子结点的高度为1叶子结点的父节点高度为2以此类推根节点的高度最高。
层根节点在第一层以此类推。
兄弟节点 拥有共同父节点的节点互称为兄弟节点。 二叉查找树
二叉查找树又称二叉排序树或者二叉搜索树。 特点
1每一个节点上最多有两个子节点
2左子节点的值小于当前节点的值
3右子节点的值大于当前节点的值
目的提高检索数据的性能。
二叉查找树添加节点
小的存左边大的存右边一样的不存。
平衡二叉树
二叉树查找存在的问题可能出现瘸子现象导致查询的性能与单链表一样查询速度变慢
平衡二叉树是在满足查找二叉树的大小规则下让树尽可能矮小以此提高查数据的性能。
平衡二叉树的要求
任意节点的左右两个子树的高度差不超过1任意节点的左右两个子树都是一颗平衡二叉树。
平衡二叉树在添加元素后可能导致不平衡
基本策略是进行左旋或者右旋保证平衡。
平衡二叉树-旋转的四种情况
左左 当根节点左子树的左子树有节点插入导致二叉树不平衡做一个右旋再移动相关结点。
左右
当根节点左子树的右子树有节点插入导致二叉树不平衡先子树左旋再根树右旋再移动相关结点。
右右
当根节点右子树的右子树有节点插入导致二叉树不平衡做一个左旋再移动相关结点。
右左
当根节点右子树的左子树有节点插入导致二叉树不平衡先子树右旋再根树左旋再移动相关结点。
红黑树
红黑树是一种自平衡的二叉查找树是计算机科学中用到的一种数据结构。
1972年出现当时被称之为平衡二叉B树。1978年被修改为如今的红黑树。
每一个节点可以是红或者黑红黑树不是通过高度平衡的它的平衡是通过“红黑规则”进行实现的。 红黑规则
每一个节点或是红色的或者是黑色的根节点必须是黑色
如果一个节点没有子节点或者父节点则该节点相应的指针属性值为Nil这些Nil视为叶节点每个叶节点(Nil)是黑色的
如果某一个节点是红色那么它的子节点必须是黑色(不能出现两个红色节点相连的情况)
对每一个节点从该节点到其所有后代叶节点的简单路径上均包含相同数目的黑色节点。
结点的存储结构 添加节点
添加的节点的颜色可以是红色的也可以是黑色的。 默认用红色效率高。
红黑树增删改查的性能都很好。
