试题-若在一棵(分类)平衡树T中先删除某结点N,然后再插入该结点N,得到的新的平衡树T1,则T和T1不一定相同。但是如果在T上先插入结点M,然后再

题目

若在一棵(分类)平衡树T中先删除某结点N,然后再插入该结点N,得到的新的平衡树T1,则T和T1不一定相同。但是如果在T上先插入结点M,然后再删除M结点,那么得到的新的平衡树T2一定与T完全相同()

A.对

B.错

解答

正确答案是 B

平衡树左右子树的高度差的绝对值不超过 1（左右子树的高度差为该结点的平衡因子，只能取 -1， 0， 1），且其左右子树也是平衡树。

向平衡树中插入结点时，该结点一定是插入在叶子节点上的，这时需要检查平衡树的各结点的平衡因子，如果有平衡因子的绝对值大于 1的结点存在，就需要调整结点使其再次满足平衡树的性质。删除结点的时候也要检查平衡树的性质是否被破坏，然后做出相应的调整，具体的调整方法在这里就不再赘述。

综上，如果删除的结点N是叶子结点且删除之后平衡树不会涉及调整，那么再次插入该结点，树是相同的，否则就不同。同理，先插入结点M，若其不改变平衡树的性质，再删除结点M，树是相同的，否则就会不同。

C 7条回复评论

一只小鹿哈

学到了，原来是这样

发表于 2021-09-10 10:45:00

猪猪猪

完全是在考察语文逻辑。

平衡树先删除某结点之后，第一种情况，该结点是叶子结点，则删除之后在插入，T和T1是相同的；第二种情况，该结点是不是叶子结点，则删除之后，再插入的话，就只能在叶子结点插入，因而T和T1不相同；

平衡树先插入结点M，则是在叶子结点出插入M，因而删除该叶子结点之后，完全不影响T,因而T和T1是完全相同的

发表于 2018-10-13 16:01:18

橘子汽水

不论是删除还是插入，一旦打破平衡树的平衡属性，则不然会引起旋转。一旋转，树的结构就会发生变化。

发表于 2018-10-13 16:01:07

碧海问舟

原来是AVL树，题目看成是二叉排序树，所以选了对的

唉

总结：

若在一棵(分类)平衡树T中先删除某结点N,然后再插入该结点N,得到的新的平衡树T1,则T和T1不一定相同。但是如果在T上先插入结点M,然后再删除M结点,那么得到的新的平衡树T2一定与T完全相同() 错

若在一棵(分类)二叉排序树T中先删除某结点N,然后再插入该结点N,得到的新的二叉排序树T1,则T和T1不一定相同。但是如果在T上先插入结点M,然后再删除M结点,那么得到的新的二叉排序树T2一定与T完全相同() 对

发表于 2018-10-13 16:00:59

碧海问舟

因为平衡二叉树插入的节点不一定在叶子上，注意是平衡二叉树

发表于 2018-10-13 16:00:50

咸鱼王

插入的节点不一定在叶子节点上

发表于 2018-10-13 16:00:43

小可爱

删除4，再插入4

发表于 2018-10-13 16:00:34

问题信息

分类：数据结构 - 平衡二叉树

难度: