一、AVL树的特征 虽说二叉查找树是一种优秀的数据结构，能够大大降低数据查询的复杂度。但是，并不是说有情况下二叉树都能够达到快速查找的目的。   我们发现，如果按照[7,10,11,12,14,15,18]这样的顺序一个个元素进行插入的话就会出现右图所示的二叉树，这样的二叉树跟一个链表几乎是没有区别的，查找的效率一样，没有体现出二叉树的优势。出现这种原因是构建二叉树的过程中没有平衡节点的左右子树的高度。根节点7的右子树有很高的深度，但是左子树是空的。我们需要的是一棵左右节点平衡的二叉树，而其中一种传统的平衡二叉树是AVL树。 树的高度可以看做是节点与最低的叶子节点的距离。根节点的高度最大...

一、二叉查找树 1、简介 二叉查找树也称为有序二叉查找树,满足二叉查找树的一般性质,是指一棵空树具有如下性质: 任意节点左子树不为空,则左子树的值均小于根节点的值. 任意节点右子树不为空,则右子树的值均大于于根节点的值. 任意节点的左右子树也分别是二叉查找树. 没有键值相等的节点. 2、局限性及应用 一个二叉查找树是由n个节点随机构成,所以，对于某些情况,二叉查找树会退化成一个有n个节点的线性链.如下图: b图为一个普通的二叉查找树,大家看a图,如果我们的根节点选择是最小或者最大的数,那么二叉查找树就完全退化成了线性结构,因此,在二叉查找树的基础上,又出现了AVL树,红黑树,它们两个...