03数据结构

树结构之红黑树[不那么平衡的平衡二叉树]红黑树要遵循红黑规则 :1.红黑树中的节点有颜色属性,颜色属性为红或黑2.根节点的颜色一定是黑的3.当红黑树节点没有子节点时,需用叶子节点表示最后节点4.两个红色节点不可以相连5.根节点到其任意最远叶子节点,所经历的简单路径,上黑色节点的数量要相等红黑树节点与二叉树节点属性不同,多一个颜色属性---红黑树结构的特点 :1.元素唯一[红黑树可以去重 : 新老元素相减为零,不加入新元素]2.元素存取无序----新减老 : 升序[左大右小] 老减新 : 降序 [左小右大]3.元素无索引红黑树添加元素的变化规律 :1.新节点的颜色必须是红色,根节点除外红黑树规则的存在和红黑树添加节点规律,会让红黑树元素添加时发生结构变化,从而压缩树的层数提高查找效率哈希表 : hashtable,散列表哈希表的厉害之处 :1.哈希表结构是由数组 链表 红黑树组成2.哈希表结构设计非常的灵活,很多的操作是有程序员来决定哈希表结构的特点 :1.元素唯一 ---去重逻辑程序员决定,新元素.equals老元素2.元素存取无序---元素的哈希值决定元素的存取位置,获取哈希值逻辑程序员决定,元素.hashcode()3.元素无索引哈希表存元素的逻辑1.哈希表结构会在内存创建一个长度为16,加载因子为0.75的数组,作为哈希表的基础容器---加载因子决定扩容的指标,一般是当哈希表中元素的数量达到为 长度 * 加载因子值时,对哈希表底部数组扩容两倍2.去计算元素的哈希值(元素.hash()哈希值获取的函数逻辑由使用哈希表的程序员决定)3.根据元素哈希值,计算此元素应该存放在哈希表底层数组中的哪个索引位置 : 元素哈希值 % 底层数组长度 / 元素哈希值 底层数组长度 - 14.把元素封装到单向链表的节点中,链表节点添加到计算的数组索引位置5.如果索引位置的值是NULL,那么直接添加新元素,如果此索引位置有元素,那么拿新元素依次的和链表上的老元素equals(程序员定)比较6.在新版哈希表中加入了红黑树树化 : 1.底层数组长度64且单个索引位置的链表元素数量8时,会对此位置的链表做树化操作反树化 : 把红黑树变回链表哈希表做扩容时,会改变元素存储索引位置,从而提高哈希表中链表的查询效率哈希表引入红黑树,提高了自己的查找效率,因为树会压缩层数栈结构 : Stackz栈结构的特点 :1.元素无索引2.元素存续,先进后出3.元素可重复4.栈中数据使用完毕立即回收 类似栈内存队列 Queue队列结构的特点 :1.元素无索引2.元素存有序3.元素可重复4.先进先出5.队列中数据使用完毕后立即回收 类似排队算法 : 解决需求的办法[逻辑]时间复杂度 : 算法效率的重要指标时间复杂度O(n) : 计算一段逻辑在指定问题规模下,每句代码执行次数之和空间复杂度 : 算法效率的指标查找算法 : 查找元素的逻辑1.顺序查找 : 一个个的查找int flowSort(int *arr,int element,int length) { if (length 0) { return-1; } for (int i 0; i length; i) { if (arr[i] element) { return i; } return -1; } }二分查找 :从中间开始找,每次数据量减半,但需注意序列有序/** * brief 二分查找法 * 升序二分查找法 * param arr * param length * param element 目标元素 * return int 所在的位置 */ int binarySearch(int* arr,int length,int element) { //定义头和尾变量 int start 0; int end length - 1; //判断是否相等,不等就查找 while (start end) { //定义中间索引位置 int mid (start end) 1; if (element arr[mid]) { start mid 1; } else if(element arr[mid]) { end mid - 1; } else { return mid; } } return -1; }