Python中的树形数据结构: splay树

2023-04-11 00:00:00 python 数据结构 splay

Splay树是一种自平衡二叉搜索树,具有较好的平均和最坏情况时间复杂度。其特点在于,每次插入、查找或删除一个节点时,都将该节点通过一系列的旋转操作移动到根节点的位置,从而使树保持平衡。

下面是Python中实现Splay树的基本代码演示,其中使用字符串作为范例:

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class SplayTree:
    def __init__(self):
        self.root = None

    def zig(self, node):
        parent = node.right
        node.right = parent.left
        parent.left = node
        return parent

    def zag(self, node):
        parent = node.left
        node.left = parent.right
        parent.right = node
        return parent

    def splay(self, node):
        if node == None or node == self.root:
            return node
        parent = node.parent
        grandparent = parent.parent
        if grandparent == None:
            if node == parent.left:
                self.root = self.zag(parent)
            else:
                self.root = self.zig(parent)
        else:
            if parent == grandparent.left and node == parent.left:
                grandparent.left = self.zag(grandparent.left)
            elif parent == grandparent.right and node == parent.right:
                grandparent.right = self.zig(grandparent.right)
            elif parent == grandparent.left and node == parent.right:
                grandparent.left = self.zig(parent)
                grandparent.left = self.zag(grandparent.left)
            else:
                grandparent.right = self.zag(parent)
                grandparent.right = self.zig(grandparent.right)
            self.splay(node)

    def insert(self, value):
        node = Node(value)
        if self.root == None:
            self.root = node
        else:
            parent = None
            temp = self.root
            while temp != None:
                parent = temp
                if value < temp.value:
                    temp = temp.left
                else:
                    temp = temp.right
            node.parent = parent
            if value < parent.value:
                parent.left = node
            else:
                parent.right = node
            self.splay(node)

    def search(self, value):
        temp = self.root
        while temp != None and temp.value != value:
            if value < temp.value:
                temp = temp.left
            else:
                temp = temp.right
        if temp != None:
            self.splay(temp)
        return temp

    def delete(self, value):
        node = self.search(value)
        if node == None:
            return
        if node.left == None:
            replace = node.right
            if replace != None:
                replace.parent = None
        elif node.right == None:
            replace = node.left
            if replace != None:
                replace.parent = None
        else:
            replace = node.left
            while replace.right != None:
                replace = replace.right
            if replace.parent != node:
                replace.parent.right = replace.left
                if replace.left != None:
                    replace.left.parent = replace.parent
                replace.left = node.left
                replace.left.parent = replace
            replace.right = node.right
            replace.right.parent = replace
        if node.parent == None:
            self.root = replace
        elif node == node.parent.left:
            node.parent.left = replace
        else:
            node.parent.right = replace
        if replace != None:
            self.splay(replace)

# sample usage
tree = SplayTree()
tree.insert("pican")
tree.insert("dang")
tree.insert("cheng")
tree.insert("gong")
tree.insert("ming")
tree.search("gong")

相关文章