设为首页 加入收藏

TOP

【C++研发面试笔记】10. 基本数据结构-平衡二叉搜索树AVL
2016-10-08 11:31:12 】 浏览:258
Tags:研发 面试 笔记 10. 基本 数据结构 平衡 搜索 AVL

10.1 AVL的定义

定义:平衡二叉树或为空树,或为如下性质的二叉排序树:
(1)左右子树深度之差的绝对值不超过1;
(2)左右子树仍然为平衡二叉树.
平衡因子BF=左子树深度-右子树深度.
平衡二叉树每个结点的平衡因子只能是1,0,-1。若其绝对值超过1,则该二叉排序树就是不平衡的。


10.2 AVL的实现

10.2.1 结构

这里写图片描述

10.2.2 节点的创建

这里写图片描述

10.2.3 旋转

AVL树在插入节点,可能会失去平衡,其情况是LL、LR、RL、RR这4种之一。
(1) LL:LeftLeft,也称为”左左”。插入或删除一个节点后,根节点的左子树的左子树还有非空子节点,导致”根的左子树的高度”比”根的右子树的高度”大2。
(2) LR:LeftRight,也称为”左右”。插入或删除一个节点后,根节点的左子树的右子树还有非空子节点,导致”根的左子树的高度”比”根的右子树的高度”大2。
(3) RL:RightLeft,称为”右左”。插入或删除一个节点后,根节点的右子树的左子树还有非空子节点,导致”根的右子树的高度”比”根的左子树的高度”大2。
(4) RR:RightRight,称为”右右”。插入或删除一个节点后,根节点的右子树的右子树还有非空子节点,导致”根的右子树的高度”比”根的左子树的高度”大2。
这里写图片描述
这4种情况对应的旋转方法:
(1)LL失去平衡的情况,可以通过一次旋转让AVL树恢复平衡。
这里写图片描述
这里写图片描述
(2)RR是与LL对称的情况!RR恢复平衡的旋转方法如下:
这里写图片描述
这里写图片描述
(3)LR失去平衡的情况,需要经过两次旋转才能让AVL树恢复平衡:
这里写图片描述
这里写图片描述
(4)RL是与LR的对称情况!RL恢复平衡的旋转方法如下:
这里写图片描述
这里写图片描述

10.2.4 查找

这里写图片描述
非递归方法
这里写图片描述

10.2.5 结点插入

这里写图片描述

10.2.6 删除节点

这里写图片描述
这里写图片描述

10.2.7 销毁AVL树

这里写图片描述

10.2.8 树的遍历

这里写图片描述

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇【C++研发面试笔记】2. 多态性 下一篇C++及数据结构笔试面试常见知识点..

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目