计算机知识二叉平衡树AVL思维导图
简单介绍二叉平衡树AVL的内容
树图思维导图提供 计算机知识二叉平衡树AVL思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 计算机知识二叉平衡树AVL思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：9c0d55b282179a4d5f2c3d6fb3d40925
思维导图大纲
二叉平衡树AVL思维导图模板大纲
定义
任意结点的左右子树高度之差的绝对值不超过1
平衡因子
某结点的平衡因子指该结点左右子树高度之差
平衡二叉树中平衡因子的取值只可能为 -1，0，1
插入
插入结点之后要检查本次操作是否导致树的不平衡、有则调整结点位置关系使之达到平衡
调整方法
RR平衡旋转（左单旋转）
由于A的右孩子（R）的右子树（R）插入了新结点，破坏了平衡，因此要将右孩子B左旋转代替结点A，B原来的左子树给A当右子树
LR平衡旋转（先左后右双旋转）
由于A的左孩子B的右子树C插入了新结点，破坏了平衡，要进行两次旋转，先左旋后右旋：①将B的右孩子C左旋到B的位置 ②将C右旋到A的位置
RL平衡旋转（先右后做双旋转）
由于A的右孩子B的左子树C插入了新结点，破坏了平衡，要进行两次旋转，先右旋后左旋：①将B的左孩子C右旋到B的位置 ②将C左旋到A的位置
LL平衡旋转（右单旋转）
由于A的左孩子（L）的左子树（L）插入了新结点、破坏了平衡、因此要将左孩子B向右旋转代替结点A，B原来的右子树给A当左子树
查找
给定值与关键字比较的次数不超过树的深度
含有n个结点的平衡二叉树树的深度为 最大为O(log2 n)
平均查找长度为O(log2 n)
相关思维导图模板
树图思维导图提供 树状结构梦境分析问卷 在线思维导图免费制作，点击“编辑”按钮，可对 树状结构梦境分析问卷 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：affcf25df8be2c6146a1d6bc7888bbf1
树图思维导图提供 市场风险思维脑图 在线思维导图免费制作，点击“编辑”按钮，可对 市场风险思维脑图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：d03691e901556ef9b9d8e16358d169c2
沪公网安备 31011502019485号
上海工商