Tag-树

 2017-02-15 20:15:21 |  0 Comments  |  数据结构

树_AVL

# AVL树的实现 普通的二叉搜索树在多出插入删除后,左右子树节点数可能会出现较大的差异,此时插入删除操作的复杂度就不确定了。而AVL树能在插入或删除后自行调整结构,做到左右子树差不多高。 AVL是**平衡树**的一种 AVL树得名于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis ## 特点 - 自平衡的二叉搜索树,AVL树中任何节点的两个子树的高度最大差
 2017-02-15 20:15:11 |  0 Comments  |  数据结构

树_二叉查找树

# 二叉搜索树的实现 二叉搜索树也称二叉查找树 ## 特点 - 左子节点的值<根节点的值<右子节点的值 - 左右子树都是二叉搜索树 - 所有的节点的值不重复 **性能特点** 查找、插入的时间复杂度较低。为O(log n) 查找过程有点像`折半查找`,从父节点到子节点问题的规模就减半`t(n) = t(n/2) + c2`,所有其复杂度是O(log n),插入也是类似的。 ## 节点结构 ``` Python class SBTNode(): def __init__(self,value=None,parent=None,left=None,right=None): self.left = left self.parent = parent self.right = right self.value=value #使用魔法方法自定义比较运算符效果 def __gt__(self, other): return self.value>other.value def __ge__(self, other): return self.value>=other.value def __lt__(self, other): return self.value temp:
 2017-01-19 21:34:29 |  0 Comments  |  数据结构

树_基本概念

# 前言 本文继承自http://www.cnblogs.com/skywang12345/p/3576452.html 结合<<数据结构与算法分析>> 使用Python实现 # 名词解释 **结点的度**:结点拥有的子树的数目。 **叶子**:度为零的结点。 **分支结点**:度不为零的结点。 **树的度**:树中结点的最大的度。 **层次**:根结点的层次为1,其余结点的层次等于该结点的双亲结点的层次加1。