【数据结构】网易2012校园招聘题目--平衡二叉树的插入问题
平衡二叉树的插入问题 参考: http://www.cnblogs.com/fornever/archive/2011/11/15/2249492.html 文章中,将平衡二叉树的插入问题,归结为四种情形。分别是左左,右右,左右,右左。 这里的意思是: (1)左左:在一个结点的左孩子的左孩子上插入了一个结点,导致平衡破坏。
a结点有右孩子d,那要进行x和a变换,那么a的右孩子放哪啊? 很简单,如图放在x的左孩子上;分析:x>d,d>a,所以d可作为x的左孩子,且可作为a的右孩子中的孩子。 (2)右右:在一个结点的右孩子的右孩子上插入了一个结点,导致平衡破坏。
(3)左右:在一个结点的左孩子的右孩子上插入了一个结点,导致平衡破坏。
(4)右左:在一个结点的右孩子的左孩子上插入了一个结点,导致平衡破坏。 通过观察得出规律: 左左,右右只需做出一次旋转变换即可重新得出平衡二叉树。 左右,右左,需要做出两次旋转变化才能得到平衡二叉树。左右,一次变化得到左左,然后再变化得到平衡;右左,一次变化得到右右,然后再变化得到平衡。
这样,看网易这道校园招聘题就有思路了: 以下是一颗平衡二叉树,请画出插入键值3以后的这颗平衡二叉树。
变换过程: (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |