文档介绍：动态搜索算法比较
[转自用于动态搜索的常见查找树主要有:二叉查找树(BST),平衡二叉查找树(AVL),红黑树(RBT),B~/B+树(B-tree)。这四种树都具备下面几个优势:
(1)都是动态结构。在删除,插入操作的时候,都不需要彻底重建原始的索引树。最多就是执行一定量的旋转,变色操作来有限的改变树的形态。而这些操作所付出的代价都远远小于重建一棵树。
(2)查找的时间复杂度大体维持在O(log(N))数量级上。可能有些结构在最差的情况下效率将会下降很快,比如BST。这个会在下面的对比中详细阐述。
下面我们开始概括性描述这四种树,并相互比较一下优劣。
(Binary Search Tree)详细见《查找结构专题(2):二叉查找树[BST]》
很显然,二叉查找树的发现完全是因为静态查找结构在动态插入,删除结点所表现出来的无能为力(需要付出极大的代价)。
BST的操作代价分析:
(1)查找代价:任何一个数据的查找过程都需要从根结点出发,沿某一个路径朝叶子结点前进。因此查找中数据比较次数与树的形态密切相关。
当树中每个结点左右子树高度大致相同时,树高为logN。则平均查找长度与logN成正比,查找的平均时间复杂度在O(logN)数量级上。
当先后插入的关键字有序时,BST退化成单支树结构。此时树高n。平均查找长度为(n+1)/2,查找的平均时间复杂度在O(N)数量级上。
(2)插入代价:新结点插入到树的叶子上,完全不需要改变树中原有结点的组织结构。插入一个结点的代价与查找一个不存在的数据的代价完全相同。
(3)删除代价:当删除一个结点P,首先需要定位到这个结点P,这个过程需要一个查找的代价。然后稍微改变一下树的形态。如果被删除结点的左、右子树只有一个存在,则改变形态的代价仅为O(1)。如果被删除结点的左、右子树均存在,,在改变一些左右子树即可。因此删除操作的时间复杂度最大不会超过O(logN)。
BST效率总结:查找最好时间复杂度O(logN),最坏时间复杂度O(N)。
插入删除操作算法简单,时间复杂度与查找差不多
(Balanced Binary Search Tree)详细见《查找结构专题(3):平衡二叉查找树[AVL]》
二叉查找树在最差情况下竟然和顺序查找效率相当,这是无法仍受的。事实也证明,当存储数据足够大的时候,树的结构对某些关键字的查找效率影响很大。当然,造成这种情况的主要原因就是BST不够平衡(左右子树高度差太大)。
既然如此,那么我们就需要通过一定的算法,将不平衡树改变成平衡树。因此,AVL树就诞生了。
AVL的操作代价分析:
(1)查找代价:AVL是严格平衡的BST(平衡因子不超过1)。那么查找过程与BST一样,只是AVL不会出现最差情况的BST(单支树)。因此查找效率最好,最坏情况都是O(logN)数量级的。
(2)插入代价:AVL必须要保证严格平衡(|bf|=1),那么每一次插入数据使得AVL中某些结点的平衡因子超过1就必须进行旋转操作。事实上,AVL的每一次插入结点操作最多只需要旋转1次(单旋转或双旋转)。因此,总体上插入操作的代价仍然在O(logN)级别上(插入结点需要首先查找插入的位置)。
(