• 欢迎来到我的博客
  • [email protected]

平衡二叉树(AVL)

学习笔记 tianlan 11个月前 (04-09) 293次浏览 0个评论 扫描二维码
文章目录[隐藏]

引入

如果二叉排序树用不好,就会退化成斜树,实现算法性能退化成了 O(n)

平衡二叉树(AVL)

定义

1.首先是二叉排序树

2.平衡二叉树要求每个节点的左子树和右子树的高度差至多等于 1,这个高度(深度)差的值叫做平衡因子 BF,也就是说 BF 的值不能大于1,否则就不是平衡二叉树。

实现原理

和二叉排序树差不多,只不过每次插入元素后,需要检查树的平衡性,如果平衡性遭到破坏,则需要通过左旋/右旋来调整平衡性。

平衡二叉树(AVL)

参考网站

https://xueyuanjun.com/post/21006


天蓝, 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:平衡二叉树(AVL)
喜欢 (0)
[[email protected]]
分享 (0)

您必须 登录 才能发表评论!