一:背景 平衡二叉树(又称AVL树)是二叉查找树的一个进化体,由于二叉查找树不是严格的O(logN),所以引入一个具有平衡概念的二叉树,它的查找速度是O(logN)。所以在学习平衡二叉树之前,读者必须需要了解下二叉查找树,具体链接:二叉查找树 那么平衡是什么意思?我们要求对于一棵二叉查找树 ,它的每一个节点的左右子树高度之差不超过1。(对于树的高度的约定:空节点高度是0;叶子节点高度是1。)例如下图: 在进行下面的分析之前,我们先对AVL树作个概述,让读者先了解其运作机制,而后读者接下来的阅读才会容易许多。 我们为…

2016年7月13日 0条评论 0点热度 阅读全文

一:概念介绍 单源最短路径问题,即在图中求出给定顶点到其它任一顶点的最短路径。形象点,如下图,假如有4个城镇A,B,C,D,它们之间有道路连通,且有长度。现在给定城镇A,求分别到其他城镇B,C,D的最短距离。正如下图, A到B,C,D的最短路径为: A--B  15 A--B--C  25 A--B--D  30 1)最短路径的最优子结构性质    该性质描述为:如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,k和s是这条路径上的一…

2016年3月2日 0条评论 0点热度 阅读全文