https://leetcode.com/problems/contains-duplicate-iii/

BST.py

class Solution(object):
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        """
        :type nums: List[int]
        :type k: int
        :type t: int
        :rtype: bool
        """
        if not nums:
            return False

        #build tree
        bTree = BinaryTree(Node(0, nums[0]))
        for i in range(1, len(nums)):
            newNode = bTree.insert(Node(i, nums[i]))
            if i > k:
                bTree.remove(bTree.locate(nums[i - k - 1], i - k - 1))
            diff = t + 1

            if bTree.successor(newNode):
                diff = bTree.successor(newNode).val - newNode.val
                if diff <= t:
                    return True
            if bTree.predecessor(newNode):
                diff = newNode.val - bTree.predecessor(newNode).val
                if diff <= t:
                    return True
        return False

class BinaryTree(object):
    def __init__(self, root):
        self.root = root

    def locate(self, val, id):
        node = self.root
        while node and node.ind != id:
            if val < node.val:
                node = node.left
            else:
                node = node.right
        if val != node.val:
            return None
        else:
            return node

    def insert(self, node):
        cur = self.root
        while cur != None:
            preCur = cur
            if node.val < cur.val:
                cur = cur.left
            else:
                cur = cur.right
        node.p = preCur
        if not preCur:
            self.root = node
        elif preCur.val > node.val:
            preCur.left = node
        else:
            preCur.right = node
        return node

    def remove(self, node):
        if not node.left:
            self.__transplant(node, node.right)
        elif not node.right:
            self.__transplant(node, node.left)
        else:
            cur = self.min(node.right)
            if cur.p != node:
                self.__transplant(cur, cur.right)
                cur.right = node.right
                node.right.p = cur
            self.__transplant(node, cur)
            cur.left = node.left
            node.left.p = cur

    def __transplant(self, nodeA, nodeB):
        if not nodeA.p:
            self.root = nodeB
        elif nodeA == nodeA.p.left:
            nodeA.p.left = nodeB
        elif nodeA == nodeA.p.right:
            nodeA.p.right = nodeB
        if nodeB:
            nodeB.p = nodeA.p

    def max(self, node):
        cur = node
        while cur.right:
            cur = cur.right
        return cur

    def min(self, node):
        cur = node
        while cur.left:
            cur = cur.left
        return cur

    def successor(self, node):
        if node.right:
            return self.min(node.right)
        cur = node.p
        while cur and node == cur.right:
            node = cur
            cur = cur.p
        return cur

    def predecessor(self, node):
        if node.left:
            return self.max(node.left)
        cur = node.p
        while cur and node == cur.left:
            node = cur
            cur = cur.p
        return cur

class Node(object):
    def __init__(self, index, value):
        self.ind = index
        self.val = value
        self.p = None
        self.left = None
        self.right = None

def main():
    sol = Solution()
    print sol.containsNearbyAlmostDuplicate([], 0, 0)
    # nums = [15, 6, 18, 8 ,9 ,9, 3, 1]
    # bTree = BinaryTree(Node(0, nums[0]))
    # for i in range(1, len(nums)):
    #     bTree.insert(Node(i, nums[i]))
    # bTree.remove(bTree.root.left)
    # print bTree.root.left.right.val
    # print bTree.locate(9, 3)

if __name__ == '__main__':
    main()