I have been trying to solve an online problem within 9 days. I have an online delete insert with repetitions of 100,000, and I need to find the median of these. I tried two heaps, but to implement a random delete operation. Now I am in the binary search trees, as they seem to insert and delete 100,000 data in 2 seconds on my computer. I am working on python and I need to run in 16 seconds.
I have checked the solutions on-line, but I definitely do not answer my needs. I calculated the calculation median, while inserting and deleting can be a good strategy. This I wrote two methods that get as the successor or predecessor of the node.
The problem is that I realized that this is the wrong assignment of parent pointers during recursive deletion.
I tried two methods, both of which did not work well, I would appreciate it if I could help!
The code:
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)
Output
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
expected - back 9 - 7
my answer
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:
Now
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)