平衡二叉树的 左旋右旋 以X为中心单左旋 双左旋等操作到底这么做?
来源:学生作业帮 编辑:百度作业网作业帮 分类:数学作业 时间:2024/07/24 09:48:58
平衡二叉树的 左旋右旋 以X为中心单左旋 双左旋等操作到底这么做?
苦恼很久了,看书还是不懂.
到底是怎么转的我还是没看出来,麻烦说详细点
以这道题为例吧:
插入序列:12,4,1,7,8,10,9,2,11,6,5
1、先插入12成为根
2、插入4在12的左子树,没有旋转
3、插入1在4的左子树,以4为中心向右单旋转,结果如下:
4
/ \
1 12
4、插入7在12的左子树,没有旋转
5、插入8在7的右子树,以8开始先左后右双旋转,结果如下:
4
/ \
1 8
/ \
7 12
6、插入10在12左子树,以8为中心开始向左单旋转,结果如下:
8
/ \
4 12
/ \ /
1 7 10
7、插入9在10 的左子树,以10为中心向右单旋转,结果如下:
8
/ \
4 10
/ \ / \
1 7 9 12
8、插入2在1的右子树,没有旋转
9、插入11在12 的左子树,没有旋转
10、插入6在7的左子树,没有旋转
11、插入5在6的左子树,以6为中心向右单旋转,结果如下:
8
/ \
4 10
/ \ / \
1 6 9 12
\ / \ /
2 5 7 11
苦恼很久了,看书还是不懂.
到底是怎么转的我还是没看出来,麻烦说详细点
以这道题为例吧:
插入序列:12,4,1,7,8,10,9,2,11,6,5
1、先插入12成为根
2、插入4在12的左子树,没有旋转
3、插入1在4的左子树,以4为中心向右单旋转,结果如下:
4
/ \
1 12
4、插入7在12的左子树,没有旋转
5、插入8在7的右子树,以8开始先左后右双旋转,结果如下:
4
/ \
1 8
/ \
7 12
6、插入10在12左子树,以8为中心开始向左单旋转,结果如下:
8
/ \
4 12
/ \ /
1 7 10
7、插入9在10 的左子树,以10为中心向右单旋转,结果如下:
8
/ \
4 10
/ \ / \
1 7 9 12
8、插入2在1的右子树,没有旋转
9、插入11在12 的左子树,没有旋转
10、插入6在7的左子树,没有旋转
11、插入5在6的左子树,以6为中心向右单旋转,结果如下:
8
/ \
4 10
/ \ / \
1 6 9 12
\ / \ /
2 5 7 11
首先插入一个根,然后插入子树,左边是小的,右边是大的插.如12、7、8.先拆除4跟12的联系,接上8,因为8是三个数的中间值,然后左边小右边大的插入上去.同理下面也是.
再问: 为什么这叫旋转 双旋转是什么 那顺\逆针旋转是怎样的呢
再问: 为什么这叫旋转 双旋转是什么 那顺\逆针旋转是怎样的呢
目前市场流行右旋VC,右旋是怎么回事?右旋VC真比左旋的好吗?
风机的左旋右旋是如何定义的
螺旋线的左旋和右旋是怎么判断的?
蜗轮蜗杆的左旋右旋传动如何判断呢?
若x是二叉树中序线索树中一个有左孩子的结点,切X不为根,则X的前驱为()
怎么判断螺栓左旋还是右旋?
请问电子经纬仪的水平角右旋/左旋是什么意思呢?盘左/盘右换盘的时候需要同时换右旋/左旋吗?
左旋右旋化学如何判断基团的大小优先顺序
求以双曲线4分之x的平方-5分之y的平方的中心为顶点,左焦点为焦点的抛物线标准方程
螺纹左旋和右旋有何区别
对于子弹飞行时的克里奥效应(地球偏转力)与膛线左旋和右旋之间的关系
在偏振现象的观测与分析中,如何产生和检测右旋或左旋椭圆偏振光?