平衡二叉树
gonghr 人气:0声明：图片及内容基于：https://www.bilibili.com/video/BV1kT4y1w7Cx?from=articleDetail
平衡二叉树的定义
构造平衡二叉树
平衡二叉树的调整
LL型
①将A的左孩子B提升为新的根结点；
②将原来的根结点A降为B的右孩子；
③各子树按大小关系连接(BL和AR不变，BR调整为A的左子树)。
RR型
①将A的右孩子B提升为新的根结点；
②将原来的根结点A降为B的左孩子；
③各子树按大小关系连接(AL和BR不变，BL调整为A的右子树)。
LR型
①将B的左孩子C提升为新的根结点；
②将原来的根结点A降为C的右孩子；
③各子树按大小关系连接(BL和AR不变，CL和CR分别调整为B的右子树和A的左子树)。
RL型
①将B的左孩子C提升为新的根结点；
②将原来的根结点A降为C的左孩子；
③各子树按大小关系连接(AL和BR不变，CL和CR分别调整为A的右子树和B的左子树)。
练习
答案：LL型
四种调整类型总结
拓展
加载全部内容