栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

java数据结构-跳表-栈-二叉树

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

java数据结构-跳表-栈-二叉树

文章目录
    • 跳表
    • 栈stack
      • 概述
      • stack如何扩容
    • 二叉树
      • 概念
      • B-tree
      • B+tree

跳表

跳表是一种用空间换时间思想的数据结构,它会随机地将一些节点提升到更高的层次,以创建一种逐层的数据结果,以提高操作的速度
https://blog.csdn.net/guangcigeyun/article/details/8278349
参考还没有来得及整理。

栈stack 概述

stack是栈,是一个重要的数据结构,具有先进先出的特点;
public class stack< E > extends Vector< E > 继承自Vector队列;

常用方法

方法说明
stack()创建一个空堆栈
boolean empty()测试此堆栈是否为空
E peek()查看此堆栈顶部的对象,而不从堆栈中删除它
E pop()删除此堆栈顶部的对象,并将该对象作为此函数的值返回
E push( E item)将元素推送到此堆栈的顶部
int search(object o)返回一个对象在此堆栈上的基于1的位置
stack如何扩容

栈构造方法只有一个,且stack继承自Vector,父类默认容量是10,它扩容的是push方法实现的;
Stack直接调用了Vector类的addElement(E item)方法;

二叉树 概念
  • 二叉树
    每个节点至多只有二棵子树,左子树和右子树,次序不能颠倒。

  • 逻辑上分类
    空二叉树、只有一个根结点的二叉树、只有左子树、只有右子树、完全二叉树(特例:满二叉树)。

  • 遍历二叉树
    按一定的规则和顺序走遍二叉树的所有结点,使每一个结点都被访问一次,而且只被访问一次,有前序、中序、后序遍历。

  • 二叉查找树(二叉搜索树)
    为了解决数据库索引排好序的原则。提出。
    在满足二叉树的条件下,左子树的节点值总是小于根的节点值,右子树的节点值总是大于根的节点值,也就是左子树节点值 < 根的节点值 < 右子树节点值。
    但是二叉查找树构建可能极不平衡,最后构建成了一个链表。

  • 平衡二叉树(AVL树)
    为了解决二叉查找树构建极不平衡的情况。提出。
    符合二叉查找树的定义,其次必须满足任何节点的两个子树的高度之差的绝对值不超过 1。
    当数据量过多时,二叉树高度会越来越高,1000个数据有9-10层,那么可能找一个数据需要9-10次IO。
    就会出现平衡二叉树高度过高导致的IO问题。提出B-tree 和 B+tree

  • B-tree
    每个节点上多放一些元素,减少磁盘IO。
    多路搜索树;

  • B+tree
    是B-tree树的变体,是一种多路搜索树;

B-tree

介绍根节点分支节点
除根节点、叶子节点
叶子节点
最多儿子节点数节点数最多只有M个儿子,且M>2节点数最多只有M个儿子,且M>2–
儿子节点数[2,M][M/2,M]
关键字数至少M/2-1(向上取整)
最多 M-1个
至少M/2-1(向上取整)
最多 M-1个
至少M/2-1(向上取整)
最多 M-1个
关键字个数 = 指向儿子节点的指针个数-1关键字个数 = 指向儿子节点的指针个数-1–
关键字 k[1],k[2],…,k[M-1],且k[i]关键字 k[1],k[2],…,k[M-1],且k[i]–
指针指针p[1],p[2]…p[M];p[1] 指向关键字小于k[1]的子树;
p[M] 指向关键字小于k[M]的子树;
p[i] 指向关键字属于(k[i-1],k[i])的子树
位置最顶端中间部分位于同一层且最低层
节点内容
关键字 = 就是MySQL中数据表的索引
指针、关键字、数据指针、关键字、数据关键字、数据

  • 特性:
    关键字集合分布在整颗树中;
    任何一个关键字只能出现在一个结点中;
    搜索有可能在非叶子结点结束;
    搜索性能等价于在关键字全集内做一次二分查找;
    自动层次控制:
    由于限制了除根结点以外的非叶子结点,至少含有M/2个儿子,确保了结点的至少利用率,其最底搜索性能为:O(logN);
B+tree

图示:

说明根节点分支节点
除根节点、叶子节点
叶子节点
儿子数有M个儿子则有m个元素有M个儿子则有m个元素–
存储内容关键字(索引)、指针关键字(索引)、指针关键字、数据
存储––所有根节点、分支节点都存在于子节点中,是最大值或最小值
––包含所有关键字、指向数据记录的指针
叶子节点本身是根据关键字从小到大顺序链接的

作用:
优势= 更加高效的单元素查找。

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/986588.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号