[数据结构与算法] 二叉排序树之平衡二叉排序树

二叉排序树

1. 二叉排序树

二叉排序树的检索

def bt_search(btree, key):
    bt = btree:
    while bt:
        if key < bt.val:
            bt = bt.left
        elif key > bt.val:
            bt = bt.right
        else:
            return bt.val
    
    return None

二叉排序树数据插入
思路:

• 若树为空,直接新建结点
• 若树不为空:
• • 应该向左走而左结点为空,插入;
• • 应该向右走而右结点为空,插入;
• • 覆盖原有结点

def bt_insert(btree, key):
    if btree is None:
        return TreeNode(key)
    bt = btree
    while True:
        if key < bt.val:
            if bt.letf is None:
                bt.left = TreeNode(key)
                return btree
            bt = bt.left
        elif key > bt.val:
            if bt.right is None:
                bt.right = Tree.Node(key)
                return btree
            bt = bt.right
        else:
            bt.val = key
            return btree

二叉排序树数据删除
思路:

• 找到待删除数值和它的父节点在树中的位置
• 若子结点的左子树为空,则直接将子节点的右子树挂到父节点,此处有3种情况
• • 父节点为空(子节点为根节点),则直接将根节点设为子节点的右子树
• • 子节点是父节点的左结点,则将子节点的右子树挂到父节点的左结点
• • 子节点是父节点的右结点,则将子节点的右子树挂到父节点的右结点
• 若子节点的左子树不为空,先找到左子树的最右结点,并将子节点的右子树挂到最右结点的右结点上,后续同样有三种情况
• • 父节点为空(子节点为根节点),则直接将根节点设为子节点的左子树
• • 子节点是父节点的左结点,则将子节点的左子树挂到父节点的左结点
• • 子节点是父节点的右结点,则将子节点的左子树挂到父节点的右结点

def delete(btree, key):
    bt = btree
    father, child = None, btree
    while child and child.val != key:
        father = child
        if key < child.val:
            child = child.left
        elif key > child.val:
            child = child.right
    if child is None:
        return 
    
    # 子节点左子树为空
    if child.left is None:
        if father is None:
            btree = child.right
        elif child is father.left:
            father.left = child.right
        else:
            father.right = child.right
        return btree

    # 子节点左子树不为空
    most_right = child.left
    while most_right.right:
        most_right = most_right.right
    
    most_right.right = child.right
    if father is None:
        btree = child.left
    elif child is father.left:
        father.left = child.left
    else:
        father.right = child.left
    return btree

2. 平衡二叉排序树

记结点左子树和右子树的高度差为平衡因子(Balance Factor),平衡因子的取值为-1,0,1.

• 如果数据插入位置到根节点途径上每一个结点的BF都为0,那么新插入的结点不会影响导致树失衡,此时只需更新途径上结点的BF值即可.
• 如果途径上结点BF值不全为0,则可以从插入节点位置沿着途径向上查找,找到第一个BF值不为0的结点,以该节点为根节点的树称为最小非平衡子树,后续的调整都在最小非平衡子树上进行. 记最小非平衡子树的根节点为a, 有左右两棵子树,BF都为0,但两棵树高度差1
• • 如果数据插入较低子树,则a的高度不变,且BF变为0.只需调整插入位置到a路径上结点的BF值即可,其他结点的BF值不变
• • 如果数据插入较高子树,则要调整高子树一部分数据到低子树中,以平衡高度.
• • • LL型调整,a左子树较高,新节点插入到左子树的左子树
• • • LR型调整,a左子树较高,新节点插入到左子树的右子树
• • • RR型调整,a右子树较高,新节点插入到右子树的左子树
• • • LL型调整,a右子树较高,新节点插入到左子树的左子树

LL调整

(1) 插入结点前,中序遍历的序列为 $A b B a C$AbBaC
(2) 插入结点后,导致结点a的BF变为2,不满足平衡二叉树的要求
(3) 要保持中序遍历的顺序不变,$A^{\prime} b B a C$A′bBaC,将b作为最小非平衡子树的根节点,$A^{\prime}$A′为左子树,$BaC$BaC为右子树,即可达到平衡.

给树节点增加一个BF属性:

class TreeNode():
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        self.bf = 0

LL调整python实现:

def LL(a, b):
    a.left = b.right
    b.right = a

    a.bf = 0
    b.bf = 0
    return b

RR调整
RR调整与LL调整类似:

def RR(a, b):
    a.right = b.left
    b.left = a

    a.bf = 0
    b.bf = 0
    return b

LR调整

(1) 记根节点a左子树的右子树的根节点为c.由于a是最小非平衡子树的跟,所以b,c的bf都为0,以a为根的中序遍历序列是$AbBcCaD$AbBcCaD
(2) 新节点可能插入c的左子树(B)或右子树©,插入后b结点的BF=-1, a结点的BF为2,失衡!
(3) 将c提升为最小非平衡子树的根节点,左右结点分别为b,a,如图所示,中序遍历的结果为$AbB^{\prime}cCaD$AbB′cCaD 或$AbBcC^{\prime}aD$AbBcC′aD,保持不变,且c结点BF变为0,b和a结点的BF为-1,0或者1,取决于新节点位置.

def LR(a,b):
    c = b.right
    b.right = c.left
    c.left = b
    a.left = c.right
    c.right = a

    # 以下情况是失衡后二叉树的情况
    if c.bf == 0:# c本身为插入节点
        a.bf = b.bf = 0
    elif c.bf == 1: # 新节点在左子树
        b.bf = 0
        a.bf = -1
    else:   # 新节点在右子树
        b.bf = -1
        a.bf = 0
    
    c.bf = 0
    return c

c本身为插入结点的情况如下:

RL调整

def RL(a,b):
    c = b.left
    b.left = c.right
    c.right = b
    a.right = c.left
    c.left = a

    if c.bf == 0:
        a.bf = b.bf = 0
    elif c.bf == 1:
        a.bf = 0
        b.bf = -1
    else:
        a.bf = -1
        b.bf = 0
    c.bf = 0
    return c

平衡二叉排序树的插入操作:

• 查找新节点的插入位置,并在查找过程中记录最小不平衡子树的根
• 修改插入位置到最小不平衡子树根路径上各节点的平衡因子
• 检查以a为根的子树是否失衡,若失衡则依据情况进行调整.

def insert(btree, key):
    if btree is None:
        return TreeNode(key)
    a = btree   # 最终是最小不平衡树的根
    p = btree   # 指针
    fa = None   # a的父节点
    q = None    # p的父节点

    # 1. 查找插入位置并记录最小非平衡树根节点
    while p:
        # 若BF值不为0,则有可能为最小不平衡树的结点
        if p.bf != 0:
            fa, a = q, p
        
        # 查找插入位置:
        if p.val == key:
            return btree
        elif key < p.val:
            q = p
            p = p.left
        else:
            q = p
            p = p.right
    # 2. 插入节点
    # 此时q是待插入结点的父节点
    node = TreeNode(key)
    if key < q.val:
        q.left = node
    else:
        q.right = node
    
    # 3. 更新BF值,只需更新插入位置到a结点路径上结点的BF值.
    # 先判断插入节点在a的左子树还是右子树
    if key < a.val:
        p = a.left  # 指针
        b = a.left  # a深度较大子树的根节点,用于后续调整
        d = 1
    else:
        p = a.right
        b = a.right
        d = -1

    while p != node:
        if key < p.val:
            p.bf = 1    # p原来BF为0
            p = p.left
        else:
            p.bf = -1
            p = p.right
        
    # 4. 判断是否需要调整
    if a.bf == 0:   # a本身平衡,无需调整
        a.bf = d
        return btree
    elif a.bf == -d:    # 增加的结点在较低的树上,无需调整
        a.bf = 0
        return btree
    else:   # 增加的结点在较高的树上
        if d == 1:  # 增加在左子树
            if b.bf == 1: # 增加在左子树的左子树
                b = LL(a, b)
            else:   # 增加在左子树的右子树
                b = LR(a, b)
        else:
            if b.bf == 1:
                b = RL(a, b)
            else:
                b = RR(a, b)
    
    # 5.将调整好的树接回去
    # a为根节点
    if pa is None:
        btree = b
    elif pa.left == a:
        pa.left = b
    else:
        pa.right = b
    
    return btree