平衡二叉树AVL

1、定义

  平衡二叉树(Balanced Binary Tree)是二叉查找树的一个改进,也是第一个引入平衡概念的二叉树。1962年,G.M. Adelson-Velsky 和 E.M. Landis发明了这棵树,所以它又叫AVL树。平衡二叉树要求对于每一个节点来说,它的左右子树的高度(深度)之差绝度值不能超过1。如果插入或者删除一个节点使得高度之差大于1,就要进行节点之间的旋转,将二叉树重新维持在一个平衡状态。这个方案很好的解决了二叉查找树退化成链表的问题,把插入,查找,删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间,不过相对二叉查找树来说,时间上稳定了很多。

2、旋转

  单旋转

平衡二叉树AVL

上一篇:二叉查找树、平衡二叉树(AVL)、B+树、联合索引


下一篇:【数据结构】平衡二叉树—AVL树