Both O(log(n)) Red-Black Tree solution in Python
Just want to give another way to solve this problem. \n\nUnlike other solutions using Heap, Red-Black Tree solution has O(log(n)) time complexity for both addNu
Just want to give another way to solve this problem. \n\nUnlike other solutions using Heap, `Red-Black Tree` solution has `O(log(n))` time complexity for both `addNum` and `findMedian`.\n\nI also tried `Treap`, but always got TLE unfortunately.\n\n    class RedBlackTreeNode(object):\n        def __init__(self, val):\n            self.val = val\n            self.left = None\n            self.right = None\n            self.size = 1\n            self.isRed = True\n    \n    \n    class RedBlackTree(object):\n        def __init__(self):\n            self.root = None\n    \n        def sizeOf(self, node):\n            return node.size if node else 0\n    \n        @property\n        def size(self):\n            return self.sizeOf(self.root)\n    \n        def rotateLeft(self, root):\n            right = root.right\n    \n            root.size, right.size = self.sizeOf(\n                root.left) + self.sizeOf(right.left) + 1, root.size\n    \n            root.right = right.left\n            right.left = root\n    \n            right.isRed = root.isRed\n            root.isRed = True\n    \n            return right\n    \n        def rotateRight(self, root):\n            left = root.left\n    \n            root.size, left.size = self.sizeOf(\n                root.right) + self.sizeOf(left.right) + 1, root.size\n    \n            root.left = left.right\n            left.right = root\n    \n            left.isRed = root.isRed\n            root.isRed = True\n    \n            return left\n    \n        def flipColor(self, root):\n            root.left.isRed = False\n            root.right.isRed = False\n            root.isRed = True\n            return root\n    \n        def insertTo(self, root, val):\n            if not root:\n                return RedBlackTreeNode(val)\n    \n            if val > root.val:\n                root.right = self.insertTo(root.right, val)\n            else:\n                root.left = self.insertTo(root.left, val)\n    \n            if (root.right and root.right.isRed) and not (\n                    root.left and root.left.isRed):\n                root = self.rotateLeft(root)\n    \n            if (root.left and root.left.isRed) and (\n                    root.left.left and root.left.left.isRed):\n                root = self.rotateRight(root)\n    \n            if (root.left and root.left.isRed) and (\n                    root.right and root.right.isRed):\n                root = self.flipColor(root)\n    \n            root.size = sum(map(self.sizeOf, (root.left, root.right))) + 1\n            return root\n    \n        def insert(self, val):\n            self.root = self.insertTo(self.root, val)\n            self.root.isRed = False\n    \n        def searchK(self, k, root=None):\n            root = root or self.root\n    \n            size = self.sizeOf(root.left) + 1\n            if k == size:\n                return root.val\n    \n            return self.searchK(k, root.left) if k < size else self.searchK(\n                k - size, root.right)\n    \n    \n    class MedianFinder(object):\n        def __init__(self):\n            self.tree = RedBlackTree()\n    \n        def addNum(self, num):\n            self.tree.insert(num)\n    \n        def findMedian(self):\n            size = self.tree.size\n            if size & 1:\n                return self.tree.searchK(size + 1 >> 1)\n            return sum(map(self.tree.searchK, (size >> 1, size + 2 >> 1))) / 2.0
[]