请输入您要查询的百科知识:

 

词条 平衡二叉搜索树
释义

任何结点的左子树和右子树高度最多相差1的二叉搜索树。

(1)AVL树的插入算法

a. 插入结点之后仍然是AVL树,则不调整;

b. 插入结点之后不再满足AVL树条件,则进行调整,根据导致不平衡的原因,分为:

a) LL型――单旋转调整

b) LR型――双旋转调整

c) RL型――双旋转调整

d) RR型――单旋转调整

下图是顺序插入单词{cup,cop,copy,hit,hi,his,hia}后得到的AVL树,单词之间按照字典顺序比较:

(2)AVL树的删除算法

a. 删除过程如BST结点的删除算法(教材算法4.16);

b. 删除后调整――从被删除的结点找到祖父结点,然后开始单旋转或多旋转操作,一次旋转结束并不 意味着树已经平衡,因为这可能会导致它的祖先结点发生新的不平衡。所以这样的调整操作要一直进行下去,直到树平衡为止。

随便看

 

百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。

 

Copyright © 2004-2023 Cnenc.net All Rights Reserved
更新时间:2024/12/23 16:05:55