算法_树

青旅半醒 2023-02-18 08:20 114阅读 0赞

## 树 ##

应用领域：操作系统、图像学、数据库系统、计算机网络

树是一种非线性的数据结构，数据结构树也分为：根、枝和叶三个部分，一般图示数据结构把根放在上面，叶放在下面

*  分类体系是层次化，越接近顶部的层越普遍，越接近底部的层越独特
 *  一个节点的子节点与另一个节点的子节点相互之间是隔离、独立的
 *  每一个叶节点都具有唯一性

### 相关术语 ###

![树][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70]

1.  节点Node：组成树的基本部分
    
    每个节点具有名称，或“键值”，节点还可以保存额外数据项，数据项根据不同的应用而变
2.  边Edge：边是组成树的另一个基本部分
    
    每条边恰好连接两个节点，表示节点之间具有关联，边具有出入方向；每个节点（除根节点）恰有一条来自另一节点的入边；每个节点可以有多条链接到其它节点的出边（顶层没有入边，底层没有出边）
3.  跟Root：树种唯一一个没有入边的节点
4.  路径Path：由边依次连接在一起的节点的有序列表
5.  子节点Children：入边均来自同一个节点的若干节点
6.  父节点Parent：一个节点时其所有出边所连接节点
7.  兄弟节点Sibling：具有同一个父节点的节点之间
8.  子树Subtree：一个节点和其所有子孙节点，以及相关边的集合（BDE/CF/D/E/F）
9.  叶节点Leaf：没有子节点的节点
10. 层级Level：从根节点开始达到一个节点的路径，所包含的边的数量
    
    D的层级为2（从根开始经过B到D），跟节点的层级为0
11. 高度：树中所有节点的最大层级

### 树的定义 ###

1.  节点和边的集合
    
    树由若干节点，以及两两连接节点的边组成，并有如下性质：
    
     *  其中一个节点被设定为根
     *  每个节点n（除根节点），都恰连接一条来自节点p的边，p是n的父节点
     *  每个节点从根开始的路径是唯一的，如果每个节点最多有两个子节点，这样的树称为“二叉树”
2.  递归
    
    树：
    
     *  空集
     *  由根节点及0个或多个子树构成（其中子树也是树），每个子树的根到根节点具有边相连

## 实现树 ##

### 嵌套列表 ###

递归的嵌套列表实现二叉树，由具有3个元素的列表实现：\[root, left, right\]

*  第1个元素为根节点的值
 *  第2个元素是左子树
 *  第3个元素是右子树
    
    根是myTree\[0\]，左子树myTree\[1\]，右子树myTree\[2\]

嵌套列表法的优点：

*  子树的结构与树相同，是一种递归数据结构
 *  很容易扩展到多叉树，仅需要增加列表元素即可

![嵌套列表树][20200616183907737.png]

# 创建仅有根节点的二叉树
    def BinaryTree(r):
        # 左右子树是空列表
        return [r, [], []]
    
    # 将新节点插入树种作为其直接的左子节点
    def insertLeft(root, newBranch):
        # 把左子树pop出来
        t = root.pop(1)
        # 如果大于1 说明有子树
        if len(t) > 1:
            root.insert(1, [newBranch, t, []])
        else:
            root.insert(1, [newBranch, [], []])
        return root
    
    # 将新节点插入树种作为其直接的右子节点
    def insertRight(root, newBranch):
        t = root.pop(2)
        if len(t) > 1:
            root.insert(2, [newBranch, [], t])
        else:
            root.insert(2, [newBranch, [], []])
        return root
    
    # 取得根节点
    def getRootVal(root):
        return root[0]
    
    # 设置根节点
    def setRootVal(root, newVal):
        root[0] = newVal
    
    # 返回左子树
    def getLeftChild(root):
        return root[1]
    
    # 返回右子树
    def getRightChild(root):
        return root[2]
    
    r = BinaryTree(3)
    insertLeft(r, 4)
    insertLeft(r, 5)
    insertRight(r, 6)
    insertRight(r, 7)
    l = getLeftChild(r)
    print(l) # [5, [4, [], []], []]
    setRootVal(l, 9)
    print(r) # [3, [9, [4, [], []], []], [7, [], [6, [], []]]]
    insertLeft(l, 11)
    print(r) # [3, [9, [11, [4, [], []], []], []], [7, [], [6, [], []]]]
    print(getRightChild(getRightChild(r))) # [6, [], []]

![二叉树图示][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 1]

### 节点链接法 ###

每个节点保存根节点的数据项，以及指向左右子树的链接

![节点链接法][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 2]

class BinaryTree:
        def __init__(self, rootObj):
            # key保存根节点数据项
            self.key = rootObj
            # left/rightChild保存指向左/右子树的引用（同样是BinaryTree）
            self.leftChild = None
            self.rightChild = None
    
        def insertLeft(self, newNode):
            if self.leftChild == None:
                self.leftChild = BinaryTree(newNode)
            else:
                # 当前存在子左节点，我们插入一个节点并将已存在的子节点降级
                t = BinaryTree(newNode)
                t.leftChild = self.leftChild
                self.leftChild = t
    
        def insertRight(self, newNode):
            if self.rightChild == None:
                self.rightChild = BinaryTree(newNode)
            else:
                t = BinaryTree(newNode)
                t.rightChild = self.rightChild
                self.rightChild = t
    
        def getRightChild(self):
            return self.rightChild
    
        def getLeftChild(self):
            return self.leftChild
    
        def setRootVal(self, obj):
            self.key = obj
    
        def getRootVal(self):
            return self.key
    
    r = BinaryTree('a')
    r.insertLeft('b')
    r.insertRight('c')
    r.getRightChild().setRootVal('hello')
    r.getLeftChild().insertRight('d')
    
    print(r.getRootVal()) # a
    print(r.getLeftChild().getRootVal()) # b
    print(r.getLeftChild().getRightChild().getRootVal()) # d
    print(r.getRightChild().getRootVal()) # hello

![图示][2020061711020362.png]

## 树的应用：表达式解析 ##

将树用于表示语言中句子，可以分析句子的各种语法成分，对句子的各种成分进行处理

*  语法分析树：主谓宾，定状补

![主谓宾定状补][20200617123750732.png]

我们还可以将表达式表示为树结构

*  叶节点保存操作数，内部节点保存操作符
 *  全括号表达式：`((7+3)*(5-2))`，由于括号存在，需要计算 `*` 的7+3和5-2，表达式层次决定计算的优先级，越底层的表达式，优先级越高
 *  树种每个子树都表示一个子表达式
    
    ![表达式][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 3]

### 创建表达式解析数的过程 ###

首先，全括号表达式要分解为单词Token列表，其中单词分为括号“`（）`”、操作符“`+-*/`”和操作数“`0-9`”这几类

对于全括号表达式：`（3+（4*5））`，分解为单词表：\[’(’, ‘3’, ‘+’, ‘(’, ‘4’, ‘\*’, ‘5’,’)’, ‘)’\]

*  每当读到一个左括号时，就代表着一个新的表达式，我们需要创建一个与之相对应的新的树
 *  每当读到一个右括号时，就代表这一个表达式的结束
 *  操作数将成为叶节点和他们所属的操作符的子节点
 *  每个操作符都应该有一个左子节点和一个右子节点

![步骤1][1]

![步骤2][2]

![步骤3][3]

### 创建表达式解析数的规则 ###

从左到右扫描全括号表达的每个单词，依据规则建立解析数

*  如果当前单词是“（”：为当前节点添加一个新节点作为其左子节点，当前节点下降为这个新节点
 *  如果当前单词是操作符`“+，-，*，/”`：将当前节点的值设为此符号，为当前节点添加一个新节点作为其右子节点，当前节点下降为这个新节点
 *  如果当前单词是操作数：将当前节点的值设为此树，当前节点上升到父节点
 *  如果当前单词是“）”：则当前节点上升到父节点

通俗理解：左括号向左生儿子，右括号向上找爸爸，运算符号生二胎，遇到数字触底反弹

### 创建表达式解析树的思路 ###

创建树过程中关键的是对当前节点的跟踪

*  创建左右子树可调用 insertLeft/Right
 *  当前节点设置值，可以调用setRootVal
 *  下降到左右子树可调用getLeft/RightChild
 *  但是，上升到父节点，这个没有办法支持

我们可以用一个栈来记录跟踪父节点

*  当前节点下降时，将下降前的节点push入栈
 *  当前节点需要上升父节点时，上升到pop出栈的节点即可

# pip install pythonds
    from pythonds.basic.stack import Stack
    from pythonds.trees.binaryTree import BinaryTree
    
    
    def buildParseTree(fpexp):
        # 字符串的全括号表达式
        fplist = fpexp.split()
        pStack = Stack()
        eTree = BinaryTree('')
        # 树因为需要上升到根节点，当前节点先入栈
        pStack.push(eTree)
        currentTree = eTree
        for i in fplist:
            # 表达式开始：左括号向左生儿子
            if i == '(':
                currentTree.insertLeft('')
                # 把当前节点下降到左子节点
                pStack.push(currentTree)
                currentTree = currentTree.getLeftChild()
            elif i not in ['+', '-', '*', '/', ')']:
                # 把当前节点设置成操作数
                currentTree.setRootVal(int(i))
                # 设置完操作数，触底反弹上升一个节点
                parent = pStack.pop()
                currentTree = parent
            elif i in ['+', '-', '*', '/']:
                # 把当前节点设置成操作符
                currentTree.setRootVal(i)
                # 操作符向右生二胎
                currentTree.insertRight('')
                pStack.push(currentTree)
                currentTree = currentTree.getRightChild()
            elif i == ')':
                # 表达式结束：右括号向上找爸爸
                currentTree = pStack.pop()
            else:
                raise ValueError
        return eTree

### 创建表达式解析树求值的思路 ###

*  由于二叉树BinaryTree是一个递归数据结构，自然可以用递归算法来处理
 *  求值递归函数evaluate，由前述对子表达式的描述，可从树的底层子树开始，逐步向上层求值，最终得到整个表达式的值
 *  求值函数evaluate的递归三要素
    
    1.  基本结束条件：叶节点是最简单的子树，没有左右子节点，其根节点的数据项即为子表达式的值
    2.  缩小规模：将表达式树分为左子树、右子树，即为缩小规模
    3.  分别调用evaluate计算左子树和右子树的值，然后将左右子树的值依据根节点的操作符进行计算，从而得到表达式的值
 *  增加程序可读性技巧：函数引用
    
        >>> import operator
        >>> operator.add
        <built-in function add>
        >>> operator.add(1,2)
        3
        >>> op = operator.add
        >>> n = op(1,2)
        >>> n
        3

**表达式解析树求值代码实现：**

import operator
    def evaluate(parseTree):
        opers = { '+':operator.add, '-':operator.sub,
                '*':operator.mul, '/':operator.truediv}
        # 缩小规模
        leftC = parseTree.getLeftChild()
        rightC = parseTree.getRightChild()
    
        if leftC and rightC:
            fn = opers[parseTree.getRootVal()]
            # 递归调用
            return fn(evaluate(leftC), evaluate(rightC))
        else:
            # 基本结束条件
            return parseTree.getRootVal()
    
    print(evaluate(buildParseTree('( 3 + ( 4 * 5 ) )'))) # 23

## 树的遍历 ##

对于一个数据集中所有数据项进行访问的操作称为“遍历Traversal”

*  前序遍历（preorder）：先访问**根**节点，再递归地前序访问**左子树**、最后前序访问**右子树**
 *  中序遍历（inorder）：先递归地中序访问**左子树**，再访问**根**节点，最后中序访问**右子树**
 *  后序遍历（postorder）：先递归地后序访问**左子树**，再后序访问**右子树**，最后访问**根**节点

前序遍历的例子：

![前序遍历][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 4]

from pythonds.trees.binaryTree import BinaryTree
    
    # 前序遍历
    def preorder(tree):
        if tree:
            print(tree.getRootVal())
            preorder(tree.getLeftChild())
            preorder(tree.getRightChild())
    
    # 后序遍历
    def postorder(tree):
        if tree:
            preorder(tree.getLeftChild())
            preorder(tree.getRightChild())
            print(tree.getRootVal())
    
    # 中序遍历
    def inorder(tree):
        if tree:
            preorder(tree.getLeftChild())
            print(tree.getRootVal())
            preorder(tree.getRightChild())

在BinaryTree类里实现前序遍历，需要加入子树是否为空的判断

def preorder(self):
        print(self.key)
        if self.leftChild:
            self.leftChild.preorder()
        if self.rightChild:
            self.rightChild.preorder()

后序遍历：表达式求值

def postordereval(tree):
        opers = { '+':operator.add, '-':operator.sub,
                '*':operator.mul, '/':operator.truediv}
        res1 = None
        rse2 = None
        if tree:
            res1 = postordereval(tree.getLeftChild())
            res2 = postordereval(tree.getRightChild())
            if res1 and res2:
                return opers[tree.getRootVal()](res1, res2)
            else:
                return tree.getRootVal()

采用中序遍历递归算法来生成全括号中缀表达式

*  如果对解析树进行一个简单的中序遍历，我们将得到没有圆括号的原始表达式。我们可以修改基础的中序遍历的算法使我们复原全括号表达式
 *  在递归访问左子树之前输出左括号，然后访问右子树之后输出右括号

def printexp(tree):
        sVal = ''
        if tree:
            sVal = '(' + printexp(tree.getLeftChild())
            sVal = sVal + str(tree.getRootVal())
            sVal = sVal + printexp(tree.getRootVal()) + ')'
        return sVal

注意：`printexp` 函数对每个数字也加了括号，这些括号显然没必要加

## 优先队列 ##

*  队列有一种变体称为“优先队列”。优先队列的出队跟队列一样从队首出队
 *  但在优先队列内部，数据项的次序是由“优先级”来确定：
    
    1.  高优先级的数据排在队首，而低优先级的数据项则排在后面
    2.  优先队列的入队操作比较复杂，需要将数据项根据其优先级尽量排在队列前方

**二叉堆Binary Heap实现优先队列**

*  实现优先队列的经典方案是采用二叉堆数据结构，二叉堆能够将优先队列的入队和出队复杂度都保持在O(log n)
 *  二叉堆有趣之处在于，其逻辑结构上像二叉树，却是用非嵌套的列表来实现的
 *  最小key排在队首的称为“最小堆min heap”

> ADT BinaryHeap的操作定义如下：
> 
>  *  BinaryHeap()：创建一个空二叉堆对象
>  *  insert(k)：将新key加入到堆中
>  *  findMin()：返回堆中的最小项，最小项仍保留在堆中
>  *  delMin()：返回堆中的最小项，同时从堆中删除
>  *  isEmpty()：返回堆中是否为空
>  *  size()：返回堆中key的个数
>  *  buildHrap(list)：从一个key列表创建新堆

### 用非嵌套列表实现二叉堆 ###

二叉堆本质上是一种完全二叉树，它分为两种类型：

1.  最大堆
2.  最小堆

*  为了使堆操作保持在对数水平上，就必须采用二叉树结构
 *  同样。如果要使操作始终保持在对数数量级上，就必须始终保持二叉树的“平衡”，树根左右子树拥有相同数量的节点
 *  一个二叉树的所有非叶节点都存在左孩子和右孩子，并且所有叶子节点都在同一个层级上，那么这个树就是满二叉树
 *  满二叉树 k层 必须包含 2^(k-1) 个节点
    
    ![满二叉树][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 5]
 *  对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号为从1到n。如果这个树所有节点和同样深度的满二叉树的编号从1到n的节点位置相同，则这个二叉树为完全二叉树
 *  如果 k层不包含 2^(k-1) 个节点
 *  我们采用“完全二叉树”的结构来近似实现“平衡”
 *  完全二叉树由于其特殊性，可以用非嵌套列表以简单的方式实现，如果节点的下标为p，那么其左子节点下标为2p，右子节点下标为2p+1，其父节点下标为p//2
    
    ![完全二叉树][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 6]

通俗理解：满二叉树要求所有分支都是满的，而完全二叉树只需要保证最后一个节点之前的节点都齐全即可

### 堆次序Heap Order ###

*  任何一个节点x，其父节点p中的key均小于x中的key。这样，符合“堆”性质的二叉树，其中任何一条路径，均是一个已排序数列，根节点的key最小

### 二叉堆操作的实现 ###

*  二叉堆初始化，采用一个列表来保存堆数据，其中表首下标为0的项无用，但为了后面代码可以用到简单的整数乘除法，仍保留它
 *  `inser(key)` 方法，为了保持“完全二叉树”的性质，新key应该添加到列表末尾
 *  `inser(key)` 方法，新key加在列表末尾，显然无法保持“堆”次序，虽然对它路径的次序没有影响，但对于其到跟的路径可能破坏次序
 *  `inser(key)` 方法，需要将新key沿着路径来“上浮”到其正确位置。注意：新key的“上浮”不会影响其它路径节点的“堆次序”
    
    ![上浮][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 7]
 *  `delMin()` 方法，移走整个堆中最小的key：根节点heapList\[1\]为了保持“完全二叉树”的性质，只用最后一个节点来代替根节点
 *  `delMin()` 方法，简单的替换，还是破坏了“堆”次序
    
    解决方法：将新的根节点沿着一条路径“下沉”，直到比两个子节点都小
 *  `delMin()` 方法，“下沉”路径的选择：如果比子节点大，那么选择较小的子节点交换下沉
    
    ![节点下沉][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 8]
 *  `buildHeap(lst)` 方法，从无序表生成“堆”
    
    我们最自然的想法是：用insert(key)方法，将无序表的数据项逐个insert到堆中，但这么做的总代价是O(nlog n)
    
    其实，用“下沉”法，能够将总代价控制在O(n)
    
    ![无序表生成堆][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 9]

class BinHeap:
        def __init__(self):
            self.heapList = [0]
            self.currentSize = 0
    
        def percUp(self, i):
            while i // 2 > 0:
                # 如果比父节点小，跟父节点交换
                if self.heapList[i] < self.heapList[i//2]:
                    temp = self.heapList[i//2]
                    self.heapList[i//2] = self.heapList[i]
                    self.heapList[i] = temp
                i //= 2
    
        def percDown(self, i):
            # 沿着路径往下走
            while (i*2) <= self.currentSize:
                mc = self.minChild(i)
                # 只要比最小的子节点大就交换
                if self.heapList[i] > self.heapList[mc]:
                    tmp = self.heapList[i]
                    self.heapList[i] = self.heapList[mc]
                    self.heapList[mc] = tmp
                i = mc
    
        def minChild(self, i):
            # 如果只有唯一子节点，返回该节点
            if i*2+1 > self.currentSize:
                return i*2
            else:
                # 如果有两个子节点，返回较小的节点
                if self.heapList[i*2] < self.heapList[i*2+1]:
                    return i*2
                else:
                    return i*2+1
    
        def insert(self, k):
            # 添加到末尾
            self.heapList.append(k)
            self.currentSize = self.currentSize+1
            # 新key 上浮
            self.percUp(self.currentSize)
    
        def delMin(self):
            # 移走堆顶
            retval = self.heapList[1]
            self.heapList[1] = self.heapList[self.currentSize]
            self.currentSize -= 1
            self.heapList.pop()
            # 新顶下沉
            self.percDown(1)
            return retval
    
        def buildHeap(self, alist):
            # 从最后节点的父节点开始 叶节点无需下沉
            i = len(alist)//2
            self.currentSize = len(alist)
            self.heapList = [0] + alist[:]
            print(len(self.heapList), i)
            while (i > 0):
                print(self.heapList, i)
                self.percDown(i)
                i -= 1
            print(self.heapList, i)
    
    b = BinHeap()
    b.insert(5)
    b.insert(9)
    b.insert(14)
    b.insert(18)
    b.insert(33)
    b.insert(17)
    b.insert(27)
    b.insert(7)
    print(b.heapList) # [0, 5, 7, 14, 9, 33, 17, 27, 18]
    
    c = [5, 9, 14, 18, 33, 17, 27, 7]
    b.buildHeap(c)
    # 9 4
    # [0, 5, 9, 14, 18, 33, 17, 27, 7] 4
    # [0, 5, 9, 14, 7, 33, 17, 27, 18] 3
    # [0, 5, 9, 14, 7, 33, 17, 27, 18] 2
    # [0, 5, 7, 14, 9, 33, 17, 27, 18] 1
    # [0, 5, 7, 14, 9, 33, 17, 27, 18] 0

## 二叉搜索树Binary Search Tree ##

在ADT Map的实现方案中，可以采用不同的数据结构和搜索算法来保存和查找Key

*  有序表数据结构+二分搜索算法
 *  散列表数据结构+散列及冲突解决算法
 *  二叉树保存key，实现key的快速查找

### 二叉搜索树的性质 ###

*  比父节点小的key都出现在左子树，比父节点大的key都出现在右子树
    
    ![二叉查找树][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 10]

### 二叉搜索树实现 ###

采用“节点与引用”表示法实现二叉搜索树，它类似实现链表和表达式树时采用的方法。不过，由于必须创建并处理一颗空的二叉搜索树，因此我们将使用两个类。一个称作BinarySearchTree，另一个称作TreeNode

BinarySearchTree类有一个引用，指向作为二叉搜索树根节点的TreeNode类。大多数情况下，外面这个类的方法只是检查树是否为空。如果树中有节点，请求就会被发往BinarySearchTree类的私有方法，这个方法以根节点作为参数

**BinarySearchTree类**

**TreeNode类**

class TreeNode:
        def __init__(self, key, val, left=None, right=None, parent=None):
            self.key = key
            self.payload = val
            self.leftChild = left
            self.rightChild = right
            self.parent = parent
    
        def hasLeftChild(self):
            return self.leftChild
    
        def hasRightChild(self):
            return self.rightChild
    
        def isLeftChild(self):
            return self.parent and self.parent.leftChild == self
    
        def isRightChild(self):
            return self.parent and self.parent.rightChild == self
    
        def isRoot(self):
            return not self.parent
    
        def isLeaf(self):
            return not (self.rightChild or self.leftChild)
    
        def hasAnyChildren(self):
            return self.rightChild or self.leftChild
    
        def hasBothChildren(self):
            return self.rightChild and self.leftChild
    
        def replaceNodeData(self, key, value, lc, rc):
            self.key = key
            self.payload = value
            self.leftChild = lc
            self.rightChild = rc
            if self.hasLeftChild():
                self.leftChild.parent = self
            if self.hasRightChild():
                self.rightChild.parent = self

*  put(key, val) 方法：插入key构造BST。首先看BST是否为空，如果一个节点都没有，那么key成为根节点root。否则，就调用一个递归函数 \_put(key, val, root)来放置key
 *  \_put(key, val, currentNode) 方法：
    
    如果key比currentNode小，那么 \_put到左子树
    
     *  如果没有左子树，那么key就成为左子节点
    
    如果key比currentNode大，那么 \_put到右子树
    
     *  如果没有右子树，那么key就成为右子节点
 *  通过 \_\_setitem\_\_方法调用put方法来重载\[\]运算符（索引赋值）
    
    如此一来，就可以像myZipTree\[‘Plymouth’\] = 55446，这样的Python语句，就如同访问Python的字典一样
    
    插入一个节点键值 Key=19
    
    ![插入][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 11]
    
        def put(self, key, val):
                if self.root:
                    self._put(key, val, self.root)
                else:
                    self.root = TreeNode(key, val)
                self.size += 1
        
            def _put(self, key, val, currentNode):
                if key < currentNode.key:
                    if currentNode.hasLeftChild():
                        self._put(key, val, currentNode.leftChild)
                    else:
                        currentNode.leftChild = TreeNode(key, val, parent=currentNode)
                else:
                    if currentNode.hasRightChild():
                        self._put(key, val, currentNode.rightChild)
                    else:
                        currentNode.rightChild = TreeNode(key, val, parent=currentNode)
        
            def __setitem__(self, key, val):
                self.put(key, val)
 *  BST get(key) 方法，在树种找到key所在的节点取到payload
 *  BST 通过 \_\_getitem\_\_ 方法调用get方法来实现索引
    
    比如 z = myZipTree\[‘Fargo’\]
 *  BST 通过 \_\_contains\_\_ 方法调用\_get方法来实现归属判断(重载了in运算符)
    
    比如 ‘PKU in myZipTree’
    
        def get(self, key):
                if self.root:
                    res = self._get(key, self.root)
                    if res:
                        return res.payload
                    else:
                        return None
                else:
                    return None
        
            def _get(self, key, currentNode):
                if not currentNode:
                    return None
                elif currentNode.key == key:
                    return currentNode
                elif key < currentNode.key:
                    return self._get(key, currentNode.leftChild)
                else:
                    return self._get(key, currentNode.rightChild)
        
            def __getitem__(self, key):
                return self.get(key)
        
            def __contains__(self, key):
                if self._get(key, self.root):
                    return True
                else:
                    return False
        
        mytree = BinarySearchTree()
        mytree[3] = 'red'
        mytree[4] = 'blue'
        mytree.put(2, 'at')
        print(3 in mytree) # True
        print(mytree[3]) # red
 *  TreeNode 通过 \_\_iter\_\_ 方法实现for迭代
    
     *  可以用for循环枚举字典中所有key ADT Map也应该实现这一的迭代器功能
     *  BST类中 \_\_iter\_\_ 方法直接调用了TreeNode中的同名方法
    
    TreeNode类中的 \_\_iter\_\_ 迭代器，迭代器函数中用了for迭代，实际上是递归函数yield是对每次迭代的返回值
    
        # 中序遍历的迭代
            def __iter__(self):
                if self:
                    if self.hasLeftChild():
                        for elem in self.leftChild:
                            yield elem
                    yield self.key
                    if self.hasRightChild():
                        for elem in self.rightChild:
                            yield elem
                            
        mytree = BinarySearchTree()
        mytree[3] = 'red'
        mytree[4] = 'blue'
        mytree.put(2, 'at')
        for key in mytree:
            print(key, mytree[key])
        # 2 at
        # 3 red
        # 4 blue
 *  BST delete 方法，用\_get 找到要删除的节点，然后调用remove来删除，找不到则提示错误
 *  BST 通过 \_\_delitem\_\_ 方法实现索引删除
    
    比如 del myZipTree\[‘PKU’\]
 *  BST remove 一个节点，还要求仍然保持BST的性质，分以下3种情形：
    
    1.  这个节点没有子节点
        
        ![第一种情况][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 12]
    2.  这个节点有1个子节点
        
         *  被删节点的是左子节点？还是右子节点
         *  被删节点本身是其父节点的左子节点还是右子节点？
         *  被删节点本身就是根节点？
        
        ![第二种情况][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 13]
        
        只讨论当前节点有左子节点的情况：
        
        1.  如果当前节点是一个左子节点，只需要将当前节点的左子节点对父节点的引用改为指向当前节点的父节点，然后将父节点对当前节点的引用改为指向当前节点的左子节点
        2.  如果当前节点是一个右子节点，只需要将当前节点的右子节点对父节点的引用改为指向当前节点的父节点，然后将父节点对当前节点的引用改为指向当前节点的右子节点
        3.  如果当前节点没有父节点，那它肯定是根节点。调用replaceNodeData 方法，替换根街电的key、payload、leftChild、rightChild数据
    3.  这个节点有2个子节点
        
        这时无法简单地将某个节点上移替换被删节点但可以找到另一个合适的节点来替换被删节点，这个合适节点就是被删节点的下一个key值节点，即被删节点右子树中最小的那个，成为“后继”
        
        可以肯定这个后继节点最多只有1个子节点（本身是叶节点，或仅有右子树）
        
        将这个后继节点摘出来（也就是删除了），替换掉被删节点
        
        ![第三种情况][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 14]
        
         *  如果节点有右子节点，那么后继节点就是右子树中最小的节点
         *  如果节点没有右子节点，并且其本身是父节点的左子节点，那么后继节点就是父节点
         *  如果节点是父节点的右子节点，并且其本身没有右子节点，那么后继节点就是除其本身外父节点的后继节点
        
            def remove(self, currentNode):
                    if currentNode.isLeaf():
                        if currentNode == currentNode.parent.leftChild:
                            currentNode.parent.leftChild = None
                        else:
                            currentNode.parent.rightChild = None
                    # 有两个子节点
                    elif currentNode.hasBothChildren():
                        succ = currentNode.findSuccessor()
                        succ.spliceOut()
                        currentNode.key = succ.key
                        currentNode.payload = succ.payload
                    # 只有一个子节点
                    else:
                        if currentNode.hasLeftChild():
                            if currentNode.isLeftChild():
                                # 左子节点删除 左左组合
                                currentNode.leftChild.parent = currentNode.parent
                                currentNode.parent.leftChild = currentNode.leftChild
                            elif currentNode.isRightChild():
                                # 右子节点删除 右左组合
                                currentNode.leftChild.parent = currentNode.parent
                                currentNode.parent.rightChild = currentNode.leftChild
                            else:
                                currentNode.replaceNodeData(
                                    currentNode.leftChild.key, currentNode.leftChild.payload,
                                    currentNode.leftChild.leftChild, currentNode.leftChild.rightChild)
                        else:
                            if currentNode.isLeftChild():
                                # 左字节点删除 左右组合
                                currentNode.rightChild.parent = currentNode.parent
                                currentNode.parent.leftChild = currentNode.rightChild
                            elif currentNode.isRightChild():
                                # 右子节点删除 右右组合
                                currentNode.rightChild.parent = currentNode.parent
                                currentNode.parent.rightChild = currentNode.rightChild
                            else:
                                currentNode.replaceNodeData(
                                    currentNode.rightChild.key, currentNode.rightChild.payload,
                                    currentNode.rightChild.leftChild, currentNode.rightChild.rightChild)

### 算法分析 ###

*  其性能决定因素在于二叉搜索树的高度（最大层次），而其高度又受数据项key插入顺序的影响
 *  如果key的列表是随机分布的话，那么大于和小于根节点key的键值大概相等
 *  BST的高度就是log2 n（n是节点的个数），而且，这样的树就是平衡树
 *  put方法最差性能为O(log2 n)
 *  但key列表分布极端情况就完全不同
    
    按照从小到大顺序插入的话，put方法的性能为O(n)

class BinarySearchTree:
        def __init__(self):
            self.root = None
            self.size = 0
    
        def length(self):
            return self.size
    
        def __len__(self):
            return self.size
    
        def __iter__(self):
            return self.root.__iter__()
    
        def put(self, key, val):
            if self.root:
                self._put(key, val, self.root)
            else:
                self.root = TreeNode(key, val)
            self.size += 1
    
        def _put(self, key, val, currentNode):
            if key < currentNode.key:
                if currentNode.hasLeftChild():
                    self._put(key, val, currentNode.leftChild)
                else:
                    currentNode.leftChild = TreeNode(key, val, parent=currentNode)
            else:
                if currentNode.hasRightChild():
                    self._put(key, val, currentNode.rightChild)
                else:
                    currentNode.rightChild = TreeNode(key, val, parent=currentNode)
    
        def __setitem__(self, key, val):
            self.put(key, val)
    
        def get(self, key):
            if self.root:
                res = self._get(key, self.root)
                if res:
                    return res.payload
                else:
                    return None
            else:
                return None
    
        def _get(self, key, currentNode):
            if not currentNode:
                return None
            elif currentNode.key == key:
                return currentNode
            elif key < currentNode.key:
                return self._get(key, currentNode.leftChild)
            else:
                return self._get(key, currentNode.rightChild)
    
        def __getitem__(self, key):
            return self.get(key)
    
        def __contains__(self, key):
            if self._get(key, self.root):
                return True
            else:
                return False
    
        def delete(self, key):
            if self.size > 1:
                nodeToRemove = self._get(key, self.root)
                if nodeToRemove:
                    self.remove(nodeToRemove)
                    self.size -= 1
                else:
                    raise KeyError('Error, key not in tree')
            elif self.size == 1 and self.root.key == key:
                self.root = None
                self.size -= 1
            else:
                raise KeyError('Error, key not in tree')
    
        def __delitem__(self, key):
            self.delete(key)
    
        def remove(self, currentNode):
            if currentNode.isLeaf():
                if currentNode == currentNode.parent.leftChild:
                    currentNode.parent.leftChild = None
                else:
                    currentNode.parent.rightChild = None
            # 有两个子节点
            elif currentNode.hasBothChildren():
                succ = currentNode.findSuccessor()
                succ.spliceOut()
                currentNode.key = succ.key
                currentNode.payload = succ.payload
            # 只有一个子节点
            else:
                if currentNode.hasLeftChild():
                    if currentNode.isLeftChild():
                        # 左子节点删除 左左组合
                        currentNode.leftChild.parent = currentNode.parent
                        currentNode.parent.leftChild = currentNode.leftChild
                    elif currentNode.isRightChild():
                        # 右子节点删除 右左组合
                        currentNode.leftChild.parent = currentNode.parent
                        currentNode.parent.rightChild = currentNode.leftChild
                    else:
                        currentNode.replaceNodeData(
                            currentNode.leftChild.key, currentNode.leftChild.payload,
                            currentNode.leftChild.leftChild, currentNode.leftChild.rightChild)
                else:
                    if currentNode.isLeftChild():
                        # 左字节点删除 左右组合
                        currentNode.rightChild.parent = currentNode.parent
                        currentNode.parent.leftChild = currentNode.rightChild
                    elif currentNode.isRightChild():
                        # 右子节点删除 右右组合
                        currentNode.rightChild.parent = currentNode.parent
                        currentNode.parent.rightChild = currentNode.rightChild
                    else:
                        currentNode.replaceNodeData(
                            currentNode.rightChild.key, currentNode.rightChild.payload,
                            currentNode.rightChild.leftChild, currentNode.rightChild.rightChild)
    
    
    class TreeNode:
        def __init__(self, key, val, left=None, right=None, parent=None):
            self.key = key
            self.payload = val
            self.leftChild = left
            self.rightChild = right
            self.parent = parent
    
        def hasLeftChild(self):
            return self.leftChild
    
        def hasRightChild(self):
            return self.rightChild
    
        def isLeftChild(self):
            return self.parent and self.parent.leftChild == self
    
        def isRightChild(self):
            return self.parent and self.parent.rightChild == self
    
        def isRoot(self):
            return not self.parent
    
        def isLeaf(self):
            return not (self.rightChild or self.leftChild)
    
        def hasAnyChildren(self):
            return self.rightChild or self.leftChild
    
        def hasBothChildren(self):
            return self.rightChild and self.leftChild
    
        def replaceNodeData(self, key, value, lc, rc):
            self.key = key
            self.payload = value
            self.leftChild = lc
            self.rightChild = rc
            if self.hasLeftChild():
                self.leftChild.parent = self
            if self.hasRightChild():
                self.rightChild.parent = self
    
        def findSuccessor(self):
            succ = None
            if self.hasRightChild():
                succ = self.rightChild.findMin()
            else:
                # 目前不会遇到
                if self.parent:
                    if self.isLeftChild():
                        succ = self.parent
                    else:
                        self.parent.rightChild = None
                        succ = self.parent.findSuccessor()
                        self.parent.rightChild = self
    
        def findMin(self):
            current = self
            # 直到左下角
            while current.hasLeftChild():
                current = current.leftChild
            return current
    
        def spliceOut(self):
            # 摘出叶节点
            if self.isLeaf():
                if self.isLeftChild():
                    self.parent.leftChild = None
                else:
                    self.parent.rightChild = None
            elif self.hasAnyChildren():
                if self.hasLeftChild():
                    # 目前不会遇到
                    if self.leftChild():
                        self.parent.leftChild = self.leftChild
                    else:
                        self.parent.rightChild = self.leftChild
                    self.leftChild.parent = self.parent
                else:
                    if self.isLeftChild():
                        self.parent.leftChild = self.rightChild
                    else:
                        self.parent.rightChild = self.rightChild
                    self.rightChild.parent = self.parent
    
        def __iter__(self):
            # 中序遍历的迭代
            if self:
                if self.hasLeftChild():
                    for elem in self.leftChild:
                        yield elem
                yield self.key
                if self.hasRightChild():
                    for elem in self.rightChild:
                        yield elem
    
    
    mytree = BinarySearchTree()
    mytree[3] = 'red'
    mytree[4] = 'blue'
    mytree.put(2, 'at')
    mytree.put(5, 'fn')
    print(3 in mytree)
    print(mytree[3])
    del mytree[5]
    for key in mytree:
        print(key, mytree[key])

## 平衡二叉查找树：AVL ##

### AVL树定义 ###

*  AVL树的实现中，需要对每个节点跟踪“平衡因子balance factor” 参数
 *  平衡因子是根据节点的左右子树的高度差来定义的，确切地说，是左右子树高度差
    
    balanceFactor = height(leftSubTree) - height(rightSubTree)
    
    如果平衡因子大于0.称为“左重left-heavy”，小于0称为“右重right-heavy”，平衡因子等于0，则称作平衡
 *  如果一个二叉查找树中每个节点的平衡因子都在-1,0,1之间，则把这个二叉搜索树称为平衡树
    
    ![平衡树][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 15]
 *  在平衡树操作过程中，有节点的平衡因子超出此范围，则需要一个重新平衡的过程

### AVL树性能 ###

*  分析AVL树最差情形的性能，即平衡因子为1或者-1
    
    下图列出平衡因子为1的“左重”AVL树，树的高度从1开始，来看看问题规模（总结点树N）和比对次数（树的高度h）之间的关系如何？
    
    ![性能][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 16]
    
    ![1][1 1]
    
    ![2][2 1]
    
    ![3][3 1]

### AVL树实现 ###

*  叶节点平衡因子是0，其本身无序重新平衡
 *  但会影响其父节点的平衡因子
    
    作为左子节点插入，则父节点平衡因子增加1
    
    作为右子节点插入，则父节点平衡因子减少1
    
    ![平衡因子][20200625220518247.png]
 *  这种影响可能随着父节点到根节点的路径一直传递上去，直到：
    
    传递到根节点为止
    
    某个父节点平衡因子被调整到0，不再影响上层节点的平衡因子为止
    
    ![平衡因子][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 17]
 *  重新定义\_put 方法
    
        def _put(self, key, val, currentNode):
                if key < currentNode.key:
                    if currentNode.hasLeftChild():
                        self._put(key, val, currentNode.leftChild)
                    else:
                        currentNode.leftChild = TreeNode(key, val, parent=currentNode)
                        # 调整因子
                        self.updateBalacce(currentNode.leftChild)
                else:
                    if currentNode.hasRightChild():
                        self._put(key, val, currentNode.rightChild)
                    else:
                        currentNode.rightChild = TreeNode(key, val, parent=currentNode)
                        # 调整因子
                        self.updateBalacce(currentNode.rightChild)
 *  UpdateBalance方法
    
        def updateBalacce(self, node):
                # 检查当前节点是否需要平衡
                if node.balanceFactor > 1 or node.balanceFactor < -1:
                    self.rebalance(node)
                    return
                if node.parent != None:
                    if node.isLeftChild():
                        node.parent.balanceFactor += 1
                    elif node.isRightChild():
                        node.parent.balanceFactor -= 1
                    if node.parent.balanceFactor != 0:
                        # 调整父节点因子
                        self.updateBalacce(node.parent)
 *  rebalance重新平衡
    
    主要手段：将不平衡的子树进行旋转rotation
    
    ![左旋][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 18]
    
    ![左重右旋][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 19]
    
    ![左旋][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 20]
    
    ![调整平衡因子][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 21]
    
    ![复杂][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 22]
    
    ![rebalance][]

### AVL树总结 ###

*  经过复杂的put方法，AVL树始终维持平衡，get方法也始终保持O(log n)高性能
 *  将AVL树的put方法分为两个部分
    
    需要插入的新节点是叶节点，更新其所有父节点和祖先节点的代价最多为O(log n)
    
    如果需要插入的新节点引发了不平衡，重新平衡最多需要2次旋转，但旋转的代价跟问题规模无关，是常数O(1)
    
    所以整个put方法的时间复杂度还是O(log n)

## ADT MAP实现方法小结 ##

推荐使用散列表和AVL树

![总结][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 23]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200616182219122.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[20200616183907737.png]: https://img-blog.csdnimg.cn/20200616183907737.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200616185938990.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200617102659726.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[2020061711020362.png]: https://img-blog.csdnimg.cn/2020061711020362.png
[20200617123750732.png]: https://img-blog.csdnimg.cn/20200617123750732.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200617124908168.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[1]: https://img-blog.csdnimg.cn/20200617133500735.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[2]: https://img-blog.csdnimg.cn/2020061713360851.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[3]: https://img-blog.csdnimg.cn/20200617133715421.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200618172258948.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200621182314757.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200621185534564.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200621185723654.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200622162024194.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200623143313550.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/20200624111311405.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 11]: https://img-blog.csdnimg.cn/2020062415393681.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 12]: https://img-blog.csdnimg.cn/20200624211207345.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 13]: https://img-blog.csdnimg.cn/2020062421162486.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 14]: https://img-blog.csdnimg.cn/20200625215445372.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 15]: https://img-blog.csdnimg.cn/20200625215603284.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 16]: https://img-blog.csdnimg.cn/20200625215848153.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[1 1]: https://img-blog.csdnimg.cn/20200625220134822.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[2 1]: https://img-blog.csdnimg.cn/20200625220202189.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[3 1]: https://img-blog.csdnimg.cn/20200625220220582.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[20200625220518247.png]: https://img-blog.csdnimg.cn/20200625220518247.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 17]: https://img-blog.csdnimg.cn/20200625220916386.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 18]: https://img-blog.csdnimg.cn/20200625223435537.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 19]: https://img-blog.csdnimg.cn/20200625223556281.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 20]: https://img-blog.csdnimg.cn/20200625224011873.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 21]: https://img-blog.csdnimg.cn/20200625224129944.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 22]: https://img-blog.csdnimg.cn/20200625224353412.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[rebalance]: https://img-blog.csdnimg.cn/20200625224421676.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 23]: https://img-blog.csdnimg.cn/20200625221426434.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70