首页
|
新闻
|
新品
|
文库
|
方案
|
视频
|
下载
|
商城
|
开发板
|
数据中心
|
座谈新版
|
培训
|
工具
|
博客
|
论坛
|
百科
|
GEC
|
活动
|
主题月
|
电子展
注册
登录
论坛
博客
搜索
帮助
导航
默认风格
uchome
discuz6
GreenM
»
MCU 单片机技术
»
ARM
» 平衡二叉树的插入旋转
返回列表
回复
发帖
发新话题
发布投票
发布悬赏
发布辩论
发布活动
发布视频
发布商品
平衡二叉树的插入旋转
发短消息
加为好友
yuyang911220
当前离线
UID
1029342
帖子
9914
精华
0
积分
4959
阅读权限
90
在线时间
286 小时
注册时间
2014-5-22
最后登录
2017-7-24
论坛元老
UID
1029342
性别
男
1
#
打印
字体大小:
t
T
yuyang911220
发表于 2016-8-9 21:33
|
只看该作者
平衡二叉树的插入旋转
二叉树
,
绝对值
,
平衡
,
最好
平衡二叉树定义(AVL):它或者是一颗空树,或者具有以下性质的二叉树:它的左子树和右子树的深度之差的绝对值不超过1,且它的左子树和右子树都是一颗平衡二叉树。
最小不平衡子树:指离插入节点最近且以平衡因子的绝对值大于1的节点作为根的子树。
平衡因子(bf):结点的左子树的深度减去右子树的深度,那么显然-1<=bf<=1;
很显然,平衡二叉树是在二叉排序树(BST)上引入的,就是为了解决二叉排序树的不平衡性导致时间复杂度大大下降,那么AVL就保持住了(BST)的最好时间复杂度O(logn),所以每次的插入和删除都要确保二叉树的平衡,那么怎么保持平衡呢?
插入操作
在平衡二叉树中插入结点与二叉查找树最大的不同在于要随时保证插入后整棵二叉树是平衡的。那么
调整不平衡树的基本方法就是:
旋转,基本思路都是转换到左旋和右旋。
1) 右旋: 在最小平衡子树根节点平衡因子>=2且在根节点的左孩子的左孩子插入元素,进行右旋
2) 左旋: 在最小平衡子树根节点平衡因子>=-2且在根节点的右孩子的右孩子插入元素,进行左旋。
3) 右左:最小平衡子树根节点(80)的
右孩子
(100)的
左孩子
(90)的子节点(95)插入新元素,先绕根节点的右孩子节点(100)右旋,再围根节点(80)左旋
4) 左右:在最小平衡子树根节点(80)的
左孩子
(50)的
右孩子
(70)的子节点插入新元素,先绕根节点的左孩子节点(50)右旋,再围根节点(80)左旋
收藏
分享
评分
继承事业,薪火相传
回复
引用
订阅
TOP
返回列表
电商论坛
Pine A64
资料下载
方案分享
FAQ
行业应用
消费电子
便携式设备
医疗电子
汽车电子
工业控制
热门技术
智能可穿戴
3D打印
智能家居
综合设计
示波器技术
存储器
电子制造
计算机和外设
软件开发
分立器件
传感器技术
无源元件
资料共享
PCB综合技术
综合技术交流
EDA
MCU 单片机技术
ST MCU
Freescale MCU
NXP MCU
新唐 MCU
MIPS
X86
ARM
PowerPC
DSP技术
嵌入式技术
FPGA/CPLD可编程逻辑
模拟电路
数字电路
富士通半导体FRAM 铁电存储器“免费样片”使用心得
电源与功率管理
LED技术
测试测量
通信技术
3G
无线技术
微波在线
综合交流区
职场驿站
活动专区
在线座谈交流区
紧缺人才培训课程交流区
意见和建议