Блог пользователя calmhandtitan

Binary search trees
Автор calmhandtitan, история, 8 лет назад, По-английски

Given two binary search trees with identical structure, same node value but just one node with different values, how can we determine this node (by determining the node I mean the path from root to this node).

An obvious solution is to do traversal for both the trees and keep track of the path. But this would take O(n).

My question is can we do better than O(n) for this problem?

  • Проголосовать: нравится
  • -12
  • Проголосовать: не нравится

»
8 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

We can do an algorithm with O(n) pre-calculation and O(log(n)) query: in each node, in addition to the value of the node, we also hold the sum of the subtree of the node. Then, in order to find the different node, we do a search like this:




search(node n1, node n2):
    -- n1 is the node from the first bst, n2 from the second one --
    if n1.value != n2.value then
       return pair(n1, n2)
    else if exists(n1.left_child) and (n1.left_child.sum != n2.left_child.sum) then
       return search(n1.left_child, n2.left_child)
    else
       return search(n1.right_child, n2.right_child)

This is O(depth of result node), which is equivalent with O(log(n))

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Shouldn't O(depth of result node) be upper bounded by O(n). Think of a path like BST, values inserted in increasing order, and last nodes mismatch.

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I had initially assumed that the question refers to balanced binary search trees (in which case, "depth of result node" <= log(n)). If we're talking about unbalanced binary search trees, then the problem's worst case seems to be O(n), as you said.

      → Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

If we aren't allowed to hold any additional data in each node, I think it is impossible in the worst case. If, for instance, we are at a node, and both children nodes have the same value, there is no way to decide in which child the result is (once again, if we aren't allowed to hold any additional data). In this case, the result node might be in the last node in which we look, which would lead to an O(n) worst case complexity.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Can someone give me some resources to learn binary trees and binary search trees? Also practice problems for it. I shall be thankful to him.

→ Ответить