Awesome

LemonSaaS

python说二叉树-乐酱出品

可爱有蒙圈的乐酱来了,今天给大家介绍的是很多人听过的二叉树,说到二叉树呢,乐酱很喜欢的,因为很多地方用到。

《python说二叉树-乐酱出品》

前提知识

在这个项目中,我们先来讲讲列表和链表。

在每种集合中我们希望有效执行以下操作:

  1. 将新数据(值)插入集合中
  2. 查看给定值是否在集合中
  3. 从集合中删除值

以上操作前提是排序,排序可以优化搜索。插入或移除操作时,搜索使用频率又很高。

我们假设需要对集合进行排序,这意味着项目中需要使用到小于、大于、等于等比较运算符。简单起见,我们使用以下前提:

  1. 集合中的值是唯一的
  2. 值是简单的整数。在实际情况中,值可以是指向数据库中的数据结构或记录的指针。

一、列表

A、插入操作

collection = [3, 6, 17, 9]
collection
[3, 6, 17, 9]

collection.append(5)
collection
[3, 6, 17, 9, 5]

B、查值

如果python没有in运算符,我们可以创建一个。请注意,这是一个递归函数。它也可以使用while或for循环编写,但是这种递归在后面会被用到。

def contains(collection,value):
if not collection: return False # collection empty
elif value == collection[0]:
return True # value is in the first slot
else:
return contains(collection[1:], value) # value is somewhere futher ?

contains(collection, 5)
True
contains(collection, 10)
False
def contains(collection,value):
if not collection:
return False
elif value == collection[0]:
return True
elif value < collection[0]:
return False
else:
return contains(collection[1:], value)

C、删除集合中的某个值,这里我们使用for循环来查找分隔点。

def remove(collection, value):
for i in range(len(collection)):
if value == collection[i]:
return collection[0:i] + collection[i+1:] # remove and rejoin

二、链表

链表:包含值和指向下一个节点的指针。链表仅在排序时才有意义。

A、插入一个节点

import lists
print lists.sampleList # linked list is a nested
[10, [20, [30, [40, None]]]]

将节点插入排序链表中传统方式是操作指针。这里有三种情况:节点在链表开头、末尾或中间的某个位置。

def insert(nod0, value):
if nod0 is None:
return [value, None] # new list created
elif nod0[0] > value:
return [value, nod0[1]] # insert as first node
else:
nod = nod0
while nod[1]:
if nod[1][0] >= value: # next node in the chain?
ins = (value, nod[1]) # build a new node and
nod[1] = ins # squeeze it in
break
else:
nod = nod[1]
if nod[1] is None:
nod[1] = (value, None) # becomes the tail
return nod0
# 简洁型代码
def insert2(l, value):
if l is None:
return [value, None]
elif l[0] > value:
return [value, l]
else:
return [l[0], insert2(l[1], value)]

函数lists.showList以更自然的方式打印链表。每个节点id的最后4位数和节点值用”:”分隔。

def show_list(l, accum=""):
if l is None:
return accum
else:
if accum:
sep = "--> "
else:
sep = ""
accum += sep + "%d:%s" % (id(l) % 10000, l[0]) # include last 4 dig of id
return show_list(l[1], accum)

请注意:l1和l2在插入点(值25)之后共享相同的节点。l2有一个新的前端,这种“尾端”的共享将被证明是二叉树效率的关键特征。

l1 = lists.sampleList
print(l1)
[10, [20, [30, [40, None]]]]
l2 = lists.insert2(l1, 25)
print(l2)
print(lists.showList(l1))
7472:10 --> 8696:20 --> 2280:30 --> 2208:40
print(lists.showList(l2))
3728:10 --> 3440:20 --> 2792:25 --> 2280:30 --> 2208:40
import lists

lists.testFunc(lists.insert2)
<function insert2 at 0x7f5a2d3f9848>
[10, [20, [30, [40, None]]]]
7456:10 --> 7096:20 --> 3512:30 --> 2288:40

input value:25
[10, [20, [25, [30, [40, None]]]]]
7672:10 --> 7528:20 --> 7600:25 --> 3512:30 --> 2288:40

B、查值–通过id函数查看链表中的值

>>> a = 541
>>> id(a)     # shows value *541* resides in memory at 36300744
36300744
>>> b = a
>>> id(b)
36300744     # b == a since they point at the same value
>>> id(b), b
(36300744, 541)
>>> a = 542  # changing the value of *a*
>>> id(a), a
(36300768, 542)

函数lists.showLinks使用id来显示链。请注意,即使值None也有对应9332928的窝。

>>> l = lists.sampleList
>>> lists.showLinks(l)   # id of node, value, id of next node
140107872758600: 10 140107872758672
140107872758672: 20 140107872685088
140107872685088: 30 140107872683864
140107872683864: 40 9392928
>>> def contains(l, value) :
        if  l == None      : return False
        elif l[0] == value : return True
        else               : return contains(l[1], value)

三、链表的元组

使用insert、contains和delete函数功能,我们不需要修改现有节点。2个元素链表可以用2个元素元组替换。出于两个原因这是个好主意:

  1. 元组使用比链表更少的内存
  2. 元组不能修改节点

对链表进行修改会导致细微错误,尤其在并发进程共享链表的情况下。

可以单独查看python程序lists.py和tuples.py。他们非常相似。

四、二叉树

二叉树就像链表一样,只不过他是二维的。每个节点都有一个值和两个指向子树的指针,一个左边,一个右边。两个子树可以是值None,也可以是另一个二次树的根节点。左子树仅包含其值小于父节点的节点,右子树节点的值则更大。

为了方便讨论,在引用节点时,我将使其值更容易辨识。现在来看一个二叉树(二叉树是递归数据结构):

《python说二叉树-乐酱出品》

该树表示如下:

(50, (30, (20, (10, None, None), None), (40, None, None)),
     (80, (70, (60, None, None), None), (90, None, None)))

你可以看到到节点20和70没有任何右节点, 节点10、40、60、90根本没有子树。

树是平衡的,虽然树中有九个节点,但每个节点可以从三个步骤或更少的步骤到达。

我们来对二叉树进行三步操作(是否包含、插入新值并删除)。

>>> def contains(tree, target) :
        if tree == None : return False
        (value,left,right) = tree
        if value == target : return True
        elif value > target : return contains(left,target)
        else                : return contains(right,target)

函数contains从根节点开始遍历,每个步骤向左或向右。如果落在具体目标值的节点上,则返回True;到达终点则返回False。

>>> from bintree import contains
>>> mytree = (50, (30, (20, (10, None, None), None), (40, None, None)),
...         (80, (70, (60, None, None), None), (90, None, None)))
>>> contains(mytree, 60)
True
>>> contains(mytree, 65)
False

A、插入新节点

插入新节点需要找到正确的位置,然后再嵌套返回中构建链表、模仿原始节点,但实际上创建了一个主要与旧树合并的新树。

>>> def insert(tree, newValue) : 
        if not tree : return (newValue,None,None)
        (value,left,right) = tree
        if value == None : return (newValue,None,None)
        if value == newValue : return tree  # already there
        elif newValue < value : 
             return (value, insert(left,newValue), right)
        else :
             return (value, left, insert(right, newValue))

insert函数中每种判断情况的返回我们创建一个连接到他下面的节点的新节点。下图是插入值65的示例。

《python说二叉树-乐酱出品》

黄色节点来自原始树,你可以通过id函数检查。只用从我们的新值返回到顶部的红色节点是使用递归返回的原始值构建的新节点。只要有指向原始树根的指针,它就会继续存在。新树有一个新的根,并且可以与原始树合并。

现在,再次从第一个树开始,让我们删除节点值40。这需要值30和50的新节点,黄色节点仍是原始节点。

>>> mytree
(50, (30, (20, (10, None, None), None), (40, None, None)),
(80, (70, (60, None, None), None), (90, None, None)))
>>> oldtree = mytree
>>> from bintree import insert
>>> newtree = insert(oldtree, 65)
>>> newtree
(50, (30, (20, (10, None, None), None), (40, None, None)),
(80, (70, (60, None, (65, None, None)), None), (90, None, None)))
>>> oldtree
(50, (30, (20, (10, None, None), None), (40, None, None)),
(80, (70, (60, None, None), None), (90, None, None)))

所以,没有副作用!

B、删除节点

删除节点有点复杂。以下是删除节点值40的效果图。

《python说二叉树-乐酱出品》

当删除子树的根时,其他节点之一必须取代它。

新的根节点必须保持条件。

右子树中最小节点工作正常,为什么?它的值仍然大于左子树中的任何其他节点。如果任一子树为空,则可以使用更简单的过程。以下是代码:

>>> def delete(tree, target) :
        if tree == None : return None
        (value,left,right) = tree
        if target == value : # delete this node
            if left and right :
                swp = minval(right)
                print "Swap val", swp
                return (swp, left, delete(right,swp))
            if left == None : return right
            if right == None : return left
        elif target < value :
              return (value, delete(left,target), right)
        elif target > value :
              return (value, left, delete(right,target))

>>> def minval(tree) :
        (val, left, right) = tree
        if left == None : return val
        else : return minval(left)

如果我们找到了要删除的节点(if target == value),并且如果左右分支都存在,那么我们使用函数minval在右侧找到最小值。

创建一个新节点(return swp, left, delete(right,swp) ),并建立一个新的分支(红色)回到顶部。

如果左侧或右侧分支为空,则另一个分支可以简单地取代已删除的节点(if left == None : return right 50 if right == None : return left)。“elif target < value ”之后的代码遍历树以找到要删除的节点。

C、平衡一棵树

最佳树是可以节省时间。在具有1024个节点的平衡树中,每个节点在根的10步内。删除和插入也仅通过重建此长度的新路径来影响树。但如果插入序列不是随机的,那么这种效率可能会丢失。

下一张图插入了2个节点。他们让树有些失去平衡。而不是所有节点都在距根节点3步之内,节点62距离五步之遥。

《python说二叉树-乐酱出品》

重新平衡后,所有节点再次距离根节点不超过3步。

《python说二叉树-乐酱出品》

以下是实现这一目标的功能。我们的想法是将树转换为已排序的python链表。二叉树的最佳根位于链表的中间。获取根目录左侧的值,并为其左侧连接创建子树。右侧的值为其右侧连接创建子树。递归地执行此操作。

>>> def values(tree) :
        if not tree : return []
        (value,left,right) = tree
        return values(left) + [value] + values(right)

>>> def balance(tree) : 
        return balance2(None, values(tree))

>>> def balance2(btree, sorted) : 
        if not sorted : return btree
        split = len(sorted)/2
        btree = insert (btree,sorted[split])     # midpoint
        btree = balance2(btree,sorted[0:split])  # left side
        btree = balance2(btree,sorted[split+1:]) # right side

如果某个数字n的节点为2^n-1,那么树将完全平衡。否则,从右到左在底部会有一部分用行填充。

D、包装

这些操作二叉树的基本算法非常简单有效。除此之外,二叉树可以作为非SQL数据库的索引。能够将多个索引保存到数据库中并且同一索引的多个版本允许我们进行更改,并且还可以简单恢复早期指针来撤销这一更改。

总之,如果可能,应始终使用递归算法处理递归数据结构。python语言使之更简单。而且,虽然有学习曲线,但绝对值得付出努力。

打赏
微信
支付宝
微信二维码图片

微信扫描二维码打赏

支付宝二维码图片

支付宝扫描二维码打赏

本站文章未说明转载即为原创,转载请注明来源,LemonSaaS-A » python说二叉树-乐酱出品,并请保留声明!
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注