AVL树的python实现

AVL树是带有平衡条件的二叉查找树，一般要求每个节点的左子树和右子树的高度最多差1(空树的高度定义为-1)。 在高度为h的AVL树中，最少的节点数S(h)由S(h)=S(h-1)+S(h-2)+1得出...
avatar吴老二08月03日 树(Tree) 544 次浏览 评论
阅读全文

二叉查找树转变为有序双向链表

题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。 比如将二元查找树 10 /    \ 6       14 /  \     /　 \ ...
avatar吴老二06月25日 树(Tree) 406 次浏览 评论
阅读全文

B树及2-3树的python实现

B树(或称B-树)是一种适用于外查找的树，它是一种平衡的多叉树。 阶为M的B树具有下列结构特征： 1.树的根或者是一片树叶，或者其儿子数在2和M之间。 2.除根节点外的所有非树叶节点儿子数在┌M/2┐...
avatar吴老二06月18日 树(Tree) 625 次浏览 评论
阅读全文

图论(五)——最小生成树

一个无向图G的最小生成树就是由该图的那些连接了G的所有顶点的边构成的树，且其总权重最低。最小生成树存在当且仅当G是连通的。 对于任何一生成树T，如果将一条不属于T的边e加进来，则产生一个圈。如果从圈中...
avatar吴老二06月11日 图(Graph) 599 次浏览 评论
阅读全文

图论(二)——拓扑排序

拓扑排序是对有向无圈图的顶点的一种排序。如果存在一条vi到vj的路径，则vi排在vj前面。如果图含有圈，则拓扑排序是不可能的。 拓扑排序的两种排法： 一个简单的求拓扑排序的算法是先找出任意一个没有入边...
avatar吴老二05月19日 图(Graph) 615 次浏览 评论
阅读全文

图论(一)——图的表示

一个图(graph)G=(V,E)是由顶点集V和边集E组成。每一条边就是一个顶点对(v,w)，其中v,w∈V。如果点对是有序的，那么图就是有向图。 图中的一条路径path是一个顶点序列w1,w2,w3...
avatar吴老二05月11日 图(Graph) 858 次浏览 评论
阅读全文

Python数据结构——散列表

散列表的实现常常叫做散列(hashing)。散列仅支持INSERT,SEARCH和DELETE操作，都是在常数平均时间执行的。需要元素间任何排序信息的操作将不会得到有效的支持。 散列表是普通数组概念的...
avatar吴老二05月09日 散列表(Hash) 812 次浏览 评论
阅读全文

Python数据结构与算法——图（Graph）

如果我们可将自己的工作诠释成一个图问题的话，那么该问题至少已经接近解决方案了。而我们我们的问题实例可以用**树结构（tree）**来诠释，那么我们基本上已经拥有了一个真正有效的解决方案了。 0. 常见...
avatar吴老二04月29日 图(Graph) 788 次浏览 评论
阅读全文