0%

AVL树

0x00 AVL树

AVL树是平衡二叉查找树,在AVL树中任何节点的两个子树的高度最大差别为1,所以,也被称为高度平衡树。他有以下特点:

  • 本身首先是一颗二叉搜索树
  • 他的左右子树高度差的绝对值最多为1
  • 他的左右子树都为AVL树

而二叉搜索树是

  • 他的左子树的所有值<=根节点<=右子树
  • 他的左右子树都是二叉搜索树
1
2
3
4
5
struct tree_node{
int key; //value值
struct tree *left,*right;//左右子树
int height;//树的高度
};

0x01 树旋转

这个就比较有意思了,这个操作发生于树不平衡的情况,这时候就要用旋转操作来平衡树,但也不是整个树也要跟着旋转,一般是子树旋转

参考:https://blog.csdn.net/qq_25343557/article/details/89110319

那么问题来了,怎么确定旋转的根节点呢,

0x02 总结

算法岂是我等弟弟能学的