小编点评

**Node Rotation and Insertion in a Binary Search Tree** **Node Rotation** - `rotate_left()` and `rotate_right()` methods allow you to rotate the tree left or right by 90 degrees. - These methods find the minimum (leftmost) node in the right subtree of the current node and replace the current node with this minimum node. - The `bf` (balance factor) of the current node is updated accordingly. **Insertion** - `insert_no_rec()` method inserts a new node in the tree without recursion. - It follows a similar approach to the binary search tree insertion, but it updates the balance factor accordingly. - The tree is traversed from the left child of the current node to the right child. **Code Structure** The code uses a base class `BiTreeNode` and an abstract class `AVLNode` that inherits from `BiTreeNode`. - `AVLNode` class handles the rotation and insertion logic. - `BiTreeNode` provides basic binary tree functionality, including `root` and `bf` attributes. **Algorithm** **Insertion:** 1. Find the insertion node's position in the tree. 2. Update the `bf` of the current node. 3. Traverse the tree from the left child to the right child. 4. Replace the current node with the minimum (leftmost) node in the right subtree. 5. Update the `bf` of the current node. **Rotation:** 1. Find the minimum (leftmost) node in the right subtree of the current node. 2. Replace the current node with this minimum node. 3. Update the `bf` of the current node. 4. Traverse the tree from the left child to the right child. 5. Connect the left or right child of the current node to the new child. **Additional Notes** - The code assumes that the tree is balanced initially. - The `rotate_right_left()` and `rotate_left()` methods use a technique called "zig-zag rotation" to adjust the balance factor. - The code uses a base tree with `TreeNode` objects, but it can be extended to handle different binary tree implementations.

正文

博客地址：https://www.cnblogs.com/zylyehuo/

• 

bst.py

# -*- coding: utf-8 -*-
 
 
# 构造二叉树
class BiTreeNode:
    def __init__(self, data):
        self.data = data
        self.lchild = None  # 左孩子
        self.rchild = None  # 右孩子
        self.parent = None  # 父亲节点
 
 
# 构造二叉搜索树
class BST:
    def __init__(self, li=None):
        self.root = None
        if li:
            for val in li:
                self.insert_no_rec(val)
 
    # 插入--递归方法
    def insert(self, node, val):
        if not node:
            node = BiTreeNode(val)
        elif val < node.data:
            node.lchild = self.insert(node.lchild, val)
            node.lchild.parent = node
        elif val > node.data:
            node.rchild = self.insert(node.rchild, val)
            node.rchild.parent = node
        return node
 
    # 插入--非递归方法
    def insert_no_rec(self, val):
        p = self.root
        if not p:  # 空树
            self.root = BiTreeNode(val)
            return
        while True:
            if val < p.data:
                if p.lchild:
                    p = p.lchild
                else:  # 左孩子不存在
                    p.lchild = BiTreeNode(val)
                    p.lchild.parent = p
                    return
            elif val > p.data:
                if p.rchild:
                    p = p.rchild
                else:
                    p.rchild = BiTreeNode(val)
                    p.rchild.parent = p
                    return
            else:
                return
 
    # 查询--递归方法
    def query(self, node, val):
        if not node:
            return None
        if node.data < val:
            return self.query(node.rchild, val)
        elif node.data > val:
            return self.query(node.lchild, val)
        else:
            return node
 
    # 查询--非递归方法
    def query_no_rec(self, val):
        p = self.root
        while p:
            if p.data < val:
                p = p.rchild
            elif p.data > val:
                p = p.lchild
            else:
                return p
        return None
 
    # 前序遍历
    def pre_order(self, root):
        if root:
            print(root.data, end=',')
            self.pre_order(root.lchild)
            self.pre_order(root.rchild)
 
    # 中序遍历
    def in_order(self, root):
        if root:
            self.in_order(root.lchild)
            print(root.data, end=',')
            self.in_order(root.rchild)
 
    # 后序遍历
    def post_order(self, root):
        if root:
            self.post_order(root.lchild)
            self.post_order(root.rchild)
            print(root.data, end=',')
 
    # 情况1：要删除的 node 是叶子节点 ==> 直接删除
    # 两个下划线代表私有方法
    def __remove_node_1(self, node):
        if not node.parent:
            self.root = None
        if node == node.parent.lchild:  # node是它父亲的左孩子
            node.parent.lchild = None
        else:  # 右孩子
            node.parent.rchild = None
 
    # 情况2.1：要删除的 node 只有一个左孩子 ==> 将此节点的父亲与孩子连接，然后删除该节点
    def __remove_node_21(self, node):
        if not node.parent:  # 根节点
            self.root = node.lchild
            node.lchild.parent = None
        elif node == node.parent.lchild:
            node.parent.lchild = node.lchild
            node.lchild.parent = node.parent
        else:
            node.parent.rchild = node.lchild
            node.lchild.parent = node.parent
 
    # 情况2.2：要删除的 node 只有一个右孩子 ==> 将此节点的父亲与孩子连接，然后删除该节点
    def __remove_node_22(self, node):
        if not node.parent:
            self.root = node.rchild
        elif node == node.parent.lchild:
            node.parent.lchild = node.rchild
            node.rchild.parent = node.parent
        else:
            node.parent.rchild = node.rchild
            node.rchild.parent = node.parent
 
    # 删除节点
    def delete(self, val):
        if self.root:  # 不是空树
            node = self.query_no_rec(val)
            if not node:  # 不存在
                return False
            if not node.lchild and not node.rchild:  # 1. 叶子节点
                self.__remove_node_1(node)
            elif not node.rchild:  # 2.1 只有一个左孩子
                self.__remove_node_21(node)
            elif not node.lchild:  # 2.2 只有一个右孩子
                self.__remove_node_22(node)
            else:  # 情况3：要删除的 node 有两个孩子 ==> 将其右子树的最小节点（该节点最多有一个右孩子）删除，并替换当前节点
                min_node = node.rchild
                while min_node.lchild:
                    min_node = min_node.lchild
                node.data = min_node.data
                # 删除min_node
                if min_node.rchild:
                    self.__remove_node_22(min_node)
                else:
                    self.__remove_node_1(min_node)

# -*- coding: utf-8 -*-

from bst import BiTreeNode, BST


class AVLNode(BiTreeNode):
    def __init__(self, data):
        BiTreeNode.__init__(self, data)
        self.bf = 0  # 平衡因子


class AVLTree(BST):
    def __init__(self, li=None):
        BST.__init__(self, li)

    # 左旋
    def rotate_left(self, p, c):
        s2 = c.lchild
        p.rchild = s2
        if s2:
            s2.parent = p

        c.lchild = p
        p.parent = c

        p.bf = 0
        c.bf = 0
        return c

    # 右旋
    def rotate_right(self, p, c):
        s2 = c.rchild
        p.lchild = s2
        if s2:
            s2.parent = p

        c.rchild = p
        p.parent = c

        p.bf = 0
        c.bf = 0
        return c

    # 双旋转--右旋后左旋
    def rotate_right_left(self, p, c):
        g = c.lchild

        s3 = g.rchild
        c.lchild = s3
        if s3:
            s3.parent = c
        g.rchild = c
        c.parent = g

        s2 = g.lchild
        p.rchild = s2
        if s2:
            s2.parent = p
        g.lchild = p
        p.parent = g

        # 更新bf
        if g.bf > 0:
            p.bf = -1
            c.bf = 0
        elif g.bf < 0:
            p.bf = 0
            c.bf = 1
        else:  # 插入的是g
            p.bf = 0
            c.bf = 0
        return g

    # 双旋转--左旋后右旋
    def rotate_left_right(self, p, c):
        g = c.rchild

        s2 = g.lchild
        c.rchild = s2
        if s2:
            s2.parent = c
        g.lchild = c
        c.parent = g

        s3 = g.rchild
        p.lchild = s3
        if s3:
            s3.parent = p
        g.rchild = p
        p.parent = g

        # 更新bf
        if g.bf < 0:
            p.bf = 1
            c.bf = 0
        elif g.bf > 0:
            p.bf = 0
            c.bf = -1
        else:
            p.bf = 0
            c.bf = 0
        return g

    def insert_no_rec(self, val):
        # 1. 和BST一样，插入
        p = self.root
        if not p:  # 空树
            self.root = AVLNode(val)
            return
        while True:
            if val < p.data:
                if p.lchild:
                    p = p.lchild
                else:  # 左孩子不存在
                    p.lchild = AVLNode(val)
                    p.lchild.parent = p
                    node = p.lchild  # node 存储的就是插入的节点
                    break
            elif val > p.data:
                if p.rchild:
                    p = p.rchild
                else:
                    p.rchild = AVLNode(val)
                    p.rchild.parent = p
                    node = p.rchild
                    break
            else:  # val == p.data
                return

        # 2. 更新balance factor
        while node.parent:  # node.parent不空
            if node.parent.lchild == node:  # 传递是从左子树来的，左子树更沉了
                # 更新node.parent的bf -= 1
                if node.parent.bf < 0:  # 原来node.parent.bf == -1, 更新后变成-2
                    # 做旋转
                    # 看node哪边沉
                    g = node.parent.parent  # 为了连接旋转之后的子树
                    x = node.parent  # 旋转前的子树的根
                    if node.bf > 0:
                        n = self.rotate_left_right(node.parent, node)
                    else:
                        n = self.rotate_right(node.parent, node)
                    # 记得：把n和g连起来
                elif node.parent.bf > 0:  # 原来node.parent.bf = 1，更新之后变成0
                    node.parent.bf = 0
                    break
                else:  # 原来node.parent.bf = 0，更新之后变成-1
                    node.parent.bf = -1
                    node = node.parent
                    continue
            else:  # 传递是从右子树来的，右子树更沉了
                # 更新node.parent.bf += 1
                if node.parent.bf > 0:  # 原来node.parent.bf == 1, 更新后变成2
                    # 做旋转
                    # 看node哪边沉
                    g = node.parent.parent  # 为了连接旋转之后的子树
                    x = node.parent  # 旋转前的子树的根
                    if node.bf < 0:  # node.bf = 1
                        n = self.rotate_right_left(node.parent, node)
                    else:  # node.bf = -1
                        n = self.rotate_left(node.parent, node)
                    # 记得连起来
                elif node.parent.bf < 0:  # 原来node.parent.bf = -1，更新之后变成0
                    node.parent.bf = 0
                    break
                else:  # 原来node.parent.bf = 0，更新之后变成1
                    node.parent.bf = 1
                    node = node.parent
                    continue

            # 连接旋转后的子树
            n.parent = g
            if g:  # g不是空
                if x == g.lchild:
                    g.lchild = n
                else:
                    g.rchild = n
                break
            else:
                self.root = n
                break


tree = AVLTree([9, 8, 7, 6, 5, 4, 3, 2, 1])

# 前序遍历
tree.pre_order(tree.root)
print("")
# 中序遍历
tree.in_order(tree.root)