We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Balanced Trees
  4. Median Updates
  5. Discussions

Median Updates

  • roilylitter
     + 0 comments

    Done it with the AVL Tree. Every node of the tree tracks not only height but also size which allows to calculate the index of the node and therefore the median.

    def print_median(tree):
    if not tree:
        print("Wrong!")
        return

    if tree.root.size % 2:
        m = tree[(tree.root.size // 2) + (tree.root.size % 2)]
        if m is None:
            print("Wrong!")
        else:
            print(m.value)
    else:
        m1 = tree[(tree.root.size // 2) + (tree.root.size % 2)]
        m2 = tree[(tree.root.size // 2) + (tree.root.size % 2) + 1]

        if not m1 and not m2:
            print("Wrong!")
        else:
            print(round((m1.value + m2.value) / 2, 1) if (m1.value + m2.value) % 2 else (m1.value + m2.value) // 2)


def median(a, x):
    tree = AVL()

    for e in zip(a, x):
        if e[0] == 'a':
            tree.insert_value(e[1])
            print_median(tree)
        elif e[0] == 'r':
            m = tree.search_value(e[1])
            if m is None:
                print("Wrong!")
            else:
                tree.delete_value(e[1])
                print_median(tree)

    ` class AVL: def init(self): self.root = None

    def __len__(self):
    return self.len(self.root)

def __getitem__(self, idx):

    if idx == 0:
        return self.min_node(self.root)

    if not self.root or idx > self.root.size or idx < 0:
        raise IndexError()

    tmp = self.root
    elms = 0
    while tmp and not (idx == (elms + self.len(tmp.left) + 1)):
        if idx < (elms + self.len(tmp.left) + 1):
            tmp = tmp.left
        elif idx > (elms + self.len(tmp.left) + 1):
            elms += (self.len(tmp.left) + 1)
            tmp = tmp.right
    else:
        return tmp

    The rest of the AVL tree implementation you may find on geeksforgeeks.