算法基础（一）

最近俩天学习了很多算法,很感兴趣 所以准备长期更新下去标题 有时会学习下英语单词 学习高数 所以日期不定
写者目的 供回忆复习使用 很多基础内容请看专业书籍记忆

很多算法 如常规算法 汉诺塔 二分查找 线性查找 冒泡排序 快速排序 创建堆 堆排 插入 插入排序 希尔排序 计数排序 基数排序 桶排序 线性二叉树排序 括号 迷宫深度搜索 迷宫广度搜索 等等不多详讲 很容易学会
下面讲一个AVL树的写法

AVL 需要了解二叉树 见 AVL树百度百科

class AVLTree(BSTTree):def __init__(self,li=None):BSTTree.__init__(self,li)#右右左旋#即 s2 属于p   p属于cdef rotote_left(self,p,c):s2 =c.lchild;p.rchild=s2if s2:s2.parent=pc.lchild=pp.parent=c#更新bfp.bf = 0c.bf = 0return cdef rotote_right(self,p,c):s2=c.rchildp.lchild=s2if s2:s2.parent=pc.rchild=pp.parent=c#更新bfp.bf=0c.bf=0return cdef rotote_right_left(self,p,c):g=c.lchilds3=g.rchildc.lchild=s3if s3:s3.parent=cg.rchild =cc.parent=gs2=g.lchildp.rchild=s2if s2:s2.parent=pg.lchild=pp.parnent=g#更新bfif g.bf>0:c.bf=0p.bf=-1elif g.bf<0:c.bf=1p.bf=0else:p.bf=0c.bf=0return g#def rotote_left_right(self,p,c):g=c.rchilds2=g.lchildc.rchild=s2if s2:s2.parent=cs3=g.rchildp.lchild=s3if s3:s3.parent=pg.rchild=pp.parent=gg.lchild=cc.parent=g#更新bfif g.bf>0:p.bf=0c.bf=-1elif g.bf<0:p.bf=1c.bf=0else:p.bf=0c.bf=0return gdef insert_no_rec(self,val):p = self.root  #初始为搜索二叉树树if not p:self.root = AVLNode(val)returnwhile True:if val < p.data:if p.lchild:p = p.lchild  #持续遍历else:p.lchild = AVLNode(val)  #符合条件创建p.lchild.parent = p   #连接父节点node=p.lchild  #保存生成的pbreakelif val > p.data:if p.rchild:p = p.rchildelse:p.rchild = AVLNode(val)p.rchild.parent = pnode=p.lchild  #保存生成的pbreakelse:return  #不允许插入相同的值#接下来循环遍历print("进入")self.mid_order(self.root)while node.parent:if node.parent.lchild==node: #判断是从哪个树插入的  左边  即有 左左 （右旋）  左右 (左旋右旋)g = node.parent.parentprimitiveNode = node.parentif node.parent.bf<0:if node.bf>0:n=self.rotote_left_right(node.parent,node)breakelse:n=self.rotote_right(node.parent,node)elif node.parent.bf>0:node.parent.bf=0breakelse:node.parent.bf=-1node=node.parentcontinueelse:if node.parent.bf>0:g = node.parent.parentprimitiveNode = node.parentif node.bf>0:n=self.rotote_left(node.parent,node)else:n=self.rotote_right_left(node.parent,node)elif node.parent.bf<0:node.parent.bf=0breakelse:node.parent.bf=1node=node.parentcontinuen.parent=gif not g:self.root=nreturnif g.lchild==primitiveNode:g.lchild=nodebreakelse:g.rchild=nodebreak

大致的内容:
AVL树插入 搜索树的插入规则 结合 左旋 右旋 左右旋 右左旋
形成
bf是AVL树重要表现形式 我们可以自定义balanced factor bf 如 右树每有一层为正数 左树每有一层为负数 相加即为bf
只要是AVL树 其balanced factor总是不大于1 或者小于-1