python - 使用父指针在二叉搜索树中删除

Question

9 天来，我一直在尝试解决在线挑战。我有一个重复 100,000 次的在线插入删除，我需要找到它们的中位数。我尝试了两个堆，但意识到随机删除确实有效。我现在开始使用二进制搜索树，因为它们似乎在我的计算机上 2 秒内插入和删除 100,000 条数据。我正在研究 python，我需要在 16 秒内运行。

我已经在线查看了解决方案，但完全不能满足我的需求。我发现在插入和删除的同时计算中位数可能是一个很好的策略。我写了两个方法来获取节点的顺序后继或前导。

问题正如我所想的那样 - 在递归删除期间父指针分配不当。

我尝试了两种技术，但都效果不佳，如果能得到一些帮助，我将不胜感激!

代码:

import sys
class BSTNode:
    def __init__(self,x,parent):
        self.data = x
        self.left = None
        self.right = None
        self.count = 1
        self.parent = parent

def delete(x,T):
    if T is None:
        print('Element Not Found')
    elif x<T.data:
        T.left = delete(x,T.left)
    elif x>T.data:
        T.right = delete(x,T.right)
    elif T.left and T.right:
        TempNode = findMin(T.right)
        T.data = TempNode.data
        T.right = delete(TempNode.data,T.right)
    else:
        if T.left is None:
            T = T.right
        elif T.right is None:
            T = T.left
    return T

def findMin(T):
    if T.left:
        return findMin(T.left)
    else:
        return T

def insert(x,T,parent=None):
    if T is None:
        T = BSTNode(x,parent)
    elif x<T.data:
        T.left = insert(x,T.left,T)
    elif x>T.data:
        T.right = insert(x,T.right,T)
    else:
        T.count = T.count + 1
    return T

def inorder(T):
    if T is None:
        return
    else:
        inorder(T.left)
        b = back(T)
        if b:
            print("back:",b.data)
        print(T.data)
        n = next(T)
        if n:
            print("next:",n.data)
        inorder(T.right)

def preorder(T,i=0):
    if T is None:
        return
    else:
        for j in range(i):
            sys.stdout.write("    ")
        print(T.data)
        preorder(T.left,i+1)
        preorder(T.right,i+1)

def next(node):
    if node is None:
        return
    if node.right:
        n = node.right
        while n.left:
            n = n.left
        return n
    else:
        n = node
        while n.parent and n.parent.right is n:
            n = n.parent
        if n.parent and n.parent.left is n:
            return n.parent
        else:
            return

def back(node):
    if node is None:
        return
    if node.left:
        n = node.left
        while n.right:
            n = n.right
        return n
    else:
        n = node
        while n.parent and n.parent.left is n:
            n = n.parent
        if n.parent and n.parent.right is n:
            return n.parent
        else:
            return

T = None
T = insert(7,T)
T = insert(4,T)
T = insert(2,T)
T = insert(1,T)

T = insert(13,T)
T = insert(15,T)
T = insert(16,T)
T = insert(6,T)

T = insert(5,T)
T = insert(3,T)
T = insert(11,T)
T = insert(14,T)

T = insert(12,T)
T = insert(9,T)
T = insert(8,T)
T = insert(10,T)

T = delete(11,T)
T = delete(12,T)
T = delete(13,T)
T = delete(8,T)
preorder(T)
inorder(T)

输出

7
    4
        2
            1
            3
        6
            5
    14
        9
            10
        15
            16
1
('next:', 2)
('back:', 1)
2
('next:', 3)
('back:', 2)
3
('next:', 4)
('back:', 3)
4
('next:', 5)
('back:', 4)
5
('next:', 6)
('back:', 5)
6
('next:', 7)
('back:', 6)
7
('next:', 9)
9
('next:', 10)
('back:', 9)
10
('next:', 12)
('back:', 10)
14
('next:', 15)
('back:', 14)
15
('next:', 16)
('back:', 15)
16

预期 - 9 后面是 7

我的回答

def delete(x,T,parent=None):
    if T is None:
        print('Element Not Found')
    elif x<T.data:
        T.left = delete(x,T.left,T)
    elif x>T.data:
        T.right = delete(x,T.right,T)
    elif T.count==1:
        # 2 CHILDREN
        if T.left and T.right:
            TempNode = findMin(T.right)
            T.data = TempNode.data
            T.right = delete(TempNode.data,T.right,T)
        # 0 CHILDREN
        elif T.left is None and T.right is None:
            T = None
        # 1 CHILDREN
        elif T.right is not None:
            T = T.right
            T.parent = parent
        elif T.left is not None:
            T = T.left
            T.parent = parent
    else:
        T.count = T.count - 1
    return T

现在

9
    4
        2
            1
            3
        5
    14
        10
        15
            16
1 (2) 
('next:', 2)
('back:', 1)
2 (4) 
('next:', 3)
('back:', 2)
3 (2) 
('next:', 4)
('back:', 3)
4 (9) 
('next:', 5)
('back:', 4)
5 (4) 
('next:', 9)
('back:', 5)
9  
('next:', 10)
('back:', 9)
10 (14) 
('next:', 14)
('back:', 10)
14 (9) 
('next:', 15)
('back:', 14)
15 (14) 
('next:', 16)
('back:', 15)
16 (15)

Answer 1

您似乎没有在 else 中的 T = T.right 和 T = T.left 之后更新 T 的父指针: delete(x,T): 例程的一部分。另一种选择可能是在您替换左或右 child 时更新父指针。我认为在整个代码中始终遵循这两个约定中的任何一个一定能解决您的问题。