二叉树之BST树、AVL树

1.二叉排序树的介绍

二叉排序树为一颗二叉树，或者为空，或者满足如下条件：
如果它的左子树不为空，那么左子树上的所有结点的值均小于它的根结点的值
如果它的右子树不为空，那么右子树上的左右结点的值均大于它的根结点的值
根结点的左子树和右子树又是二叉排序树。
二叉排序树通常采用二叉链表作为存储结构。中序遍历二叉排序树便可得到一个有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即是对无序序列进行排序的过程。

2.二叉排序树的操作

我们对二叉排序的操作有三种：
查找
插入
删除
其中二叉排序树是一个动态树表，其特点就是树的结构不是一次生成的，而是在查找过程中，如果关键字不在树表中，在把关键字插入到树表中。而对于删除操作，它分为三种情况：

  1. 删除结点为叶子结点（左右子树均为NULL），所以我们可以直接删除该结点
  2. 删除结点只有左子树或者右子树，此时只需要让其左子树或者右子树直接替代删除结点的位置，称为删除结点的双亲的孩子，就可以了
  3. 当要删除的那个结点，其左右子树都存在的情况下，则要从从左子树中找出一个最大的值那个结点来替换我们需要删除的结点

3.二叉排序树代码实现：

class BinarySortTree():
    def __init__(self):
        self.root = None
    def add(self,node):
        if self.root == None:
            self.root = node
        else:
            self.root.add(node)
    def infixOrder(self):
        if self.root == None:
            print("None")
        else:
            self.root.infixOrder()
    def delete(self,value):
        if self.root == None:
            print("None")
        else:
            self.root.delete(value)

class Node():
    def __init__(self,value=None):
        self.value = value
        self.left = None
        self.right = None
        self.root = None
    def add(self,insertnode):
        if insertnode.value < self.value:
            if self.left != None:
               self.left.add(insertnode)
            else:
                self.left = insertnode
        if insertnode.value > self.value:
            if self.right != None:
                self.right.add(insertnode)
            else:
                self.right = insertnode
    def infixOrder(self):
        if self.left != None:
            self.left.infixOrder()
        print(self.value)
        if self.right != None:
            self.right.infixOrder()
    
    def delete(self,value):
        #判断是否为根结点：
        if self.value == value:
            self.covervalue,self.covervaluefather = self.left.findmaxvalue()
            self.value = self.covervalue
            self.covervaluefather.right = None
            return 
        #找到删除结点父结点
        # print(self.value)
        self.fathernode= self.findcurfathernode(value)
        #找到删除结点
        if self.fathernode.left != None and self.fathernode.left.value == value:
            self.delnode = self.fathernode.left
        elif self.fathernode.right != None and self.fathernode.right.value == value:
            self.delnode = self.fathernode.right
        #判断删除结点的三种形态
        #1.删除结点左右子结点均为空
        if self.delnode.left == None and self.delnode.right == None:
            if self.fathernode.left.value == value:
                self.fathernode.left = None
            else:
                self.fathernode.right = None   

        #2.删除结点左右子结点均不为空
        elif self.delnode.left != None and self.delnode.right != None:
            #找当前结点左子树的最大值，删除该结点并把该结点的值给当前结点
            if self.delnode.left.right == None:
                self.delnode.value = self.delnode.left.value
                self.delnode.left = None
            else:
                self.covervalue,self.covervaluefather = self.delnode.left.findmaxvalue()
                self.delnode.value = self.covervalue
                self.covervaluefather.right = None
                

        #3.删除结点左子结点或右子结点其中一个为空
        else:
            if self.fathernode.left != None and self.fathernode.left.value == value:
                if self.delnode.left != None:
                    self.fathernode.left = self.delnode.left
                else:
                    self.fathernode.left = self.delnode.right
            else:
                if self.delnode.left != None:
                    self.fathernode.right = self.delnode.left
                else:
                    self.fathernode.right = self.delnode.right


    #找到当前结点下子树的最大值，即一直往该结点的右子结点找就行
    def findmaxvalue(self):
        if self.right.right != None:
            self.right.findmaxvalue()
        else:
            covervalue = self.right.value
            return covervalue,self
    #找到待删除结点的父结点
    def findcurfathernode(self,value):
        if self.right != None and self.right.value == value:
            # print("111",self.value)
            return self
        elif self.left != None and self.left.value == value:
            # print("222",self.value)
            return self
        else:
            if self.value > value:
                self = self.left.findcurfathernode(value)
            else:
                self = self.right.findcurfathernode(value)
        # print("113331",self.value)
        return self


    
bst = BinarySortTree()
node1 = Node(1)
node3 = Node(3)
node5 = Node(5)
node7 = Node(7)
node9 = Node(9)
node10 = Node(10)
node12 = Node(12)
node2 = Node(2)
bst.add(node7)
bst.add(node3)
bst.add(node10)
bst.add(node12)
bst.add(node5)
bst.add(node1)
bst.add(node9)
bst.add(node2)
bst.infixOrder()
bst.delete(12)
bst.infixOrder()

4.AVL树的介绍：
AVL 树是一种平衡二叉树，得名于其发明者的名字（ Adelson-Velskii 以及 Landis）。（可见名字长的好处，命名都能多占一个字母出来）。平衡二叉树递归定义如下：
左右子树的高度差小于等于 1。
其每一个子树均为平衡二叉树。

平衡因子： 某个结点的左子树的高度减去右子树的高度得到的差值。
基于平衡因子，我们就可以这样定义 AVL 树。
AVL 树： 所有结点的平衡因子的绝对值都不超过 1 的二叉树。

为了计算平衡因子，我们自然需要在节点中引入高度这一属性。在这里，我们把节点的高度定义为其左右子树的高度的最大值。代码如下：

def height(self,node):
        if node == None:
            return 0
        else:
            return max(self.height(node.left),self.height(node.right))+1

当平衡因子的绝对值大于 1 时，就会触发树的平衡化操作。

树的平衡化操作
二叉树的平衡化有两大基础操作： 左旋和右旋。左旋，即是逆时针旋转；右旋，即是顺时针旋转。这种旋转在整个平衡化过程中可能进行一次或多次，这两种操作都是从失去平衡的最小子树根结点开始的(即离插入结点最近且平衡因子超过1的祖结点)。
需要平衡的四种情况
LL 型
RR 型
LR 型
RL 型

AVL 树的插入和删除操作
基于上文的再平衡操作，现在我们可以写出完整的 AVL 树的插入/删除操作。
代码是基于BST树进行开发的，但是AVL树的删除还没有写，（太懒了～）

代码实现

class AVLTree():
    def __init__(self):
        self.root = None
    def add(self,node):
        if self.root == None:
            self.root = node
        else:
            self.root.add(node)
    def infixOrder(self):
        if self.root == None:
            print("None")
        else:
            self.root.infixOrder()
    def delete(self,value):
        if self.root == None:
            print("None")
        else:
            self.root.delete(value)
    def height(self):
        if self.root == None:
            return 0
        else:
            print("height",self.root.height(self.root))
        

class Node():
    def __init__(self,value=None):
        self.value = value
        self.left = None
        self.right = None
        self.root = None
        self.leftheight = 0
        self.rightheight = 0
    #获得当前结点的深度
    def height(self,node):
        if node == None:
            return 0
        else:
            return max(self.height(node.left),self.height(node.right))+1
    def add(self,insertnode):
        # print("111",self.value)
        if insertnode.value < self.value:
            if self.left != None:
               self.left.add(insertnode)
            else:
                self.left = insertnode
        elif insertnode.value > self.value:
            if self.right != None:
                self.right.add(insertnode)
            else:
                self.right = insertnode
        #1.首先我知道如果添加一个结点，只会影响它所在的树的深度，因此只需要找到它的爷爷及以上，再去判断深度，就可以平衡了
        #2.问题是怎么从爷爷往根结点找，这会儿又忘了这是个递归的过程，我递归的从根结点一直往待插入结点的父结点找插入位置，完事之后回一直返回，这样就能从爷爷找到根结点了
        # print("222",self.value)
        if self.height(self.left) - self.height(self.right) >1:
            if insertnode.value < self.left.value:
    
                self.ll()
            else:
                self.lr()
        elif self.height(self.right) - self.height(self.left) >1:
            if insertnode.value < self.right.value:
                self.rl()
            else:
                self.rr()

    def infixOrder(self):
        if self.left != None:
            self.left.infixOrder()
        print(self.value)
        if self.right != None:
            self.right.infixOrder()
    
    def delete(self,value):
        #判断是否为根结点：
        if self.value == value:
            self.covervalue,self.covervaluefather = self.left.findmaxvalue()
            self.value = self.covervalue
            self.covervaluefather.right = None
            return 
        #找到删除结点父结点
        # print(self.value)
        self.fathernode= self.findcurfathernode(value)
        #找到删除结点
        if self.fathernode.left != None and self.fathernode.left.value == value:
            self.delnode = self.fathernode.left
        elif self.fathernode.right != None and self.fathernode.right.value == value:
            self.delnode = self.fathernode.right
        #判断删除结点的三种形态
        #1.删除结点左右子结点均为空
        if self.delnode.left == None and self.delnode.right == None:
            if self.fathernode.left != None and self.fathernode.left.value == value:
                self.fathernode.left = None
            else:
                self.fathernode.right = None   

        #2.删除结点左右子结点均不为空
        elif self.delnode.left != None and self.delnode.right != None:
            #找当前结点左子树的最大值，删除该结点并把该结点的值给当前结点
            if self.delnode.left.right == None:
                self.delnode.value = self.delnode.left.value
                self.delnode.left = None
            else:
                self.covervalue,self.covervaluefather = self.delnode.left.findmaxvalue()
                self.delnode.value = self.covervalue
                self.covervaluefather.right = None
                

        #3.删除结点左子结点或右子结点其中一个为空
        else:
            if self.fathernode.left != None and self.fathernode.left.value == value:
                if self.delnode.left != None:
                    self.fathernode.left = self.delnode.left
                else:
                    self.fathernode.left = self.delnode.right
            else:
                if self.delnode.left != None:
                    self.fathernode.right = self.delnode.left
                else:
                    self.fathernode.right = self.delnode.right
        
        
        
    #找到当前结点下子树的最大值，即一直往该结点的右子结点找就行
    def findmaxvalue(self):
        if self.right.right != None:
            self.right.findmaxvalue()
        else:
            covervalue = self.right.value
            return covervalue,self
    #找到待删除结点的父结点
    def findcurfathernode(self,value):
        if self.right != None and self.right.value == value:
            # print("111",self.value)
            return self
        elif self.left != None and self.left.value == value:
            # print("222",self.value)
            return self
        else:
            if self.value > value:
                self = self.left.findcurfathernode(value)
            else:
                self = self.right.findcurfathernode(value)
        # print("113331",self.value)
        return self
    def rr(self):
        #右右-> 左旋
        print("rr")
        head = Node()
        head.value = self.value
        head.left = self.left
        head.right = self.right.left
        self.value = self.right.value
        self.left = head
        self.right = self.right.right
    def ll(self):
        #左左 -> 右旋
        print("ll")
        head = Node()
        head.value = self.value
        head.right = self.right 
        head.left = self.left.right
        self.value = self.left.value
        self.right = head
        self.left = self.left.left
    def lr(self):
        #左右先左旋再右旋
        print("lr")
        self.left.rr()
        self.ll()
    def rl(self):
        #右左先右旋再左旋
        print("rl")
        self.right.ll()
        self.rr()

    
bst = AVLTree()
node1 = Node(1)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node7 = Node(7)
node8 = Node(8)
node9 = Node(9)
node10 = Node(10)
node11 = Node(11)
node12 = Node(12)
node13 = Node(13)
node14 = Node(14)
node15 = Node(15)
bst.add(node13)
bst.add(node11)
bst.add(node14)
bst.add(node10)
bst.add(node12)
bst.add(node15)
bst.add(node9)
# bst.add(node15)
# bst.add(node9)
# bst.add(node2)
# bst.add(node3)
# bst.infixOrder()
bst.delete(9)
# bst.infixOrder()
# bst.height()
print(bst.root.value)
print(bst.root.left.value)
print(bst.root.right.value)
print(bst.root.left.left.value)
print(bst.root.left.right.value)
# print(bst.root.right.left.value)
print(bst.root.right.right.value)
# print(bst.root.left.left.left.value)
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容