AVL树的特性及插入操作
AVL树是一棵"严格"的平衡树, "被插入元素"到"根元素"的路径每个节点的左子树和右子树的高度差不能大于1.
举例来说:A的左子树的高度为1, 右子树高度为-1(null的高度为-1), 则A的两个子树的高度差为2
此时, 就要对高的子树下的元素进行旋转操作, 以降低其高度. 对上图我们可以经过一次右旋得到:
旋转的方式有4种,分为
1.单次旋(左旋, 右旋)
2.双次旋(先左旋后右旋, 先右旋后左旋)
具体怎么旋转, 取决于元素的大小关系, 为了好理解, 我画了下面这张图阐释.
图中的三角形表示元素的子树, 在左侧表示左子树, 在右侧表示右子树.
转载于:https://my.oschina.net/u/928852/blog/3000125