7.1.3　动态查找表

1. 二叉排序树

(1) 二叉排序树：或是空树或是：①左子树不空，则左子树上所有结点的值均小于它的根结点的值；②右子树不空，则右子树上所有结点的值均大于它的根结点的值；③它的左、右子树也分别为二叉排序树。

(2) 二叉排序树操作。插入和删除

(3) 二叉树上执行删除操作。①被删除结点是叶子结点；②被删除结点只有一棵子树；③被删除结点既有左子树又有右子树

(4) 二叉排序树的时间复杂度大致可看成O(log₂n)

2. 平衡二叉树

(1) 平衡二叉树(AVL)。一棵空树或是左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1，若将二叉树上结点的平衡因子定义为该结点的左子树的深度减去右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1，0，1。

(2) 平衡二叉树的平衡调整。在平衡二叉树上插入一个节点，使之失去平衡，便要进行二叉树的平衡调整。根据插入节点的位置不同，可将平衡二叉树失去平衡的状态分为以下四种：

LL型：在平衡二叉树的左子树的左子树上插入一个节点使之失去平衡。

RR型：在平衡二叉树的右子树的右子树上插入一个节点使之失去平衡。

LR型：在平衡二叉树的左子树的右子树上插入一个节点使之失去平衡。

RL型：在平衡二叉树的右子树的左子树上插入一个节点使之失去平衡。

①单向右旋平衡处理(LL型)；②单向左旋转平衡处理(RR型)；③双向(先左后右)旋转平衡处理(LR型)；④双向旋转(先右后左)平衡处理(RL型)。

3. B树

3.1. B

B

－树：

(1) B_－树：是一种多路查找树，或为空树或满足下列m叉树：①树中每个结点至多有m棵子树；②根结点如果不是叶结点，至少有两个孩子；③除根结点和叶结点之外，每个结点的孩子个数n为：m/2≤n≤m；④有n+1个孩子的结点具有n个关键字；⑤所有的叶子结点都出现在同一层上。

(2) B_－树的操作：插入和删除。3.2. B⁺树：

(1) B⁺树的特点。①有n棵子树的结点中含有n个关键字；②所有的叶子结点中包含了全部关键字的信息，及指向这些关键字记录的指针、且叶子结点本身依关键字的大小自小而大顺序链接；③所有的非终端结点可以看成是索引部分，结点中只含有其子树(根结点)中的最大(或最小)关键字。

(2) 操作。插入、删除和B_－基本类似。