对于计算机考研数据结构考点“平衡二叉树”的内容，高顿小编在这里整理了以下有关信息，快来一起看看吧！
2024计算机考研数据结构高频考点【平衡二叉树】
　　任何一个结点的左右子树的高度相差不过1。
　　1)平衡因子：结点的左子树的高度减去右子树的高度。
　　平衡过程：插入、平衡、重组
　　a.插入：将新结点q按照平衡二叉搜索树的排序性质作为树叶插入，令其平衡因子为0，记下离q最近且平衡因子不为0的祖先结点s，若所有祖先结点的平衡因子均为0，令s指向根结点。
　　b.平衡：修改从s到q的路径上的结点的平衡因子，不修改s和q，对于其中的结点p，若q插在p的左子树，则平衡因子+1，否则-1。
　　c.重组：当s的平衡因子为0时，s为根结点，此时将s的平衡因子+1或者-1即可。
　　若s的平衡因子为-1，q插在s的左子树，或+1，插在右子树，只需改平衡因子为0。
　　若s的平衡因子为+1，q插在左子树，此时左重组，反之右重组。
　　2)重组方式：
　　a.若插入前，从根结点到新结点的插入位置的路径上，所有结点的平衡因子值均为0，则插入即可。
　　b.若插在结点较矮的子树上，则插入即可。
　　c.if(r->bf==1)
　　{s->lchild=r->rchild;r->rchild=s;}//LL
　　d.u=r->rchild;
　　r->rchild=u->lchild;
　　u->lchild=r;
　　s->lchild=u->rchild;
　　u->rchild=s;
　　本文内容整理于网络，仅供参考。
　　关于2024计算机考研数据结构高频考点【平衡二叉树】的内容，小编就给大家简单介绍到这里了。如果还有其他考研考试相关内容想要了解的，就请登录高顿考研频道看看吧。
　　小编为2024考研的小伙伴们准备了丰富的学习资料，点击下方蓝色图片即可领取哦~
考研备考资料
相关阅读
延伸阅读

展开全文