问题
问答题
下图为一棵AVL树(关键码按字典顺序排列):
请画出插入关键码won后的AVL树。
答案
参考答案:在AVL树中进行插入运算的过程:
(1)在AVL树中插入一个新结点x时,若AVL树为空,则令新结点x为插入后AVL树的根结点。
否则,将结点x的关键字与根结点T的关键字进行比较:
①若相等:不需要插入;
②若x.key<T->key:结点x插入到T的左子树中;
③若x.key>T->key:结点x插入到T的右子树中。
(2)插入后,如果此AVL树仍为平衡二叉树,则不需要旋转。
如果插入后,破坏了AVL树的平衡性,则需要通过旋转将其转化为平衡二叉树。
插入关键码won后的AVL树,如图1、图2、图3、图4所示: