二叉排序树

1.性质

左子树<根结点<右子树，中序遍历可以得到一个递增的有序序列（左根右）

2.二叉排序树的插入

⭐插入的一定是叶子结点

3.二叉排序树的删除

二叉排序树：左<根<右

先找到要被删除的目标结点z

（1）若目标结点z是叶子结点，直接删除

（2）若目标结点z只有一个左子树或只有一个右子树，则让z的子树替代z的位置

（3）若目标结点z有左、右两个子树，则令z的直接后继（或z的直接前驱）替代z的位置，然后从二叉树中删去这个直接后继（或直接前驱），这样就转化成了第一种或第二种情况。

第一种：z的直接后继替换z的位置，也就是z的右子树的最左下结点

（2）z的直接前驱，也就是z的左子树的最右下结点

4.查找效率 

 要补出失败结点。！！！

---

平衡二叉树

因为二叉排序树可能有树高为n的情况，这种查找效率非常低，所以引入了平衡二叉树。

1.定义

2.平衡二叉树的插入和调整

每次都是调整“最小不平横子树”

⭐也就是从插入点往回找，找到第一个不平横点，调整以它为根的子树 

 王道和慕课的不一样，一直跟着慕课学的，根据王道的重新写个理解吧。

暂且把导致不平衡的结点称为麻烦结点。

（1）LL插入

A是根结点，麻烦结点在A的左孩子的左子树上，（左左）所以叫LL插入。 

注：可以是A的左孩子的左子树的左边，也可以是A的左孩子的左子树的右边。

LL插入，进行右单旋，就是A结点向右下旋转，转成B的右子树的根结点，B子树变成根结点。

（另一种记忆方式是，LL插入，让A的左孩子变成根结点，其它的根据大小挂载到B上）

（2）RR插入

 A是根结点，麻烦结点在A的右孩子的右子树上，（右孩子的右子树上，所以叫RR插入）

可以是右子树的左边，也可以是右子树的右边。

RR插入，进行左单旋，就是A结点向左下旋转，A结点变成B结点的左子树的根结点，B结点成为根结点。

（另一种记忆方法，RR插入，所以让A的右孩子变成根结点，其余的根据大小挂载）。

（3）LR插入

A是根结点，麻烦结点在A结点的左孩子的右子树上，所以是LR插入。

可以是右子树的左边也可以是右子树的右边。

LR插入，做LR旋转。

LR旋转，让A的左子树的右子树的根结点变成整颗树的根结点。

（4）RL插入

A是根结点 ，麻烦结点在A的右孩子的左子树上。

可以是左子树的左边也可以是左子树的右边。

RL插入，做RL旋转，也就是让A右子树的左子树的根结点变成整棵树的根结点。

n0=0,n1=1,n2=2,n3=4,n4=7,n5=12,n6=20 

3.平衡二叉树的删除 

1.删除结点

删除结点，方法同二叉排序树。

（1）若删除的是叶子结点，直接删除

（2）如果删除的结点只有一个子树，用子树顶替删除位置

（3）如果删除的结点有两个子树

a.用直接前驱结点顶替，然后转换为对直接前驱结点的删除

b.用直接后继结点顶替，然后转换为对直接后继节点的删除

2.删除完结点，一路向上检查看是否有不平衡结点，没有就结束，有就调整

3.调整时，找最小不平衡子树下，“个头”最高的儿子、孙子

4.根据孙子的位置进行调整

5.如果不平衡向上传导了，则继续2

---

红黑树

1.定义