一、讨论题

略

二、编程练习

1.扩展buildParseTree方法，使其能够处理字符间没有空格的数字表达式。

&

2.修改buildParseTree和evaluate，使它们支持逻辑运算符(and、or、not)。注意，not是一元运算符，这会让代码有点复杂。

from chapter3.stack import Stack
from chapter6.BinaryTree2 import BinaryTree
import operator

def buildParseTree2(fpexp):
    fplist1 = fpexp.split()
    fplist = []
    for i in fplist1:
        if i in ['and', 'not', 'or']:
            fplist.append(i)
        elif i == '(not':
            fplist.append('not')
        else:
            for j in i:
                if j == 'n':
                    fplist.append('not')
                    break
                else:
                    fplist.append(j)

    pStack = Stack()
    eTree = BinaryTree('')
    pStack.push(eTree)
    currentTree = eTree
    currentTree.setRootVal(eval(fpexp))


    for i in fplist:
        if i == '(':
            currentTree.insertLeft('')
            pStack.push(currentTree)
            currentTree = currentTree.getLeftChild()
        elif i not in '+-*/)' and i not in ['and', 'or', 'not']:
            currentTree.setRootVal(eval(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()
        elif i in ['and', 'or', 'not']:
            currentTree.setRootVal(i)
            currentTree.insertRight('')
            pStack.push(currentTree)
            currentTree = currentTree.getRightChild()
        else:
            raise ValueError('Unknown Operator:' + i)

    return eTree

def evaluate(parseTree):
    opers = {'+':operator.add, '-':operator.sub, '*':operator.mul,
             '/':operator.truediv, 'and':fn_and, 'or':fn_or,
             'not':fn_not}

    leftC = parseTree.getLeftChild()
    rightC = parseTree.getRightChild()
    if parseTree.getRootVal() == 'not':
        fn = opers[parseTree.getRootVal()]
        return fn(rightC)
    else:
        if leftC and rightC:
            fn = opers[parseTree.getRootVal()]
            return fn(evaluate(leftC), evaluate(rightC))
        else:
            return parseTree.getRootVal()


def fn_and(left, right):
    return left and right

def fn_or(left, right):
    return left or right

def fn_not(right):
    return not right

if __name__ == '__main__':
    tree = buildParseTree2('((1+0) or (not 0))')
    print(evaluate(tree))

3.使用findSuccessor方法，写一个非递归的二叉搜索树中序遍历方法。

&

4.修改二叉搜索树的实现代码，从而实现线索二叉搜索树。为线索二叉搜索树写一个非递归的中序遍历方法。线索二叉搜索树为其中的每个节点都维护者指向后继节点的引用。

&

5.修改二叉搜索树的实现代码，以正确处理重复的键。也就是说，如果键已在树中，就替换有效载荷，而不是用同一个键插入一个新节点。

from chapter6.BinarySearchTree import TreeNode

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, value):
        if self.root:
            self._put(key, value, self.root)
        else:
            self.root = TreeNode(key, value)
        self.size = self.size + 1

    def _put(self, key, value, currentNode):
        if key < currentNode.key:
            if currentNode.hasLeftChild():
                self._put(key, value, currentNode.leftChild)
            else:
                currentNode.leftChild = TreeNode(key, value, parent=currentNode)
                currentNode.leftChild.succ = currentNode
                if currentNode.parent:
                    beginNode = currentNode.parent
                    while beginNode:
                        if beginNode.findSuccessor() == currentNode.leftChild:
                            beginNode.succ = currentNode.leftChild
                        beginNode = beginNode.parent

        elif key == currentNode.key:
            currentNode.payload = value
        else:
            if currentNode.hasRightChild():
                self._put(key, value, currentNode.rightChild)
            else:
                currentNode.rightChild = TreeNode(key, value, parent=currentNode)
                currentNode.succ = currentNode.rightChild
                if currentNode.rightChild.findSuccessor():
                    currentNode.rightChild.succ = currentNode.rightChild.findSuccessor()

    def __setitem__(self, key, value):
        self.put(key, value)

    def get(self, key):
        if self.root:
            res = self._get(key, self.root)

    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 = 0
        else:
            raise KeyError('Error, key not in tree')

    def remove(self, currentNode):
        if currentNode.isLeaf():
            if currentNode == currentNode.parent.leftChild:
                currentNode.parent.leftChild = None
            else:
                currentNode.parent.rightChild = None

        elif currentNode.hasLeftChild() and not currentNode.hasRightChild():
            if currentNode.isLeftChild():
                currentNode.leftChild.parent = currentNode.parent
                currentNode.parent.leftChild = currentNode.leftChild
            elif currentNode.isRightChild():
                currentNode.rightChild.parent = currentNode.parent
                currentNode.parent.rightChild = currentNode.leftChild
            else:
                currentNode.replaceNodeData(currentNode.leftChild.key,
                                            currentNode.leftChild.payload,
                                            currentNode.leftChild.leftChild,
                                            currentNode.leftChild.rightChild)
        elif currentNode.hasRightChild() and not currentNode.hasLeftChild():
            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.leftChild.key,
                                            currentNode.leftChild.payload,
                                            currentNode.leftChild.leftChild,
                                            currentNode.leftChild.rightChild)
        else:
            succ = currentNode.findSuccessor()
            succ.spliceOut()
            currentNode.key = succ.key
            currentNode.payload = succ.payload

    def inorder(self):
        currentNode = self.root
        while currentNode:
            beginNode = currentNode
            currentNode = currentNode.leftChild
        while beginNode.findSuccessor():
            print(beginNode.key)
            beginNode = beginNode.findSuccessor()
        print(beginNode.key)

    def inorder2(self):
        currentNode = self.root
        while currentNode:
            beginNode = currentNode
            currentNode = currentNode.leftChild
        while beginNode.succ:
            print(beginNode.key)
            beginNode = beginNode.succ
        print(beginNode.key)



    def __delitem__(self, key):
        self.delete(key)

if __name__ == '__main__':
    tree = BinarySearchTree()
    tree.put(2, 0)
    tree.put(7, 0)
    tree.put(1, 0)
    tree.put(3, 0)
    tree.put(0, 0)
    tree.put(0, 0)
    tree.inorder2()

6.创建限定大小的二叉堆。也就是说，堆只保持n个最重要的元素。如果堆的大小超过了n，就会舍弃最不重要的元素。

class BinaryHeap:
    def __init__(self, maxsize):
        self.heapList = [0]
        self.currentSize = 0
        self.maxsize = maxsize

    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 = i // 2

    def insert(self, k):
        self.heapList.append(k)
        self.currentSize = self.currentSize + 1
        self.percUp(self.currentSize)

    def percDown(self, i):
        while (i * 2) <= self.currentSize:
            mc = self.minChild(i)
            if self.heapList[i] > self.heapList[mc]:
                temp = self.heapList[i]
                self.heapList[i] = self.heapList[mc]
                self.heapList[mc] = temp
            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 delMin(self):
        retval = self.heapList[1]
        self.heapList[1] = self.heapList[self.currentSize]
        self.currentSize = self.currentSize - 1
        self.heapList.pop()
        self.percDown(1)
        return retval

    def buildHeap(self, alist):
        if len(alist) > self.maxsize:
            alist = alist[:self.maxsize]
        i = len(alist) // 2
        self.currentSize = len(alist)
        self.heapList = [0] + alist[:]
        while (i > 0):
            self.percDown(i)
            i -= 1

if __name__ == '__main__':
    heap = BinaryHeap(10)
    alist = [11, 5, 9, 21, 17, 19, 18, 27, 14, 33, 90, 88]
    heap.buildHeap(alist)
    print(heap.heapList)

7.整理printexp函数，去掉数字周围多余的括号。

def printexp(tree):
    sVal = ''
    if tree:
        if tree.leftChild == None and tree.rightChild == None:
            sVal = sVal + str(tree.getRootVal())
        else:
            sVal = '(' + printexp(tree.getLeftChild())
            sVal = sVal + str(tree.getRootVal())
            sVal = sVal + printexp(tree.getRightChild()) + ')'
    return sVal

if __name__ == '__main__':
    from chapter6.BinaryTree2 import BinaryTree
    x = BinaryTree('*')
    x.insertLeft('+')
    l = x.getLeftChild()
    l.insertLeft(4)
    l.insertRight(5)
    x.insertRight(7)
    print(printexp(x))

8.使用buildHeap方法，针对列表写一个时间复杂度为$O(logn)$的排序函数。

class BinaryHeap:
    def __init__(self, maxsize):
        self.heapList = [0]
        self.currentSize = 0
        self.maxsize = maxsize

    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 = i // 2

    def insert(self, k):
        self.heapList.append(k)
        self.currentSize = self.currentSize + 1
        self.percUp(self.currentSize)

    def percDown(self, i):
        while (i * 2) <= self.currentSize:
            mc = self.minChild(i)
            if self.heapList[i] > self.heapList[mc]:
                temp = self.heapList[i]
                self.heapList[i] = self.heapList[mc]
                self.heapList[mc] = temp
            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 delMin(self):
        retval = self.heapList[1]
        self.heapList[1] = self.heapList[self.currentSize]
        self.currentSize = self.currentSize - 1
        self.heapList.pop()
        self.percDown(1)
        return retval

    def buildHeap(self, alist):
        if len(alist) > self.maxsize:
            alist = alist[:self.maxsize]
        i = len(alist) // 2
        self.currentSize = len(alist)
        self.heapList = [0] + alist[:]
        while (i > 0):
            self.percDown(i)
            i -= 1

def sort(alist):
    heap = BinaryHeap(10)
    blist = [0]
    heap.buildHeap(alist)
    for i in range(1, len(alist) + 1):
        if heap.currentSize > 0:
            blist += [heap.heapList[1]]
        heap.buildHeap(heap.heapList[2:])
    print(blist)

if __name__ == '__main__':

    alist = [9, 6, 5, 2, 3]
    sort(alist)

9.写一个函数，以数学表达式解析树为参数，计算各变量的导数。

说实话我没看懂这个题目，计算变量的导数，所以数学表达式是含有xyz吗？？？在网上搜到一个和这个题目类似的，但我的python版本太低导入不了其中的一个包，我就没有试…大家可以下载下来自己跑一下。
参考链接：
http://git.oschina.net/yangtf/python_exp link

10.将二叉树实现为最大堆。

class BinaryMaxHeap:
    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 = i // 2

    def insert(self, k):
        self.heapList.append(k)
        self.currentSize = self.currentSize + 1
        self.percUp(self.currentSize)

    def percDown(self, i):
        while (i * 2) <= self.currentSize:
            mc = self.maxChild(i)
            if self.heapList[i] < self.heapList[mc]:
                temp = self.heapList[i]
                self.heapList[i] = self.heapList[mc]
                self.heapList[mc] = temp
            i = mc

    def maxChild(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 delMax(self):
        retval = self.heapList[1]
        self.heapList[1] = self.heapList[self.currentSize]
        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[:]
        while (i > 0):
            self.percDown(i)
            i -= 1

if __name__ == '__main__':
    heap = BinaryMaxHeap()
    alist = [11, 5, 9, 21, 17, 19, 18, 27, 14, 33, 90, 88]
    heap.buildHeap(alist)
    print(heap.heapList)
    heap.delMax()
    print(heap.heapList)

11.使用BinaryHeap类。实现一个叫做PriorityQueue的新类。为PriorityQueue类实现构造方法，以及enqueue方法和dequeue方法。

from chapter6.BinaryHeap import BinaryHeap

class PriorityQueue:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.append(item)
        heap = BinaryHeap()
        heap.buildHeap(self.items)
        self.items = heap.heapList[1:]

    def dequeue(self):
        return self.items.pop(0)

    def size(self):
        return len(self.items)

if __name__ == '__main__':
    q = PriorityQueue()
    q.enqueue(5)
    q.enqueue(2)
    q.enqueue(3)
    q.enqueue(6)
    q.enqueue(1)
    print(q.items)
    q.dequeue()
    print(q.items)

12.实现AVL树的delete方法。

实现AVL的delete方法，要更新平衡因子，然后再平衡。

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, value):
        if self.root:
            self._put(key, value, self.root)
        else:
            self.root = TreeNode(key, value)
        self.size = self.size + 1

    def _put(self, key, value, currentNode):
        if key < currentNode.key:
            if currentNode.hasLeftChild():
                self._put(key, value, currentNode.leftChild)
            else:
                currentNode.leftChild = TreeNode(key, value, parent=currentNode)
                currentNode.leftChild.succ = currentNode
                if currentNode.parent:
                    beginNode = currentNode.parent
                    while beginNode:
                        if beginNode.findSuccessor() == currentNode.leftChild:
                            beginNode.succ = currentNode.leftChild
                        beginNode = beginNode.parent

        elif key == currentNode.key:
            currentNode.payload = value
        else:
            if currentNode.hasRightChild():
                self._put(key, value, currentNode.rightChild)
            else:
                currentNode.rightChild = TreeNode(key, value, parent=currentNode)
                currentNode.succ = currentNode.rightChild
                if currentNode.rightChild.findSuccessor():
                    currentNode.rightChild.succ = currentNode.rightChild.findSuccessor()


    def __setitem__(self, key, value):
        self.put(key, value)

    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 = 0
        else:
            raise KeyError('Error, key not in tree')

    def remove(self, currentNode):
        if currentNode.isLeaf():
            if currentNode == currentNode.parent.leftChild:
                currentNode.parent.leftChild = None
            else:
                currentNode.parent.rightChild = None

        elif currentNode.hasLeftChild() and not currentNode.hasRightChild():
            if currentNode.isLeftChild():
                currentNode.leftChild.parent = currentNode.parent
                currentNode.parent.leftChild = currentNode.leftChild
            elif currentNode.isRightChild():
                currentNode.rightChild.parent = currentNode.parent
                currentNode.parent.rightChild = currentNode.leftChild
            else:
                currentNode.replaceNodeData(currentNode.leftChild.key,
                                            currentNode.leftChild.payload,
                                            currentNode.leftChild.leftChild,
                                            currentNode.leftChild.rightChild)
        elif currentNode.hasRightChild() and not currentNode.hasLeftChild():
            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.leftChild.key,
                                            currentNode.leftChild.payload,
                                            currentNode.leftChild.leftChild,
                                            currentNode.leftChild.rightChild)
        else:
            succ = currentNode.findSuccessor()
            succ.spliceOut()
            currentNode.key = succ.key
            currentNode.payload = succ.payload

    def inorder(self):
        currentNode = self.root
        while currentNode:
            beginNode = currentNode
            currentNode = currentNode.leftChild
        while beginNode.findSuccessor():
            print(beginNode.key, beginNode.balanceFactor)
            beginNode = beginNode.findSuccessor()
        print(beginNode.key, beginNode.balanceFactor)

    def inorder2(self):
        currentNode = self.root
        while currentNode:
            beginNode = currentNode
            currentNode = currentNode.leftChild
        while beginNode.succ:
            print(beginNode.key)
            beginNode = beginNode.succ
        print(beginNode.key)



    def __delitem__(self, key):
        self.delete(key)


class TreeNode:
    def __init__(self, key, val, left=None, right=None, parent=None, succ=None, balanceFactor=0):
        self.key = key
        self.payload = val
        self.leftChild = left
        self.rightChild = right
        self.parent = parent
        self.succ = succ
        self.balanceFactor = balanceFactor

    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.leftChild and self.rightChild

    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
        return succ

    def findMin(self):
        current = self
        while current.hasLeftChild():
            current = current.leftChild
        return current

    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

    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.isLeftChild():
                    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 spliceOut2(self):
        if self.isLeaf():
            if self.isLeftChild():
                self.parent.leftChild = None
                self.parent.balanceFactor -= 1
            else:
                self.parent.rightChild = None
                self.parent.balanceFactor += 1
        elif self.hasAnyChildren():
            if self.hasLeftChild():
                if self.isLeftChild():
                    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
                    self.parent.balanceFactor -= 1
                else:
                    self.parent.rightChild = self.rightChild
                    self.parent.balanceFactor += 1

                self.rightChild.parent = self.parent


class AVL(BinarySearchTree):


    def _put(self, key, value, currentNode):
        if key < currentNode.key:
            if currentNode.hasLeftChild():
                self._put(key, value, currentNode.leftChild)
            else:
                currentNode.leftChild = TreeNode(key, value, parent=currentNode)
                self.updateBalance(currentNode.leftChild)
        else:
            if currentNode.hasRightChild():
                self._put(key, value, currentNode.rightChild)
            else:
                currentNode.rightChild = TreeNode(key, value, parent=currentNode)
                self.updateBalance(currentNode.rightChild)

    def updateBalance(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.updateBalance(node.parent)

    def rotateLeft(self, rotRoot):
        newRoot = rotRoot.rightChild
        rotRoot.rightChild = newRoot.leftChild
        if newRoot.leftChild != None:
            newRoot.leftChild.parent = rotRoot
        newRoot.parent = rotRoot.parent
        if rotRoot.isRoot():
            self.root = newRoot
        else:
            if rotRoot.isLeftChild():
                rotRoot.parent.leftChild = newRoot
            else:
                rotRoot.parent.rightChild = newRoot
        newRoot.leftChild = rotRoot
        rotRoot.parent = newRoot
        rotRoot.balanceFactor = rotRoot.balanceFactor + 1 - min(newRoot.balanceFactor, 0)
        newRoot.balanceFactor = newRoot.balanceFactor + 1 + max(rotRoot.balanceFactor, 0)

    def rotateRight(self, rotRoot):
        newRoot = rotRoot.leftChild
        rotRoot.leftChild = newRoot.rightChild
        if newRoot.rightChild != None:
            newRoot.rightChild.parent = rotRoot
        newRoot.parent = rotRoot.parent
        if rotRoot.isRoot():
            self.root = newRoot
        else:
            if rotRoot.isLeftChild():
                rotRoot.parent.leftChild = newRoot
            else:
                rotRoot.parent.rightChild = newRoot
        newRoot.rightChild = rotRoot
        rotRoot.parent = newRoot

        rotRoot.balanceFactor = rotRoot.balanceFactor - 1 - max(newRoot.balanceFactor, 0)
        newRoot.balanceFactor = newRoot.balanceFactor - 1 + min(rotRoot.balanceFactor, 0)

    def rebalance(self, node):
        if node.balanceFactor < 0:
            if node.rightChild.balanceFactor > 0:
                self.rotateRight(node.rightChild)
                self.rotateLeft(node)
            else:
                self.rotateLeft(node)
        elif node.balanceFactor > 0:
            if node.leftChild.balanceFactor < 0:
                self.rotateLeft(node.leftChild)
                self.rotateRight(node)
            else:
                self.rotateRight(node)
    def updateBalance2(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.updateBalance2(node.parent)

    def delete1(self, key):
        if self.size > 1:
            nodeToRemove = self._get(key, self.root)
            if nodeToRemove:
                self.remove1(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 = 0
        else:
            raise KeyError('Error, key not in tree')

    def remove1(self, currentNode):


        if currentNode.isLeaf():
            if currentNode == currentNode.parent.leftChild:
                currentNode.parent.leftChild = None
                currentNode.parent.balanceFactor -= 1
            else:
                currentNode.parent.rightChild = None
                currentNode.parent.balanceFactor += 1
            self.updateBalance2(currentNode.parent)
        elif currentNode.hasLeftChild() and not currentNode.hasRightChild():
            if currentNode.isLeftChild():
                currentNode.leftChild.parent = currentNode.parent
                currentNode.parent.leftChild = currentNode.leftChild
                currentNode.parent.balanceFactor -= 1
            elif currentNode.isRightChild():
                currentNode.rightChild.parent = currentNode.parent
                currentNode.parent.rightChild = currentNode.leftChild
                currentNode.parent.balanceFactor += 1
            else:
                currentNode.replaceNodeData(currentNode.leftChild.key,
                                            currentNode.leftChild.payload,
                                            currentNode.leftChild.leftChild,
                                            currentNode.leftChild.rightChild)
            self.updateBalance2(currentNode.parent)
        elif currentNode.hasRightChild() and not currentNode.hasLeftChild():
            if currentNode.isLeftChild():
                currentNode.rightChild.parent = currentNode.parent
                currentNode.parent.leftChild = currentNode.rightChild
                currentNode.parent.balanceFactor -= 1
            elif currentNode.isRightChild():
                currentNode.rightChild.parent = currentNode.parent
                currentNode.parent.rightChild = currentNode.rightChild
                currentNode.parent.balanceFactor += 1
            else:
                currentNode.replaceNodeData(currentNode.leftChild.key,
                                            currentNode.leftChild.payload,
                                            currentNode.leftChild.leftChild,
                                            currentNode.leftChild.rightChild)
            self.updateBalance2(currentNode.parent)
        else:

            succ = currentNode.findSuccessor()
            succ.spliceOut2()
            self.updateBalance2(currentNode)
            currentNode.key = succ.key
            currentNode.payload = succ.payload


if __name__ == '__main__':
    tree = AVL()
    tree.put(2, 0)
    tree.put(7, 0)
    tree.put(1, 0)
    tree.put(3, 0)
    tree.put(0, 0)
    tree.inorder()
    node = tree._get(7, tree.root)
    print('xxxx', tree.root.key, tree._get(1, tree.root).balanceFactor,
           tree._get(3, tree.root).balanceFactor,
          tree._get(7, tree.root).balanceFactor,
          tree._get(0, tree.root).balanceFactor, )
    tree.delete1(3)
    tree.inorder()
    print('xxxx', tree.root.key, tree._get(1, tree.root).balanceFactor,
          tree._get(2, tree.root).balanceFactor,
          tree._get(7, tree.root).balanceFactor,
          tree._get(0, tree.root).balanceFactor, )

三、总结

主要学习了

1.用python表达树的两种方法，
2.二叉搜索树，AVL树，
3.最大堆，最小堆等。