二叉排序树

性质：中序遍历是递增的

查找

算法实现

BSTree SearchBST(BSTree T, KeyType key) {
    if(!T || key == T->data) return T;
    else if(key < T->data) return SearchBST(T->lchild, key);
    else return SearchBST(T->rchild, key);
}

算法分析

最坏情况：单支树 ASL=(n+1)/2
平均情况：ASL=log2(n)

插入

时间复杂度O(log2(n))

创建

时间复杂度O(nlog2(n))

删除

在不破坏二叉排序树性质的情况下，选择合理的被删结点的左/右孩子对其进行替代。
时间复杂度O(log2(n))

平衡二叉树（AVL树）

平衡因子（BF）

节点左右子树的深度差。
AVL树的所有节点的BF为0/1/-1.
查找的时间复杂度是O(log2(n))

平衡调整方法

调整最小不平衡子树。
书上总结了4中旋转方式（LL，RR，RL，LR），但是完全不需要记，因为很抽象。确定好调整范围后直接进行调整。