ZKX's LAB

平衡二叉树 删除结点如何调整 在平衡二叉树上删除一个结点后仍使其平衡,最坏情况下需要旋转多少次?

2020-10-12知识9

在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A 根据题意,这棵树应该是这样D D\\/\\A E 插入C A EB B\\C这时不平衡点为A,无左孩子,平衡因子0-1=-1所以应该用LR左右型来调整。

在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A 根据题意,这棵树应该是这样 D D/\\/\\ A E 插入C A E/B B \\ C这时不平衡点为A,无左孩子,平衡因子0-1=-1所以应该用LR左右型来调整。

平衡二叉树节点的删除得到的平衡二叉树唯一吗? 某结点的平衡因子原来不为0,并且删除造成其较矮的子树被更变矮一层,于是该结点发生不平衡当其原来的较高子树(该子树并未被变矮)的平衡因子为0,则可以执行一个单旋转(或者双旋转)来恢复结点的平衡因此此时原则上的结果并不唯一但是不过如果要写程序,肯定是用单旋转而不是双旋转,相比执行的操作要少一些,运行结果自然也唯一了

平衡二叉树删除结点需要考虑平衡因子吗? 这个肯定需要考虑的,删除节点可能导致平衡二叉树不平衡,进而需要调整平衡树和平衡因子。

在平衡二叉树上删除一个结点后仍使其平衡,最坏情况下需要旋转多少次? 设树的高度为h,则最坏时需要从最深分支的倒数第3层开始一直旋转到根,不论是单旋转还是双旋转都算旋转一次,就是h-2次

#平衡二叉树

随机阅读

qrcode
访问手机版