外冈网站建设,程序员接外包网站,wordpress带会员vip主题,鞍山信息港官网目录 树的组成
节点
度
根节点
其他组成部分
二叉树
普通二叉树
二叉查找树
二叉树的遍历
前序遍历
中序遍历
后序遍历
层序遍历
总结
平衡二叉树
平衡二叉树的旋转机制
左旋
右旋
需要旋转的四种情况
左左
左右
右右
右左
总结
红黑树 树的组成
节点…目录 树的组成
节点
度
根节点
其他组成部分
二叉树
普通二叉树
二叉查找树
二叉树的遍历
前序遍历
中序遍历
后序遍历
层序遍历
总结
平衡二叉树
平衡二叉树的旋转机制
左旋
右旋
需要旋转的四种情况
左左
左右
右右
右左
总结
红黑树 树的组成
节点
先引入树的组成节点
节点又分为父节点左子节点和右子节点 节点的组成是什么呢 度
度是每一个节点的子节点的数量
所以在二叉树中任意节点的度2
根节点
最顶层的节点
其他组成部分 二叉树
普通二叉树
满足度小于等于2的普通的树
二叉查找树 特点度小于等于2
左子节点小于当前节点
右子节点小于当前节点
二叉树的遍历
我也不知道如何介绍看图片以及结合文字思考一下很容易就能明白
图片左侧是遍历后的结果顺序是从左往右从上往下
前序遍历 中序遍历 后序遍历 层序遍历 总结 平衡二叉树
规则任意节点左右子树高度差不超过1
如下图你不能只看根节点你还得看其他的所有节点看看所有节点的左右子树高度差是否超过一
注意没有左右节点时我们认为该节点的左右节点的高度为0
举例左侧二叉树的10节点他没有左节点所以左节点高度为0右节点高度为3高度差为3所以不是平衡二叉树 平衡二叉树的旋转机制
旋转分为左旋和右旋
触发时机当添加一个节点后平衡二叉树不再平衡就要进行相应的旋转
左旋
类型一不平衡的节点不是根节点时
举个例子
下图是一个平衡二叉树 在11节点处添加右节点12此时二叉树不再平衡如下图 然后我们要找到导致不平衡的节点
方法如下也就是从我们添加的12节点处开始往上找判断节点是否平衡知道找到不平衡的节点为止如下图我们找到了10 所以接下来我们要对其进行左旋
步骤如下图 类型二不平衡的节点是根节点时
举例
加节点前 加节点后 找不平衡节点
最后发现是根节点7不平衡
进行左旋
步骤如下图 右旋
这个和左旋基本操作类似所以我不多加详细介绍了直接给图
类型一不平衡的节点不是根节点时
右旋前 右旋后 类型二不平衡的节点是根节点时
右旋前 右旋后 需要旋转的四种情况
左左
旋转前添加节点分别是1和3 旋转后 左右
旋转前添加节点为6 第一次局部左旋变成左左的情况 第二次整体右旋 右右
旋转前12为添加节点 一次左旋即可 右左
旋转前8为添加节点 对根节点的右子树进行局部右旋得到 此时变为了右右的情况了再对他进行整体左旋 总结 红黑树
有点复杂不好讲述自行看图片介绍 是一个二叉查找树高度不平衡满足红黑规则
红黑规则 添加节点的规则 注意这里的叔叔个人认为是伯伯比较是父亲的兄弟也就是说如果父是左右子节点则叔就是右左子节点
其余的自己看按照步骤走
