- 跳表
- 栈stack
- 概述
- stack如何扩容
- 二叉树
- 概念
- B-tree
- B+tree
跳表是一种用空间换时间思想的数据结构,它会随机地将一些节点提升到更高的层次,以创建一种逐层的数据结果,以提高操作的速度
https://blog.csdn.net/guangcigeyun/article/details/8278349
参考还没有来得及整理。
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继承自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树的变体,是一种多路搜索树;
| 介绍 | 根节点 | 分支节点 除根节点、叶子节点 | 叶子节点 |
|---|---|---|---|
| 最多儿子节点数 | 节点数最多只有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);
图示:
| 说明 | 根节点 | 分支节点 除根节点、叶子节点 | 叶子节点 |
|---|---|---|---|
| 儿子数 | 有M个儿子则有m个元素 | 有M个儿子则有m个元素 | – |
| 存储内容 | 关键字(索引)、指针 | 关键字(索引)、指针 | 关键字、数据 |
| 存储 | – | – | 所有根节点、分支节点都存在于子节点中,是最大值或最小值 |
| – | – | 包含所有关键字、指向数据记录的指针 叶子节点本身是根据关键字从小到大顺序链接的 |
作用:
优势= 更加高效的单元素查找。



