数据结构Python版--树_python 树

一、树

作为数据结构的树和现实世界中的树有很多共同之处，二者皆有根、茎、叶。不同之处在于前者的根在顶部而叶在底部。
树的第一个属性是层次性，第二个属性是一个节点的所有子节点都与另一个节点的所有子节点无关，第三个属性是叶子节点都是独一无二的。
节点是树的基础，我们称作键，节点可以带有附加信息，称为有效载荷。边是树的另一个基础部分，两个节点通过一条边相连，表示它们之间存在的关系，除了根节点以外，每个节点都仅有一条入边，可以有多条出边。根节点是树中唯一没有入边的节点。路径是由边连接的有序节点列表，层数是从根节点到n的唯一路径长度，根节点的层数为0.树的高度是其中节点层数的最大值。
定义1：树由节点及连接节点的边构成，具有以下属性：有一个根节点，除了根节点外，其他的每个节点都与唯一的父节点相连，从根节点到其他每个节点都有且仅有一条路径，如果每个节点有两个子节点，就称这样的树为二叉树。
定义2：一颗树要么为空，要么由一个根结点和零棵或多棵子树欧城，子树本身也是一棵树。每棵子树的根节点通过一条边连到父树的根节点。

实现

BinaryTree()创建一个二叉树实例
getLeftChild()返回当前节点的左子节点所对应的二叉树
getRightChild()返回当前节点的右子节点所对应的二叉树
setRootVal(val)在当前节点中存储参数val中的对象
getRootVal()返回当前节点存储的对象
insertLeft(val)新建一颗二叉树，并将其作为当前节点的左子节点
insertRight(val)新建一颗二叉树，并将其作为当前节点的右子节点
实现树的关键在于选择一个好的内部存储技巧。

列表之列表

在列表之列表的树中，我们将根节点的值作为列表的第一个元素，第二个元素代表的左子树的列表，第三个元素是代表右子树的列表。可以通过标准的切片来访问子树。

'''
不是定义二叉树类
是创建可用于标准列表的函数
'''
def BinaryTree(r):
    return [r,[],[]]

'''
添加左子树，需要在列表的第二个位置加入一个新列表
如果列表的第二个位置已经有内容了，要保留已有内容，并将它作为新列表的左子树
在插入左子树时，先活得当前的左子树所对应的列表，然后加入新的左子树
将旧的左子树作为新节点的左子树
插入右子树也是一样的道理
'''
# 插入左子树
def insertLeft(root,newBranch):
    t = root.pop(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,[],[]])

# 访问函数
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)
print("1",r)

运行结果：
1 [3, [5, [4, [], []], []], [7, [], [6, [], []]]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

节点与引用

利用节点与引用，定义一个类，其中有根节点和左右子树的属性。

'''
构造方法接受一个对象，并将其存储到根节点中
正如可以在列表中存储任何对象，根节点对象也可以成为任何对象的引用
'''
class BinaryTree:
    def __init__(self,rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None
    '''
    两种情况，一种是根本没有左子节点 
    另一种是已经存在左子节点，插入一个节点，并将已有的左子节点降一层。
    '''
    def insertLeft(self,newNode):
        if self.leftChild == None:
            self.leftChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.left = self.leftChild
            self.leftChild = t

    def insertRight(self,newNode):
        if self.rightChild == None:
            self.rightChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.right = self.rightChild
            self.rightChild = t

    # 二叉树访问函数
    def getRight(self):
        return self.rightChild
    def getLeft(self):
        return self.leftChild

    def setRootVal(self,obj):
        self.key = obj
    def getRootVal(self):
        return self.key

# 根节点的左右子节点本身都是BinaryTree类的实例
r = BinaryTree('a')
print("2",r.getRootVal())
print("3",r.getLeft())
r.insertLeft('b')
print("4",r.getLeft())
print("5",r.getLeft().getRootVal())

运行结果：
2 a
3 None
4 <__main__.BinaryTree object at 0x000002A0081CB550>
5 b
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

二叉树的应用

解析树

解析树可以用来表示现实世界中像句子或数学表达式这样的构造。

问题：
1.如何根据完全括号表达式构建解析树
2.如何计算解析树中的表达式
3.如何将解析树还原成最初的数学表达式
创建4条规则：
1.如果当前标记是（，就可以为当前节点添加一个左子节点，并下沉至该子节点；2.如果当前标记在列表[‘+’,‘-’,‘/’,'']中就将当前节点的值设为当前标记对应的运算符；为当前接待你添加一个右子节点，并下沉至该子节点；3.如果当前标记是数字，就将当前节点的值设为这个数并返回至父节点；4.如果当前标记是），就跳到当前节点的父节点。
表达式（3+（45））构建过程

# 输出树
    def postorder(self):
        if self.leftChild:
            self.leftChild.postorder()
        if self.rightChild:
            self.rightChild.postorder()
        print(self.key)

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.getLeft()
        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.getRight()
        elif i == ')':
        # 返回到父节点
            currentTree = pStack.pop()
        else:
            raise ValueError
    return eTree

pt = buildParseTree('( ( 10 + 5 ) * 3 )')
# 输出树的函数
pt.postorder()

运行结果：
10
5
+
3
*
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

计算解析树并返回计算结果，通过递归计算每棵子树得到整棵解析树的结果。

# 计算二叉解析树的递归函数
def evaluate(parseTree):
    # 字典中存储的值是operator模块的函数
    opers = {'+':operator.add,'-':operator.sub,'*':operator.mul,'/':operator.truediv}
    leftC = parseTree.getLeft()
    rightC = parseTree.getRight()

    if leftC and rightC:
        fn = opers[parseTree.getRootVal()]
        return fn(evaluate(leftC),evaluate(rightC))
    else:
        return parseTree.getRootVal()
print(evaluate(pt))
运行结果：
45
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

树的遍历

遍历一共三种方式：前序遍历、中序遍历和后序遍历.
前序遍历：先访问根节点，然后递归的前序遍历左子树，最后递归的前序遍历右子树
中序遍历：先递归的中序遍历左子树，然后当问根节点，最后递归的中序遍历右子树
后序遍历: 先递归的后序遍历右子树，然后递归的后序遍历左子树，最后访问根节点

# 前序遍历实现为内部函数
    def preorder(self):
        print(self.key)
        if self.leftChild:
            self.left.preorder()
        if self.rightChild:
            self.right.preorder()
      
 # 前序遍历算法实现为外部函数:参数是二叉树
def preorder(tree):
    if tree:
        print(tree.getRootVal())
        preorder(tree.getLeft())
        preorder(tree.getRight())

# 后序遍历函数
def postorder(tree):
    if tree != None:
        postorder(tree.getLeft())
        postorder(tree.getRight())
        print(tree.getRootVal())

# 后序求值函数
def postordereval(tree):
    opers = {'+':operator.add,'-':operator.sub,'*':operator.mul,'/':operator.truediv}
    res1 = None
    res2 = None
    if tree:
        res1 = postordereval(tree.getLeft())
        res2 = postordereval(tree.getRight())
        if res1 and res2:
            return opers[tree.getRootVal()](res1,res2)
        else:return tree.getRootVal()

# 中序遍历函数 ：还原不带括号的表达式
def inorder(tree):
    if tree != None:
        inorder(tree.getLeft())
        print(tree.getRootVal())
        inorder(tree.getRight())

# 修改中序遍历函数：还原完全括号表达式
def printexp(tree):
    sVal =""
    if tree:
        # 在递归调用左子树前打印一个左括号，在递归调用右子树后打印一个右括号
        sVal = '('+printexp(tree.getLeft())
        sVal = sVal +str(tree.getRootVal())
        sVal = sVal +printexp(tree.getRight())+')'

    return sVal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

利用二叉堆实现优先级队列

队列中有一个重要的变体叫做优先级队列，和队列一样，优先级队列从头部移除元素，不过元素的逻辑顺序是由优先级决定的，优先级高的元素在最前面，优先级最低的元素在最后面。
实现优先级队列的经典方法是使用叫做二叉堆的数据结构。列表的插入操作时O(n)，排序操作时O(nlogn)，但是二叉堆的入队和出队操作均可达到O(logn).
二叉堆有两个常见的变体，最小堆和最大堆。

二叉堆的操作

BinaryHeap()新建的一个空的二叉堆
insert(k)往堆中加入一个新的元素
findMin()返回最小元素，并将元素留在堆中
delMin()返回最小元素，并将该元素从堆中移除
isEmpty()在堆为空的时候返回True,否则返回false
size()返回堆中元素的个数
bulidHeap(list)根据一个列表创建堆
平衡二叉树指的是，其根节点的左右子树含有数量大致相等的节点。在实现二叉堆时，通过创建一颗完全二叉树来维持书的平衡。完全二叉树是除了最底层，其他每一层的节点都是满的，在最底层我们从左向右填充。

完全二叉树可以用一个列表来表示他，对列表中处于位置p的节点来说，它的左子节点正好处于位置2p，右子节点处于位置2p+1.若要找到树中任意节点父节点的位置，只需要使用整数出发即可。

# 新建二叉堆
class binHeap:
    def __init__(self):
        # 使用列表来表示二叉堆：设置第一个元素为0，便于使用整数除法
        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)

    '''
    堆的性质要求根节点是树的最小元素
    delMin难点在于如何在移除根节点之后重新获得堆的结构性质和有序性
    1.取出列表中的最后一个元素，将其移动到根节点的位置
    2.将新的根节点沿着树推到正确的位置，以获得堆的有序性
    '''

    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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

我们还需要讨论根据元素列表构建整个堆的方法。

 # 根据元素列表构建堆
    def bulidHeap(self,alist):
        # 找到不是叶子节点的最后一个节点位置
        i = len(alist)//2
        # 初始化堆
        self.currentSize = len(alist)
        self.heapList = [0] + alist[:]
        # 构建堆
        while(i>0):
            self.percDown(i)
            i = i-1
1
2
3
4
5
6
7
8
9
10
11

二叉搜索树

二叉搜索树是映射的另一种实现。重点不是元素在树中的确切位置，而是如何利用二叉树的结构提供高效的搜索。

搜索树的实现

二叉搜索树依赖于这样一个性质：小于父节点的键都在左子树中，大于父节点键都在右子树中，称这个性质为二叉搜索行，它会引导我们实现映射接口。

'''
采用'节点与引用'表示法来实现二叉搜索树
必须创建并处理一颗空的二叉搜索树
BinarySearchTree类有一个引用，指向作为二叉搜索树根节点的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__()

    '''
    从根节点开始搜索二叉树，比较新键和当前节点的键
    如果新键更小，搜索左子树，如果新键更大，搜索右子树
    当没有可供搜索的左（右）子节点时，说明找到了新的插入位置
    向树中插入一个节点，做法是创建一个TreeNode对象，并插入到前一步发现的位置上
    插入方法不能正确的处理重复的键，遇到重复的键的时候会在已有节点的右子树中创建一个具有同样键的节点
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

插入值

  
   # 为二叉搜索树插入新的节点
   def put(self,key,val):
       # 不是根节点
       if self.root:
           self._put(key,val,self.root)
       # 创建根节点
       else:
           self.root = TreeNode(key,val)
       self.size = 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.rightChilid =TreeNode(key,val,parent=currentNode)
   '''
   通过__setitem__方法调用put方法来重载[]运算符 
   就像访问一个字典一样
   '''
   def __setitem__(self, key, value):
       self.put(key,value)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

# 提供辅助函数 显示的将每个节点的父节点记录为它的一个属性
class TreeNode:
    def __init__(self,key,val,left=None,right=None,parent = None):
        self.key = key
        self.payload = val
        self.leftChild = left
        self.rightChilid = right
        self.parent = parent
        #平衡因子
        self.balanceFactor = 0

    def hasLeftChild(self):
        return self.leftChild

    def hasRightChild(self):
        return self.rightChilid

    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.rightChilid or self.leftChild)

    def hasAnyChildren(self):
        return self.rightChilid or self.leftChild

    def hasBothChildren(self):
        return self.rightChilid and self.leftChild

    def replaceNodeData(self,key,value,lc,rc):
        self.key = key
        self.payload = value
        self.leftChild = lc
        self.rightChilid = rc
        if self.hasLeftChild():
            self.leftChild.parent = self
        if self.hasRightChild():
            self.rightChilid.parent = self
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

查找值

'''
    get、_get和__getitem__实现:查找键对应的值
    '''
    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,curretNode):
        if not curretNode:
            return None
        elif curretNode.key == key:
            return curretNode
        elif key < curretNode.key:
            return self._get(key,curretNode.leftChild)
        else:
            return self._get(key,curretNode.rightChild)
    
    def __getitem__(self, item):
        return self.key
    # 检查树中是否有某个键:contains方法重载了in运算符
    def __contains__(self, key):
        if self._get(key,self.root):
            return True
        else:
            return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

'''
    get、_get和__getitem__实现:查找键对应的值
    '''
    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,curretNode):
        if not curretNode:
            return None
        elif curretNode.key == key:
            return curretNode
        elif key < curretNode.key:
            return self._get(key,curretNode.leftChild)
        else:
            return self._get(key,curretNode.rightChild)

    def __getitem__(self, item):
        return self.key
    # 检查树中是否有某个键:contains方法重载了in运算符
    def __contains__(self, key):
        # 传入键值和查找树
        if self._get(key,self.root):
            return True
        else:
            return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

删除值

'''
        在书中搜索并找到要删除的节点，如果书中不止一个节点，使用_get方法搜索，找到要移除的TreeNode
        如果树中只有一个节点意味着要移除根节点
        不管哪种情况，如果找不到要删除的键，就直接抛出一个异常
        '''
    def delete(self,key):
        if self.size > 1:
            nodeToRemove = self._get(key,self.root)
            if nodeToRemove:
                self.remove(nodeToRemove)
                self.size = 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 = self.size-1
        else:
            raise KeyError('Error,key not in there')
    def __delitem__(self, key):
        self.delete(key)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

一旦找到待删除键对应的节点，就必须考虑3种情况。

如果一个节点有两个子节点，就不太可能仅依靠其中一个子节点取代它来解决问题。但是可以搜索整棵树，找到可以替换待删除节点的节点。候选节点要能为左右子树都保持二叉搜索树的关系，也就是树中具有次大键的节点，我们将这个键称为后继节点。（后继节点：中序遍历中该节点的下一个节点）后继节点的子节点必定不会多于一个，移除后继节点后，只需将它直接放到树中待删除节点的位置上即可。

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

    def __delitem__(self, key):
         self.delete(key)
    '''
    寻找后继节点，利用二叉搜索树的属性
    考虑3种情况：
    1.如果节点有右子节点，后继节点就是右子树中的最小节点
    2.如果节点没有右子节点，并且本身是父节点的左子节点，那么后继节点就是父节点
    3.如果节点是父节点的右子节点，并且本身没有右子节点，那么后继节点就是除本身外父节点的后继节点
    finMin查找子树的最小键，在任意的二叉搜索树种，最小键就是最左边的子节点，
    只需沿着子树的每个节点的leftChild引用走，直到遇到一个没有左子节点的节点
    '''
    # 查找后继节点
    def findSuccessor(self):
        succ = None
        # 含有右子树
        if self.hasRightChild():
            succ = self.rightChilid.finMin()
        # 没有右子树
        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 finMin(self):
        current = self
        while current.hasLeftChild():
            current = current.leftChild
        return current

        # 对后继节点进行移除，spliceOut可以直接访问待拼接的节点，并进行正确的修改
        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 remove(self, currentNode):
        # 叶子节点
        if currentNode.isLeaf():
            if currentNode == currentNode.parent.leftChild:
                currentNode.parent.leftChild = None
            else:
                currentNode.parent.rightChild = None
        # 两个节点
        elif currentNode.hasBothChild():
            # 找到后继节点
            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)
mytree = BinarySearchTree()
mytree[3]="red"
mytree[4]="blue"
mytree[6]="yellow"
mytree[2]="at"

print(3 in mytree)
print(mytree[6])
del mytree[2]
print(mytree[2])
运行结果：
True
yellow
None
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

这个代码是递归的。

 # 二叉搜索树迭代器：中序遍历
    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.rightChilid:
                    yield elem
1
2
3
4
5
6
7
8
9
10

平衡二叉搜索树

当二叉搜索树不平衡时,get和put操作的性能可能降到O(n)，一种能自动维持平衡的树叫AVL树，实现AVL树与普通的二叉搜索树一样，唯一的差别就是性能，实现AVL树时，要记录每一个节点的平衡因子，将平衡因子定义为左右子树的高度之差。如果平衡因子大于零就是左倾，如果平衡因子小于零就是右倾，如果平衡因子等于零就是完全平衡，将平衡因子为-1，0，1的树都定义为平衡树，一旦某个节点的平衡因子超出这个范围，就需要一个过程让树恢复平衡。



AVL树的时间复杂度被限制为O(logN)。

AVL树的实现

所有的新键都是以叶子节点插入的，因为新叶子节点的平衡因子是零，所以新插节点没有什么限制条件。但是插入新节点后，必须更新父节点的平衡因子，新的叶子节点对其父节点平衡因子的影响取决于他是左子节点还是右子节点。如果是右子节点，父节点的平衡因子减一，如果是左子节点，则父节点的平衡因子加一。
这个关系可以递归到每个祖先，直到根节点。更新平衡因子是递归过程，就检查以下两种基本情况：
1.递归调用抵达根节点
2.父节点的平衡因子调整为0，可以确信，如果子树的平衡因子为零，那么祖先节点的平衡因子不会发生变化。
左旋步骤：
1.将右子节点提升为子树的根节点
2.将旧根节点作为新根节点的左子节点
3.如果新根节点B已经有一个左子节点，将其作为新左子节点A的右子节点，因为节点B之前是A的右子节点，因此节点A必然没有右子节点，因此可以为她添加新的右子节点，无须过多考虑。

如果子树需要左旋，首先检查右子树的平衡因子，如果右子树左倾，就对右子树做一次右旋，再围绕原节点做一次左旋。
如果子树需要右旋，首先检查左子树的平衡因子，如果左子树右倾，就对左子树做一次左旋，再围绕原节点做一次右旋。

class AVLTree(BinarySearchTree):
    # 重载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.updateBalance(currentNode.leftChild)
        else:
            # 插入到右子树中
            if currentNode.hasRightChild():
                self._put(key,val,currentNode.rightChild)
            else:
                currentNode.rightChild= TreeNode(key,val,parent=currentNode)
                self.updateBalance(currentNode.rightChild)
    # 更新平衡因子
    def updateBalance(self,node):
        # 首先检查当前节点是否平衡
        if node.balanceFactor > 1 or node.balanceFactor < -1:
            self.rebalance(node)
            return
        # 调节父节点的平衡因子为0
        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.isRightChild():
                rotRoot.parent.rightChild = newRoot
            else:
                rotRoot.parent.leftChild = 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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

小结

二叉堆的删除算法，应该有比书中提出的方法更清晰的解决思路。