AVL树概念 AVL树旋转、插入、删除操作说明

发布:2022-10-25 11:10:56
阅读:2341
作者:网络整理
分享:复制链接

AVL树是一种平衡二叉搜索树,其特点是左侧子树与右侧子树的高度差的绝对值是0和1。

AVL树实例图

AVL树旋转、插入、删除操作

1、AVL树旋转子树

即交换子树节点的位置,旋转后的AVL树依旧遵循高度平衡规则。左旋转,右侧节点的排列被转换为左侧节点的排列。前后如下图:

右旋转,左侧节点的排列被转换为右侧节点的排列。前后如下图:

平衡旋转,有2种情况,一是先左旋转后右旋转,排列首先向左移动,再向右移动;二是先右旋转再左旋转,排列首先向右移动,再向左移动。如下图:

先左旋转后右旋转。

先右旋转再左旋转。

2、插入新节点

初始二叉树。

设要插入的节点“9”,首先遍历初始二叉树左侧子树和右侧子树,再考虑AVL树高度平衡规则,则得出最后的二叉树结构,如下图:

3、删除节点

删除节点后,AVL树的平衡发生变化。为了重新平衡,需要执行适当的旋转。

首先,定位要删除的节点,根据节点是否存在子节点,进行替换删除,考虑高度平衡规则,需要旋转来平衡。

替换要删除的节点。

删除节点W,并更新。

向右旋转以平衡树。

最终得到Avl树,如下图:

扫码进群
微信群
免费体验AI服务