数据结构图例

2、散列冲突怎么解决？

3.提取编码

next

hash算法比如（%7）

push 压栈

55

0

1

2

3

4

999

33

栈底元素

data

35

双向链表

7

SPFA

30

5

rightchild E

E

15

13

11

叔叔节点

element

LR

17

左旋

删掉下标3的数据(ArrayList源码分析)

一起送走

第五加入的

自身有地址，无数据

底部

head

红黑树的5中特性是什么?    1、任何一个节点到其叶子节点的路径上黑色节点一定要相同~！    2、所有叶子（空节点）都是黑色的！    3、根节点一定是黑色！    4、两个红色节点不能是父子关系！    5、只有两种颜色，因为属性是用boolean定义的！左旋右旋变色的条件是什么?span style=\"font-size: inherit;\

10

左旋第一步

2^31=21亿

78

E1

22

1、root节点为树的根节点，通过遍历的方式，查询下方节点，属于入口节点2、left child A是root节点的左儿子节点；3、left child A与mid child B 和 right child C是兄弟节点，对于left child D来说，是它的叔叔节点！4、通常，我们把root顶点成为node根节点5、n一般表示节点数量，h表示节点高度；

18

B+树

树高（层高3层）

68

问题1:二叉树有什么特点?问题2:与链表有什么区别和共性?

下标:    0             1            2            3             4            5             6           7

略

数组

。。。

单向链表

顶部

RR

二叉树特性：       节点数不能超过2个！       隐含有序！       满二叉树: n=2^(h+1)- 1    h表示树高度，只有根节点h为0；没有根节点，h为-1！切记！

59

下标:    0             1            2            3             4            5             6

插入节点

99

16

26

parent

最先加入的

nil12的左儿子

........

12

9

nil叶子节点(12的右儿子null)

left child A

变换后

栈顶指针

int默认为0

双端队列(deque)

LR右旋第一步

50

加载因子（负载因子）

最坏情况二叉树

栈底指针

leftchild D

prev

last

10的右nil

赋值

第四加入的

指向地址

HashMap的内部类

E3

普通树

同左省略

38

如果还有一起送走

第二加入的

20

right child C

LL右旋第一步

4：1出队，进行松弛，此时有有4，修改数组并将?入队4:  队列{1}->{1}

58

初始队列：{0}

假设有六个字母出现的频率如下：A27、B 8、C 15、D 15、E 30、F 5

19

package com.woniuxy.tree;/** *  自定义二叉查找树 ： 树根 root *  树的底层都是节点Node */public class BinaryTree {       private Node root; // 二叉树树根       public BinaryTree() {}//无参构造函数       private class Node{ //内部类定义node节点            private long data; // 数据域            private Node leftChild; // 当前节点的左子结点            private Node rightChild; // 当前节点的右子结点            public  Node(long data) { this.data = data; }//有参node类的构造函数            @Override            public String toString() {return String.valueOf(data);}//重写toString的方法       } }

8

......

二叉树

....

指向磁盘地址

同左

地址(假设):0x88

同理根节点变为黑色

27

23

链表

E2

栈stack

LL

根节点条件

第二步:执行RR进行左旋

叶子节点（无孩子的节点）

-1

头哨兵节点

53

LL右旋第二步

B

mysql----MyISAM的特性:      非聚集索引。由（.MYI）文件存储下标和对应下标数据磁盘地址，而数据库数据存在（.MYD）文件中!

root

特性：    （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；     （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；     （3）左、右子树也分别为二叉排序树；       

D

C

根节点

6

F

指向下一个地址

peek查看

34

它的特性是什么?

32

66

如何判断栈为空?

变换根节点

aa

B+tree---MyISAM

1.生成赫夫曼树

尾哨兵节点

因为只是为了演示左右旋，暂时不满足红黑树的条件

head头节点

初始

28

childen(1)

1、线性探测方法2、二次探测方法3、双重散列方法4、链表法

散列表

next指针

123

44

E5

结合了栈和队列的特性!

pop弹栈

poll / remove出队

first

数据库行数据

mysql----InnoDB的特性:      聚集(聚簇)索引。由（.IBD）文件存储下标和对应下标数据库字段数据!

RL

队列queue

............

A

InnoDB

hash算法比如（%2）

在下标3的位子插入4(ArrayList指定下标插入也是一样)

42

如果是Integer数组呢?

fa

右旋

二叉树基本属性定义

1、散列冲突

二叉查找树（二叉排序树，二叉搜索树）

算法（了解即可）-----赫夫曼树(最优二叉树)与SPFA

24

E4

myh

2.左子树置0，右子树置1

最后赋值:arr[3]=4;

56

LinkedList的内部类

有值

地址(假设):0x01

汉诺塔

B-tree

midchild B

       在B-Tree中按key检索数据的算法非常直观：首先从根节点进行二分查找，如果找到则返回对应节点的data，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或找到null指针，前者查找成功，后者查找失败!

只有栈顶元素是可以访问的

遍历方式：       先序遍历（先根遍历）：                     优先遍历根节点，再遍历左分支（如果左分支还设有左分支，则继续往下遍历直到底层，遍历方式依旧是先根后左），最后遍历右分支；左图先序遍历结果：19 12 1 17 27 23 38       中序遍历（中根遍历）：                     优先遍历左分支，再遍历根，最后遍历右分支（道理同上），请自行输出结果：       后序遍历（后根遍历）：                     优先遍历左分支，再遍历右分支，最后遍历根节点（道理同上），请自行输出结果：

下列代码的问题点:      为什么没有头哨兵节点??因为HashMap的代码中是不需要的?为什么呢?      为什么没有尾哨兵节点呢?binCount在HashMap中的putVal方法中用来干嘛?       treeifyBin这个又是什么?什么时候是扩容(扩容的时候会发生什么)?

.......

无值

最后赋值:elementData[--size] = null; // clear to let GC do its work

add / offer入队

区别：这两个链表最大的不同就是头结点是否是哑元，以及取出元素（get函数）的时候for循环变量i的不同；双向循环链表（和java.util包的设计一样）：由于head是哑元，因此取元素从head的下一个结点取单向链表：head不是哑元，第一次必须取head头结点的元素，因此循环上和双向循环链表不同。也就是第一次get并没有进入for循环，直接返回了头结点，从第二次才开始进入for循环，这里要特别注意

树

vex

第三加入的

字母

编码

01

1001

101

00

1000

这个是红黑树么?

开放寻址法：