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

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

数据结构教科书上开篇就是“什么是数据结构?”,这里我也就不多说了,没意思。 我总是把“数据结构”和“算法”这两个词语看做是一样的(个人而言哈),我们倒不如说说算法能干什么,学习数据结构能干什么? 不知道大家有没有看过印度大片《三傻大闹宝莱坞》,里边的主人公在上课(应该是机械课之类的)的时候被一位老师叫起回答一个问题,“说下机器的含义”,当时这位主人公就简单的说了句,“能省力的就是机器”。 现在就可以回答上面的问题了,学习算法和数据结构就是把你的程序运行速度变得更快,内存需求变得更小,代码长度变得更短。其中速度是最重…

2016年4月28日 0条评论 1点热度 阅读全文

一:概念介绍 单源最短路径问题,即在图中求出给定顶点到其它任一顶点的最短路径。形象点,如下图,假如有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条评论 6点热度 阅读全文