白话平衡二叉树

时间:2021-12-15 17:31:20

  对于我们做Java开发的程序员来,绝大多数时候我们并不需要自己去实现一个平衡二叉树的数据结构,很多用到二叉树的地方都是封装好的算法,我们只需要利用暴露出来的API就行了,那么对于平衡二叉树,虽然不需要去实现,但是理解原理对我们是很有帮助的,特别是底层如果使用了平衡二叉树,那么就能够清晰的知道他的性能。

  那么我们怎么样去理解平衡二叉树呢?

  我们都清楚,二叉树的查找性能最坏是链表查找,复杂度是O(1),而平衡二叉树的复杂度是log2(N),这在数据量比较大的情况下性能差距是很大的。所以我们就要尽量把树变成平衡二叉树,也就是所谓的高度平衡。最坏性能的情况是链表,对于这种数据结构来说,给我们感性的认识是这种数据结构很瘦,而满二叉树,完全二叉树很胖,因为胖,所以层数少,所以查找性能好。因此构建二叉树的时候要尽量做到很胖,而不要很瘦。这就是平衡二叉树。

  另外,关于构建二叉树的时候,有什么左旋转,有旋转,什么LL,RR,LR,RL这几种型号,其实也不用去记这种结构,我们只需要知道,假如有3个节点的链表,顺序增大或者减小,我们要把这种结构的链表编程二叉树,只需要用手抓住中间节点向上提一下,让中间节点在上方,两头的节点在下方,这就是让我们的层数减少了1,也就是在插入的时候平衡因子为2的时候破坏平衡性的时候,向上一提,层数减少1,于是又回到了平衡二叉树。这里说的是3个节点的顺序链表(用  大-中-小 来表示或者是小-中-大,都一样),如果是RL或者LR型,他不是顺序链表,而是(小-大-中)这种结构,所以我们就得先转换成(小-中-大),在抓住中间的向上提,这就有了所谓的先右旋转,再左旋转的操作。

  再来说删除,平衡二叉树在增加节点的时候会破坏平衡性,相反,删除的时候一样会破坏平衡,原理和增加节点差不多,删除叶子节点和只有一个子树的节点比较好理解,删掉,然后旋转就行了,如上面所说,复杂的是删除的节点左右都有子树,由于搜索二叉树的中序遍历得到的结果是一个从小到大的数组,那么删除某个元素的时候其实只需要将相邻的移除掉,这样一来还是能够建成为一颗平衡术,而相邻的节点必然是叶子节点或者只有左或者右子树的节点(这是由于排序的原理,仔细去思考一下,体会一下就明白了),所以又回到上面的节奏了,如果平衡被破坏,就旋转。

  这基本上就是AVL树的全部内容,我基本上是结合《大话数据结构》和http://blog.csdn.net/goodluckwhh/article/details/11786079这篇帖子来的。

  终归一句话,二叉树查找其实基本上是树的深度,所以我们要树变得很浅,很胖,而当出现不平衡的时候,我们要将其选择调整成为平衡树。

  这样来理解平衡二叉树相对来说要好理解一些。后面会分享一个白话的红黑树结构。