有序表

1. 对应c++的map,java是TreeMap

2. key是有序的,时间复杂度为logN

3. 红黑树,sb树,avl树的底层实现结构:基于搜索二叉树的增删改查实现,只是在添加节点后有不同版本的调整。调整方式为左旋或右旋。

avl树(通过高度)

任何一个节点左树和右树的高度差不超过1(平衡性)

增加节点调整平衡的类型:

1.LL型:左边比右边长,通过右旋调整为平衡

2.RR型:右边比左边长,通过左旋调整为平衡

3.LR型:左树的右链过长,对右链的头的右节点和右链进行左旋,在对整个树右旋。

4.RL型:右树的左链过长,对左链的头的左节点和左链进行右旋,在对整个树左旋。

sb树(通过侄子节点个数不大于叔叔节点个数)

添加节点调整平衡的类型:

1.LL型:左孩子的左孩子大于右孩子的大小。

2.LR型:左孩子的右孩子大于右孩子的大小。

3.RL型:右孩子的左孩子大于左孩子的大小。

4.RR型:右孩子的右孩子大于左孩子的大小。