#import "../template.typ": *
#pagebreak()
= 有序表
所有的操作都是log(n) 红黑树,AVL树,SB树,跳表(skiplist)都可以实现有序表
上面所有结构实现的时间复杂度没有区别.知识原理不同,常数时间有区别.
通常用SB树(好改.)

> 跳表不是一个系列的,其他三个都属于平衡搜索二叉树系列.

== 搜索二叉树
若有重复节点,例如5,5.则可以使用5*2 例如5,a;5,b.则可以使用5,{a,b}
重复节点不影响复杂度.

删除: 没有孩子,直接删 左右孩子不全,也简单,让唯一的节点替代.
都有的话,左树的最右,或者右树上最左.替代的节点的子树直接接到替代节点的父去.

缺点: 没有平衡性,没办法每时每刻都是log(n) 取决于用户的数据.

左右子树高度差不超过1.(严格平衡) 这里平衡是指左右子树高度差不太大.

== AVL树(严格平衡)

(搜索二叉树,左旋,右旋) 带有自平衡操作的搜索二叉树
avl在上面的基础上,增加了如何用左旋和右旋
红黑树,也是同样的基础,但是其有自己平衡性的定义,如何平衡的操作 SB树也是自己定义.

=== 左旋,右旋
头节点倒向哪边就是xx旋

avl树怎么查到自己不平衡的?
增删改查操作与搜索二叉树完全一致,但是加入/删除一个节点后,会往上查是否有平衡性.
删除节点两个孩子都全的时候,从哪儿查起.替换节点的父开始.

=== 四种平衡性被破坏的情况
LL型:左树过长 RR型:右树过长 LR型:左孩子的右孩子过长(把左孩子的右孩子调成头部)
RL型:右孩子的左孩子过长(把右孩子的左孩子调成头部)

红黑树和SB树与avl树增删改查节点全一样,检查时机全一样.
有区别的是,到具体某一个节点的时候,判断的违规条件不一样.
avl维持高度信息,红黑树维持自己的有关平衡二叉树的信息,SB树维持的是节点的大小,即有多少个节点的信息. 

== SB树
平衡性 每棵子树的大小不小于其兄弟的子树大小.
即每棵叔叔树的大小不小于其任何之子树的大小 > 这里的大小是节点的数量

LL型:左树过多 RR型:右树过多 LR型:左孩子的右孩子过多(把左孩子的右孩子调成头部)
RL型:右孩子的左孩子过多(把右孩子的左孩子调成头部)
