===============
== 大程熙 ==
===============
一个小学生

数据结构之平衡二叉树学习

平衡二叉树重新学习。

二叉排序树可能退化成一个链表的缺点,可以使用平衡二叉树来解决。平衡二叉树具有二叉排序树所有特点,新增了一个特性来保证树的平衡:每个结点的左子树和右子树的高度差的绝对值不超过1。

平衡二叉树基于这样的特点,可以保证不会出现大量的结点偏向于一边的情况。

平衡二叉树的插入操作

平衡二叉树插入一个结点后可能导致平衡被破坏,需要调整该不平衡子树,达到新的平衡。

插入新结点有多种情况需要调整平衡:

  • LL型,在一个结点的左子结点(L)的左子结点(L)进行插入,需要进行向右旋转。
  • RR型,在一个结点的右子结点(R)的右子结点(R)进行插入,需要进行向左旋转。
  • LR型,在一个结点的左子结点(L)的右子结点(R)进行插入,需要先进行一次向左旋转,再进行一次向右旋转。
  • RL型,在一个结点的右子结点(R)的左子结点(L)进行插入,需要先进行一次向右旋转,再进行一次向左旋转。

LL型调整

当在B的左(L)孩子A的左(L)子树上插入结点时,需要向右旋转,B的左孩子A作为新的根节点,将A原来的右子树变为B的左子树,B变为A的右子树。

RR型调整

当在A的右(R)孩子的右(R)子树上插入结点时,需要向左选准,A的有孩子B作为新的根节点,B的左子树变为A的右子树,A变为B的左子树。

LR型调整

当在C的左(L)孩子A的右(R)子树B上插入结点时,需要先将A向左旋转,变成LL型,再将C向右旋转,B作为新的根节点,A作为B的左孩子,C作为B的右孩子。

RL型调整

当在A的右(R)孩子C的左(L)子树B上插入结点时,需要先将C向右旋转,变成RR型,再将A向左旋转,B作为新的根节点,A作为B的左孩子,C作为B的右孩子。

平衡二叉树分析

时间复杂度

  • 复杂度为$O(nlog_2n)$

缺点

平衡二叉树在每次插入和删除结点的时候,几乎都会破坏平衡,需要进行旋转调整平衡,在插入和删除频繁的场景中,频繁的平衡调整会影响性能。

红黑树可以解决平衡二叉树的缺点,红黑树在插入和查找过程中不会频繁破坏红黑树的平衡,不需要频繁调整。

参考内容

  • 《数据结构(Java版)》