C++模板实现的AVL树
1 AVL树的定义AVL树是一种自平衡二叉排序树,它的特点是任何一个节点的左子树高度和右子树的高度差在-1,0,1三者之间。AVL树的任何一个子树都是AVL树。2 AVL树的实现AVL树本质是一种二叉排序树,所以二叉排序树的任何性质AVL树都具有,但是AVL树稍微复杂的地方就是AVL树必须满足平衡条件,具体跟BST不同的地方主要体现在插入,删除操作。插入操作:当插入之后可能会出现不平衡,所以这时候要通过旋转树来实现平衡。旋转有四种类型,左左,左右,右左,右...