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

Автор Shellhead96, история, 7 лет назад, По-английски

You are given an array of n integers. You need to insert these elements into 2 binary search trees(BSTs), such that maximum(height(BST-1), height(BST-2)) could be minimized. Elements can be inserted into BST in any order. (Constraints — 1<=n<=10^5)

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

»
7 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится
  1. Sort all numbers
  2. Build 1st BST over first half
  3. Build 2nd BST over second half

Building BST like that:

For interval [l, r] make element at (l + r) / 2 the root and apply the same process recursively for left child with interval [l, (l + r) / 2 - 1] and right child with interval [(l + r) / 2 + 1, r]

If you're not required to build them and all you need is minimized maximum height, note that to minimize the height we need to make the tree a complete binary tree, and a complete binary will have floor(log2(n)) levels assuming that a tree with a single node has height zero

If you use C++, you can calculate floor(log2(n)) with just:

int logn = 31 - __builtin_clz(n);
int max_height = 31 - __builtin_clz((n+1)/2);
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    But what about this condition:maximum(height(BST-1), height(BST-2)) could be minimized??

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

      If I understood him correctly, maximum(height(BST-1), height(BST-2)) will be equal to log2(n / 2).