二叉查找树AVL树

二叉查找树 若它的左子树不为空,则左子树上所有的节点值都小于它的根节点值。 若它的右子树不为空,则右子树上所有的节点值都大于它的根节点值。 它的左右子树也分别可以充当为二叉查找树。 查找的平均复杂度是O(log(n))的,最坏情况是O(N)的。 查找所需的次数是二叉查找树的最大深度。 AVL树(平衡二叉查找树) 具有二叉查找树的全部特性。 每个节点的左子树的高度和右子树高度差值小于等于1(平衡二叉树的性质) 左旋:逆时针旋转两个节点,原先的右节点成为新的父节点,原先的父节点成为原先的右节点的左节点。如果原先的右节点有左节点,则将该左节点挂到原先的父节点的右侧。 右旋:顺时针旋转两个节点,原先的