数据信息构造与优化算法python語言完成(五) 树

摘要:1.树是有层级的:越贴近高层的归类越广泛,越贴近最底层的归类越与众不同2.一个连接点的子连接点和另外一个连接点的子连接点互相中间是防护,单独的3.每个叶连接点(最低层的连...

1.树是有层级的:越贴近高层的归类越广泛,越贴近最底层的归类越与众不同
2.一个连接点的子连接点和另外一个连接点的子连接点互相中间是防护,单独的
3.每个叶连接点(最低层的连接点)都具备唯一性

树的运用:
文档系统软件
HTML标识
网站域名管理体系

树构造的专业术语:
Node 连接点:每一个连接点都是有一个key-value
Edge 边:边是联接2个连接点的线,表明连接点中间相关系,边有进出方位,一个连接点能够有一条入边(父连接点连向自身的边),有好几条出边。根连接点沒有入边,叶连接点沒有出边
Root 根(连接点) 树中唯一沒有入边的连接点
Path 相对路径:由边先后联接在一起的连接点的井然有序目录
Children 子连接点
Parent 父连接点
Sibling 弟兄连接点:具备同一个父连接点的连接点
Subtree 篇幅
Left 叶连接点:最底层连接点
Level 等级:从根连接点刚开始到某一个连接点所历经的边数。根连接点的等级是0层
高宽比:较大等级即高宽比

树实际上是连接点和边的结合

==========================================

 

树的python完成

 

1.用目录+递归完成一个二叉树(二叉树是一个父连接点数最多只有有2个子连接点的树)
构思:一个目录储放3个原素,第一个原素是根连接点,第二个和第三个原素是左子树和右子树,左子树和右子树又包括了支系连接点。
为何用递归完成,由于树的部分构造和总体构造是类似的,这类状况就很合适应用递归完成。比如左子树的构造和整棵树一样全是二叉树,左子树的左子树也是一个二叉树。

# 应用目录完成一个二叉树
class BinaryTree:
    def __init__(self,root):
        # 第二和第三个原素是左子树和右子树,假如要完成n叉树,则必须目录有n+一个原素
        self.tree = [root,[],[]]    # root是根连接点,是一个一般种类的数据信息而并不是目录
    # 加上一个新连接点到树中做为其立即的左子连接点
    def insertLeft(self,item,tree=[]):  # item是一个一般种类的数据信息
        tree = tree if tree else self.tree
        leftTree = tree.pop(1)
        if len(leftTree) 0:
            tree.insert(1,[item,leftTree,[]])
        else:
            tree.insert(1,[item,[],[]])
    # 加上一个新连接点到树中做为其立即的右子连接点
    def insertRight(self,item,tree=[]):
        tree = tree if tree else self.tree
        rightTree = tree.pop(2)
        if len(rightTree) 0:
            tree.insert(2, [item, [], rightTree])
        else:
            tree.insert(2, [item, [], []])
    # 获得根连接点
    def getRootVal(self,tree=[]):
        tree = tree if tree else self.tree
        return tree[0]
    # 设定根连接点
    def setRootVal(self,item,tree=[]):
        tree = tree if tree else self.tree
        tree[0] = item
    # 获得一个树的左子树
    def getLeftChild(self,tree=[]):
        tree = tree if tree else self.tree
        return tree[1]
    # 获得一个树的右子树
    def getRightChild(self,tree=[]):
        tree = tree if tree else self.tree
        return tree[2]
    def __str__(self):
        return str(self.tree)
if __name__ == "__main__":
    t = BinaryTree(1)
    t.insertLeft(4)
    t.insertLeft(5)
    t.insertRight(6)
    t.insertRight(7)
    print(t)
    l = t.getLeftChild()
    print(l)
    t.setRootVal(9,l)
    print(t)
    t.insertLeft(11,l)
    print(t)
    print(t.getRightChild(t.getRightChild()))
    


   
从上边的编码能看出,加上连接点的情况下并不是只有从叶连接点加上连接点,还可以从随意一个非叶连接点下加上一个连接点。

 

2.应用链表完成二叉树

# 应用链表完成二叉树
class Node:     # 链表连接点类,这一连接点类和以前单边链表或是双重链表格中的连接点类不一样,不一样取决于它的有2个指针,由于二叉树的一个连接点有两根边
    def __init__(self,value):
        self.value = value
        self.left = None    # 左指针
        self.right = None   # 右指针
    def __str__(self):
        return str({"value":self.value,"left":self.left,"right":self.right})
class LinkedListBinaryTree(Node):       # 二叉树实质是一个有2个指针的连接点
    # 往一棵树的根连接点下插进一个左子连接点
    def insertLeft(self,nodeValue):
        leftTree = LinkedListBinaryTree(nodeValue)  # 转化成一棵左子树
        if self.left == None:
            self.left = leftTree
        else:
            leftTree.left = self.left
            self.left = leftTree
    def insertRight(self, nodeValue):
        rightTree = LinkedListBinaryTree(nodeValue)  # 转化成一棵左子树
        if self.right == None:
            self.right = rightTree
        else:
            rightTree.right = self.right
            self.right = rightTree
    def getRootVal(self):     # 获得根连接点的值
        return self.value
    def setRootVal(self,value):
        self.value = value
    def getLeftChild(self):  # 获得左子树
        return self.left
    def getRightChild(self):
        return self.right
        


应用链表完成树更为的形象化

 

=========================================

树的运用:表述式分析

# 简易的数学课表述式分析(用二叉树完成)
class MathExpression:
 num = list("")
 opDict = {"+": operator.add, "-": operator.sub, "*": operator.mul, "/": operator.truediv}
 def __init__(self,expression):
 self.expression = list(expression) # 传到的表述式是一个全括弧表述式,每个实际操作都用()包起来
 self.currentTree = None # 纪录当今子树是哪一棵
 self.topTree = None # 纪录最高层的子树
 self.degree = [] # 将历经树的层用存进到栈内(目地是让currentTree能够返回上一层子树),栈用目录仿真模拟
 # 搭建一棵表述式分析树
 # 这棵树是由好几个单面的二叉树搭建而成的一棵大二叉树
 # 叶子连接点只有是实际操作数,非叶子连接点和根连接点只有是实际操作符
 # 当碰到最终一个“)”的情况下,当今子树 currentTree 会返回最底层
 def build(self):
 for item in self.expression:
 if item == " ":
 continue
 if item == "(": # 碰到左括弧则建立一棵单面的二叉子树
 if self.currentTree == None: # 假如沒有建立过树,则该二叉子树做为高层的树干
 self.currentTree = LinkedListBinaryTree()
 self.topTree = self.currentTree
 else: # 假如早已拥有高层的树干,则建立的二叉子树加上为当今子树的左子树或是右子树
 if self.currentTree.left == None:
 self.currentTree.insertLeft("")
 tree = self.currentTree.getLeftChild()
 else:
 self.currentTree.insertRight("")
 tree = self.currentTree.getRightChild()
 self.degree.append(self.currentTree) # 进到下一层以前,先纪录这一层是哪个支系
 self.currentTree = tree # 进到下一层

if item in self.opDict: # 碰到实际操作符则为当今子树的根连接点设定值 self.currentTree.setRootVal(item) if item in self.num: # 碰到实际操作数则将实际操作数纪录到当今子树的左叶子连接点或是右叶子连接点 if self.currentTree.left == None: self.currentTree.left = item else: self.currentTree.right = item # 测算表述式树中表述式的結果(应用递归 + 分治算法对策) def calculate(self): # 这一并不是完毕标准只是一种独特状况的分辨 if self.currentTree.getRootVal() not in self.opDict: return self.currentTree.getRootVal() op = self.opDict[self.currentTree.getRootVal()] if not isinstance(self.currentTree.left, LinkedListBinaryTree): # 完毕标准 left = self.currentTree.left else: self.degree.append(self.currentTree) self.currentTree = self.currentTree.left left = self.calculate()
if not isinstance(self.currentTree.right, LinkedListBinaryTree): # 完毕标准 right = self.currentTree.right else: self.degree.append(self.currentTree) self.currentTree = self.currentTree.right right = self.calculate() res = op(int(left),int(right)) self.currentTree.setRootVal(res) # 沒有这一步还可以 self.currentTree = self.degree.pop() # 每测算出一身高树的值就回到上一层 return res if __name__ == "__main__": expression = "((1+(2*3))-4)" mp = MathExpression(expression) mp.build() # 搭建表述式树 print(mp.currentTree == mp.topTree) # 当搭建完表述式树的情况下,当今连接点变回根连接点 print(mp.calculate())

 

 


树的解析xml

有3种方式
1.前序解析xml(preorder)
先浏览根连接点,再递归的前序浏览左子树,最终前序浏览右子树

2.中序解析xml(inorder)
先递归的中序浏览左子树,在浏览根连接点,最终中序的浏览有连接点

3.后序解析xml(postorder)
依次序的浏览左子树,再后编号的浏览右子树,最终浏览根连接点

接下去各自完成这3种解析xml方式

# 树的解析xml
# 前序解析xml(以从上到下的次序解析xml)
def preorder(binaryTree):
    if isinstance(binaryTree,LinkedListBinaryTree):
        print(binaryTree.getRootVal())
        preorder(binaryTree.getLeftChild())
        preorder(binaryTree.getRightChild())
    elif binaryTree != None:
        print(binaryTree)
# 中序解析xml(以从左往右的次序解析xml)
def inorder(binaryTree):
    if isinstance(binaryTree,LinkedListBinaryTree):
        inorder(binaryTree.getLeftChild())
        print(binaryTree.getRootVal())
        inorder(binaryTree.getRightChild())
    elif binaryTree != None:
        print(binaryTree)
# 后序解析xml(以从下到上的次序解析xml)
def postorder(binaryTree):
    if isinstance(binaryTree,LinkedListBinaryTree):
        postorder(binaryTree.getLeftChild())
        postorder(binaryTree.getRightChild())
        print(binaryTree.getRootVal())
    elif binaryTree != None:
        print(binaryTree)
if __name__ == "__main__":
    expression = "((1+(2*3))-4)"
    mp = MathExpression(expression)
    mp.build()      # 搭建表述式树
    preorder(mp.topTree)
    print("---")
    inorder(mp.topTree)
    print("---")
    postorder(mp.topTree)
    

从上边的编码能看出,三种解析xml方法编码彻底一样,仅仅启用次序有一定的不一样。
口诀
前序:上上下
中序:左上右
后序:上下上

这儿非常值得一提的是,不管是哪样解析xml全是用了分治算法对策。

上边的表述式树在calculate的情况下是先获得子树的根连接点,再获得左子连接点,再获得右子连接点,是一个上上下的次序,因此归属于前序解析xml。

下边写一个涵数版本号的表述式树的搭建,分析和解析xml# 涵数版的表述式树

def buildParseTree(fexp):
    fexp = list(fexp)
    # 一刚开始先建立一个高层子树,根连接点不取值
    currentTree = None
    stack = []  # 用栈储存currentTree历经的哪几层子树,便捷当今树currentTree的回朔
    for i in fexp:
        # print(stack)
        if fexp == " ":
            continue
        if i == "(":
            if currentTree == None:
                currentTree = LinkedListBinaryTree("")
            currentTree.insertLeft("")      # 建立一棵左子树
            currentTree.insertRight("")      # 建立一棵右子树
            stack.append(currentTree)  # 进到下一层的树前,先将本层的树放进stack中,纪录currentTree历经的树
            currentTree = currentTree.getLeftChild()    # 进到下一层树
            # print(currentTree)
        elif i not in ["(","+","-","*","/",")"]:
            # print(currentTree)
            currentTree.setRootVal(i)
            currentTree = stack.pop()
        elif i in ["+","-","*","/"]:
            currentTree.setRootVal(i)
            stack.append(currentTree)
            currentTree = currentTree.getRightChild()
        elif i == ")":
            if len(stack):
                currentTree = stack.pop()
    return currentTree
# 应用中序解析xml的方法测算
def calculateParseTree(tree):
    opDict = {"+": operator.add, "-": operator.sub, "*": operator.mul, "/": operator.truediv}
    if tree.getRootVal() not in ["+","-","*","/"]:  # 假如根连接点的值是标值而并不是标记,则考虑完毕标准
        return tree.getRootVal()
    left = calculateParseTree(tree.getLeftChild())
    op = opDict[tree.getRootVal()]
    right = calculateParseTree(tree.getRightChild())
    return op(int(left),int(right))
if __name__ == "__main__":
    expression = "((1+(2*3))-4)"
    mp = buildParseTree(expression)
    inorder(mp)
    print(calculateParseTree(mp))
    


   
calculateParseTree这一方式应用了中序解析xml的方法去测算表述式树的值。
 

 

 


优先选择序列

序列是优秀先出的(FIFO),优先选择序列是序列的一种变体,也是优秀先出,可是容许一些重要的每日任务或是特定的每日任务优先选择插到队首或是队尾弹出来。

举一个案子,往优先选择序列里边插进
5,7,3,11
标值小的优先选择级更大,希望弹出来的情况下优先选择级大的会先弹出来来
因此弹出来来的結果是
3,5,7,11 

要完成这一作用,可使用排列来做,每一次插进一数量的情况下将这一数和序列中别的的数开展较为,并将这一数插进到适合的部位。

假如应用井然有序表(即根据排列的方法)完成这一优先选择序列,弹出来的情况下繁杂度是O(1),插进的情况下繁杂度是O(n)


接下去详细介绍应用二叉堆完成优先选择序列,能够做到弹出来和插进的繁杂度全是O(logn)

以便使堆实际操作能维持在多数水准上,就务必选用二叉树构造并且务必自始至终维持二叉树的 均衡 ,即树根上下子树有着同样总数的连接点(对称性);

大家选用 彻底二叉树 的构造来类似完成 均衡
彻底二叉树,叶连接点数最多只出現在最低层和次最底层,并且最低层的叶连接点都持续集中化在最左侧,每一个非叶连接点都是有2个子连接点,数最多会有一个连接点列外

彻底二叉树能够用一个非嵌套循环的目录来表明(便是一个一维的目录)。这棵二叉树从逻辑性上去说成一棵树,可是实际主要表现出去的确是一个目录,因此大家将他称为二叉堆(用目录表明一个堆)。

 

 

这一二叉堆的特点以下:
假定某一个连接点的下标为p,那麼其左子连接点的下标为2p,右子连接点下标为2p+1,父连接点下标为 p//2(往下取整)
树连接点的下标便是目录的下标,连接点的值便是目录的值

全部目录纪录的连接点的次序是纪录着树的从上到下从左往右的次序。

合乎 堆 特性的二叉树,父连接点的值一直比子连接点的值小,叶子连接点的值则较大。换句话说,上边的连接点的值比下边连接点的值要小,因而一切一条相对路径全是一个已排好序的数列。可是同一层中,左侧连接点的值比右侧连接点的值不大不小(上边的连接点比下边的连接点值小,但左侧的连接点不一定比右侧的连接点小)。

 


实际构思:
搭建一个二叉堆类,这一二叉堆便是优先选择序列,这一类有三个关键方式:insert,pop和buildHeap
insert 往优先选择序列尾部插进数据信息    
插进以后,该方式內部会将数据信息调节到适合的部位促使该数据信息所属的下标考虑上边设置的标准
比如 插进的是一个较小的数,可是因为上边要求了子连接点的值比父连接点的大,因此这一数的在树连接点中应当要 上浮 到某一个连接点以考虑上边的标准
该优化算法非常因此冒泡排列1次,可是仅仅对树中的某一条相对路径排列而并不是对全部二叉堆目录的原素排,因此繁杂数为 O(logn)

 

pop    从优先选择序列头顶部弹出来优先选择级最大的原素(便是值最少的原素,也便是根连接点)
当弹出来根连接点以后,根连接点应当补好别的连接点。
大家挑选将二叉堆目录中最终一个原素(最终一个叶连接点)调到根连接点,可是这一原素毫无疑问比下边的每个子连接点大,因此要将该跟连接点 下移 到适合的部位。
该涵数繁杂度也是O(logn)

 

buildHeap  搭建一个二叉堆
便是将一个乱序的目录搭建成二叉堆目录,搭建的构思便是对非叶子连接点的连接点从下到上逐一开展下移,因为下移的繁杂度是 O(logn),必须对n-k个连接点开展下移(在其中k是叶连接点数量),因此buidHeap的繁杂度是 O(nlogn)

 

# 二叉堆完成优先选择序列
class BinaryHeap:
 def __init__(self):
 self.heapList = [0] # 用一个不嵌套循环的目录表明二叉堆(优先选择序列);将第一个原素设成0的目地是以便让根连接点从下标1刚开始,那样便可以考虑“某一个连接点的下标为p,那麼其左子连接点的下标为2p,右子连接点下标为2p+1,父连接点下标为 p//2”这一标准;因此第一个原素0仅仅以便占位性病变
 self.currentSize = 0 # 纪录树连接点数量,它即是连接点数量,也是最终一个连接点的下标
 # 往优先选择序列尾部插进
 def insert(self,item):
 self.heapList.append(item)
 self.currentSize += 1
 # 原素插进尾部后做数据信息上浮
 self.__percUp()
 # 从优先选择序列头顶部弹出来原素
 def pop(self):
 minVal = self.heapList[1] # 这儿不必用pop(1)随后再用insert(1,self.heapList[-1]),由于这2个全是O(n)的繁杂度
 self.heapList[1] = self.heapList[-1]
 self.heapList.pop()
 self.currentSize -= 1
 # 尾部原素补好根连接点后做根连接点下移
 self.__percDown(1) # 传到的1是根连接点下标,表明要下移根连接点
 return minVal
 # 传到一个混乱的目录,依据这一目录搭建出一个二叉堆
 def buildHeap(self,alist):
 self.heapList = [0] + alist[:]
 self.currentSize = len(self.heapList)-1
 # 搭建的构思便是对非叶子连接点的连接点从下到上逐一开展下移实际操作
 i = self.currentSize // 2 # 这一i下标便是第一个开展下移实际操作的下标,也是全部要下移实际操作的连接点中最终一个连接点
 while i 0:
 self.__percDown(i)
 i-=1
 # 上浮最终一个尾部连接点
 # 上浮的构思便是将最终一个连接点和全部先祖连接点的值开展较为,假如该连接点比某一个先祖连接点小则和它交换
 def __percUp(self):
 i = self.currentSize # 最终一个原素的下标
 while i // 2 0: # i//2是下标为i的连接点的父连接点的下标
 fatherIndex = i//2
 if self.heapList[fatherIndex] self.heapList[i]:
 self.heapList[fatherIndex],self.heapList[i] = self.heapList[i],self.heapList[fatherIndex]
 i = fatherIndex
 else:
 break

def __percDown(self,index): # 先较为index连接点下上下子连接点哪一个大,随后再拿上下子连接点中小型的哪个连接点和index连接点比 # 假如index连接点比它大,就和这一子连接点互换 # 比如 index连接点的值是 100 它的左子连接点是99,右子连接点是98,那麼index连接点要和它的右子连接点交换,那样父连接点就变为了98,比左子连接点99小,合乎父连接点比子连接点小的这一标准 stoped = False while index*2 = self.currentSize and not stoped: # index*2是左子连接点的下标,index*2 = self.currentSize表明存有index连接点的左子连接点。假如当今连接点沒有左子连接点,那麼右子连接点毫无疑问都没有,这时下移终止 # print(index) leftIndex = index*2 rightIndex = index*2 + 1 if rightIndex self.currentSize: # 假如沒有右子连接点可是有左子连接点,那麼就拿左子连接点和index连接点较为 comparedIndex = leftIndex else: comparedIndex = leftIndex if self.heapList[leftIndex] = self.heapList[rightIndex] else rightIndex if self.heapList[index] paredIndex]: # 假如index连接点比要较为的连接点的值大则交换,不然不交换 self.heapList[index],paredIndex] = paredIndex],self.heapList[index] index = comparedIndex else: # 假如index连接点比要较为的子连接点的值小,表明能够不用再次下移了,终止循环系统 stoped = True if __name__ == "__main__": bh = BinaryHeap() bh.insert(10) bh.insert(100) bh.insert(1) bh.insert(22) bh.insert(53) bh.insert(34) bh.insert(54) bh.insert(23) bh.insert(11) bh.insert(17) bh.insert(87) print(bh.heapList) while bh.currentSize 0: print(bh.pop()) alist = [10,100,1,22,53,34,54,23,11,17,87] bh2 = BinaryHeap() bh2.buildHeap(alist) while bh2.currentSize 0: print(bh2.pop())

 

 

应用二叉树完成搜索

应用二叉树开展搜索的数称为 二叉搜索树 (BST)

回忆一下,以前大家使用过二种方法完成搜索
1.井然有序表+二分搜索
2.散目录+散列涵数

再加这儿的二叉树搜索便是3种方法

用1句话归纳这一二叉搜索树:比父连接点小的数都会左子树,比父连接点大的数都会右子树
也就是说:连接点A左侧的全部子树和支系的值都比A的值小,连接点A右侧的全部子树和支系的值都比A的值大

实际完成:
最先这一二叉搜索树应用链表构造完成。二叉搜索树自身便是一个链表,这一链表的连接点TreeNode有以下特点:
连接点有三个偏向:left 偏向左子连接点;right 偏向右子连接点;parent 偏向父连接点
连接点能够储存key和value2个特性,表明这一连接点包括的內容。
较为尺寸就是指较为key的尺寸而并不是value的尺寸。


# 更换连接点(用以删掉根连接点时启用并且用根连接点的左子连接点或是右子连接点更换自身) def replaceNode(self,key,value,lc,rc): self.key = key self.value = value self.left = lc self.right = rc if self.hasLeftChild(): self.left.parent = self if self.hasRightChild(): self.right.parent = self essor(self): node = self while node.hasLeftChild(): node = node.left return node # 将后续连接点从原部位挖到 def spliceOut(self): if self.isRightChild(): self.parent.right = None else: if self.hasRightChild(): self.parent.left = self.right self.right.parent = self.parent elif self.isLeaf(): self.parent.left = None # 后续连接点不容易有左连接点 不用分辨 if self.hasLeftChild() # 应用中序解析xml做为迭代更新方式 def __iter__(self): if self.hasLeftChild(): for elem in self.left: # 用for对self.left解析xml的情况下又会启用 self.left 的__iter__ 因此非常因此对__iter__()开展递归启用 yield elem yield self.key if self.hasRightChild(): for elem in self.right: yield elem
# 往BST中加上连接点,加上连接点的标准要考虑key假如超过父连接点的key则做为其右子连接点,假如低于父连接点的key则做为其左子连接点 def put(self,key,value): if self.root: self.__put(self.root,key,value) else: self.root = TreeNode(key,value) self.size += 1 def __put(self,currentNode,key,value): if key currentNode.key: # 假如要插进的key低于现阶段连接点的key,则这一key就放到currentNode的左连接点 if currentNode.hasLeftChild(): self.__put(currentNode.left,key,value) # 假如这一连接点早已有左连接点,则递归 else: # 假如沒有左子连接点则建立左子连接点,而且currentNode的left要偏向这一连接点,而新生儿成的这一连接点的parent要偏向currentNode currentNode.left = TreeNode(key,value,parent=currentNode) else: # 假如要插进的key超过现阶段连接点的key,则这一key就放到currentNode的右连接点 if currentNode.hasRightChild(): self.__put(currentNode.right, key, value) else: currentNode.right = TreeNode(key,value,parent=currentNode) def get(self,key): if self.root: res = self.__get(self.root,key) # 回到的res将会是none,也将会是一个连接点 return res and res.value else: return None def __get(self,currentNode,key): if currentNode == None: # 表明找不着key return None if currentNode.key == key: return currentNode elif currentNode.key key: return self.__get(currentNode.left,key) else: return self.__get(currentNode.right,key) # 依据key删掉某一连接点A # 分成三种状况:1. 连接点A沒有子连接点; 2. 连接点A仅有一个子连接点; 3. 连接点A有2个子连接点 def remove(self,key): # 先获得key所属的连接点 node = self.__get(self.root,key) if node.isLeaf(): # 1. 连接点A沒有子连接点 if node.parent.left == node: node.parent.left = None else: node.parent.right = None node.parent = None elif node.hasAnyChild() and not node.hasBothChild(): # 2. 连接点A仅有一个子连接点 sonNode = node.left if node.hasLeftChild() else node.right if node.isLeftChild(): node.parent.left = sonNode elif node.isRightChild(): node.parent.right = sonNode else: # 要删掉的连接点是根连接点 self.root = sonNode sonNode.parent = None else: # 3. 连接点A有2个子连接点 # 这类状况必须寻找连接点A右侧全部连接点中key最少的子孙后代连接点,并且用该子孙后代连接点更换连接点A。那么一来,连接点A这一部位還是合乎左侧的连接点比A连接点的key小,右侧的连接点比A连接点的key大 # 自身只有是左连接点 succ = node.essor() # 不是会出现左子连接点的,缘故非常简单你自身想一想吧 succ.spliceOut() # 将后续连接点从本来的部位挖到来 node.key = succ.key # 最终用后续连接点更换要删掉的连接点,一旦更换那麼原node即使删掉除 node.value = succ.value def __setitem__(self, key, value): self.put(key,value) def __getitem__(self, key): return self.get(key) def __contains__(self, key): if self.get(key): return True else: return False def __len__(self): return self.size def __iter__(self): if self.root: return self.root.__iter__() if __name__ == "__main__": # import random # dataKey = [i for i in range(1,50,3)] # random.shuffle(dataKey) dataKey = [34, 43, 49, 25, 46, 13, 1, 22, 40, 31, 7, 19, 37, 16, 4, 28, 10] print(dataKey) bst = BST() for i in dataKey: bst.put(i,i/2) for i in bst: print(i,bst[i]) print(bst.get(40)) print(bst.get(25)) print(bst.get(22)) print(bst.get(33)) print("===================================") bst.remove(40) bst.remove(22) bst.remove(25) bst.remove(28) for i in bst: print(i,bst[i])

put方式特性均值为 O(logn)
get方式也是O(logn)

 

最繁杂的remove方式要分三种状况

a. 要删掉的连接点沒有子连接点


b. 要删掉的连接点有一个子连接点

c. 要删掉的连接点有两个子连接点

 

remove方式的繁杂度关键反映在找寻删掉除的连接点和找寻后续连接点,应用来到_get()方式,这一全过程的繁杂度是 O(logn), 而删掉的全过程则是简易的指针取值,繁杂度是O(1)。因此remove方式的繁杂度也是 O(logn)

 

 

AVL 均衡树

针对上边的BTS二叉树,考虑到一种状况,倘若有一串数据信息,它的key是1~10,value是1~10的平方。
倘若我依照key的次序往BST加上连接点会出現一个状况:
这棵BST树的仅有右子树沒有左子树,那样就非常于变为了一个双重链表。

这时put和get方式的特性全是O(n)
这一情况下,二叉搜索树的特性越来越和井然有序链表一样。

 

这时可使用AVL均衡树处理这一难题:

AVL均衡树是在BST的基本上加上了一个特点。这一特点实际是:维持整棵树上下两侧的叠加层数基本一致。

AVL树的均衡特点能够非常好的处理上边说的这一BST次序插进连接点造成特性变差的难题。

AVL树的均衡特点促使树上下两侧的叠加层数同样因而它的put和get方式特性最烂全是O(logn)

怎样完成AVL树的均衡特点?
必须在每一个连接点纪录其 均衡因素 。
这一均衡因素是一个整数金额,是上下子树高宽比差。假如某一连接点的均衡因素 0则表明该连接点下左侧子孙后代连接点的叠加层数超过右侧的叠加层数。相反亦然。

一个BST中每一个连接点的均衡因素都会-1,0,1中间则称这类BST为均衡树(AVL)

比如有一个线形的二叉均衡树,这一树便是上边常说的次序插进。倘若是按序插进的key为1 2 3 
那麼这一BST的构造为:

 1 (-2)
 None 2 (-1)
 None 3 (0)

上边的()中纪录的便是均衡因素。
例如,根连接点右侧有双层,左侧有0层,因此根连接点的均衡因素 = 0-2 = -2 

这一情况下如何调整均衡呢?非常简单,只必须将2做为根连接点,1做为2的左子连接点就可以。这一全过程是对1开展左旋,能变成:

 2 (0)
 1 3 

 

考虑到一种繁杂点的状况

 10 (-2)
 5 20 (-1)
 25 30 (-1)
 None 40 (0)

这类状况如何将他变为均衡的呢?(只需让肯定值超出1的均衡因素调节为1之内就可以,因此如今要将10这一根连接点的均衡因素变成-1就可以)
这时有二种作法:
1.将20升职为根连接点,10这一连接点沿着20这一连接点的左侧一直降至底就可以
这时变为:

 20 (0)
 -------
 (2)25 30 (0)
 --- ---
 | | | |
 (1)10 None None 40 (0)
 (0)5 None

这类作法得话 20的均衡因素变为了0,可是25的均衡因素有变为了2

 

2.将10做为20的左子连接点,25做为10的右子连接点

 20 (0)
 -------
 10 30 (0)
 --- ---
 | | | |
 5 25 None 40 (0)

恰当的作法应当是法2
这一全过程便是对10的一个左旋

 

有一种较为独特的状况:

 10 (-2)
 None 20 (1)
 15 None

倘若依照上边的方式去做左旋的调整,能变成:

 20 (2)
 10 None
 None 15 

 

因此假如碰到这类状况,应当20这一连接点开展右旋,变为

 10 (-2)
 None 15 (-1)
 None 20

再对10开展左旋:

          15 
          |
         ---
        |   |
        10  20  

这类状况称作 之 型子树

PS:之上全部调节的全过程,全是在往树里边加上完连接点以后才刚开始的。

一个连接点A的右侧叠加层数超过左侧称作右重;相反是左重
连接点A右重则必须对连接点A开展左旋;连接点A左重则必须对连接点A开展右旋;

 

 

张柏沛IT技术性blog > 数据信息构造与优化算法python語言完成(五) 树

点一下拷贝转截该一篇文章



联系我们

全国服务热线:4000-399-000 公司邮箱:343111187@qq.com

  工作日 9:00-18:00

关注我们

官网公众号

官网公众号

Copyright?2020 广州凡科互联网科技股份有限公司 版权所有 粤ICP备10235580号 客服热线 18720358503

技术支持:小程序制作