Tag Archives: 平衡二叉树

数据结构重读 - 平衡二叉树(AVL树)

大二那会根本没蹋下心来看,觉得天书一般,连旋转都没搞明白。

今天仔细看了书,发现真的一点不难啊,鄙视自己……

首先是概念:

平衡二叉树是为了解决前面二叉排序树不均衡的问题,而加入了一种平衡机制。所以,平衡二叉树是一种特殊的二叉排序树(BST)

AVL树查找的平均和最差复杂度都是O(logn) !!!(BST的最坏是O(n))

AVL树的插入复杂度是O(logn)。

平衡二叉树(简称AVL树):对任意一个结点,它的左子树和又子树都是平衡二叉树(左子树都小于结点[......]

继续阅读