二叉排序树
性质:中序遍历是递增的
查找
算法实现
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),但是完全不需要记,因为很抽象。确定好调整范围后直接进行调整。