数据结构之平衡二叉树
1.二分查找法
例:有5、10、19、21、31、37、42、48、50这10个数,现在从这10个数中查找48这条记录,查找过程如图所示。
3次找到。如果是顺序查找,要8次。但如果要查5这条记录,顺序查找只要1次,而二分查找法却需要4次。
对于上面10个数来说,顺序查找的平均查找次数为(1+2+3+4+5+6+7+8+9+10)/10=5.5次,
而二分查找法为(4+3+2+4+3+1+4+3+2+3)/10=2.9次。
因此平均来说二分查找法的效率比顺序查找法要好。
2.二叉查找树
二叉查找树是一种典型的数据结构。如下图一颗二叉查找数
图中的数字代表每个节点的键值,二叉查找树中,左子树的键值总小于根的键值,图中序遍历后输出:2、3、5、6、7、8。
如查键值为5的记录,先找到根,其键值为6,6大于5,因此找6的左子树,找到3,而5大于3,再找右子树......一共找了3次。
计算平均查找次数可得:顺序查找的平均查找次数为(1+2+3+4+5+6)/6=3.3次,
二叉查找树的平均查找次数为:(3+3+3+2+2+1)/6=2.3次。
二叉查找树比顺序查找快。
二叉查找树可以任意构造,如图
但效率就低了许多。若想最大性能的构造一个二叉查找树,需要这颗二叉查找树是平衡的,因此引出了新的定义---平衡二叉树,或称为AVL树。
3.平衡二叉树
定义:首先符合二叉树的定义,其次必须满足任何节点的左右两个子树的高度最大差为1。显然图5-3就不是一颗平衡二叉树了。
平衡二叉树对于查找的性能是比较高的,但不是最高的。要达到最好的性能,需要建立一颗最优二叉树,但最优二叉树的建立和维护需要大量的操作,
因此我们一般只需建立一颗平衡二叉树即可。
平衡二叉树对于查询速度的确很快,但是维护一颗平衡二叉树的代价非常大,通常需要1次或多次左旋或右旋来得到插入或更新后树的平衡性。
例:当插入新的键值为3的节点时,如图
除了插入操作,还有更新和删除操作,不过和插入没有本质区别,都是通过左旋或右旋来完成的。因此对于一颗平衡二叉树的维护是有一定开销的,
不过平衡二叉树多用于内存结构对象中,因此维护的开销相对较小。