How to create a binary search tree on n vertices for o(n^2) ? The tree consists of vertices, each vertex has a pointer to the left and right subtrees and a key.

Closed due to the fact that the issue is too general for participants Denis Bubnov , Harry , rjhdby , αλεχολυτ , vp_arth 5 Mar '17 at 22:37 .

Please correct the question so that it describes the specific problem with sufficient detail to determine the appropriate answer. Do not ask a few questions at once. See “How to ask a good question?” For clarification. If the question can be reformulated according to the rules set out in the certificate , edit it .

  • one
    Are you sure that the word быстрое applicable here?) The easiest option is to sort first. Difficulty n log n will be - pavel
  • Have you tried to create it yourself (for example, according to the description in Wikipedia )? What problems have you encountered? If someone writes you an example, it’s far from the fact that he is suitable for your task. - default locale
  • @pavel is the worst case ever - asdf
  • one
    @pavel agree, now I will add a structure to the question, formally you are right, but I have a standard structure - asdf
  • one
    @defaultlocale read about the difference about small and big - asdf

2 answers 2

Well, what a question - this is the answer)

 struct Tree{ int value; Tree* left; Tree* right; } Tree* convertToTree(vector<int>& arr, int l, int r){ if (l >= r) return 0; Tree * tmp = new Tree; tmp.value = arr[(l+r)/2]; tmp.left = convertToTree(arr, l , (l+r)/2); tmp.right = convertToTree(arr, (l+r)/2+1 ,r); return tmp; } Tree* convertToTree(vector<int>& arr){ arr.sort(); return convertToTree(arr,0,arr.size()); }
  • that is, for n! Will the options be the same tree? - asdf
  • @asdf why not. - pavel
  • That's interesting, is it pseudocode or does std::vector a sort method? - ampawd
  • @ampawd pseudocode. I showed that it is necessary to sort the vector). It seemed to me that the intention was clearer. - pavel

In the simplest version -

 struct Node { Node *left, *right; int value; Node(int value):value(value),left(nullptr),right(nullptr){} }; void addNode(Node*&root, int v) { if (root == nullptr) { root = new Node(v); return; } Node * cur = root; for(;;) { if (cur->value < v) { if (cur->right) { cur = cur->right; } else { cur->right = new Node(v); return; } } else { if (cur->left) { cur = cur->left; } else { cur->left = new Node(v); return; } } } }

I did not check the performance, but it is so simple that ... if anything, correct it :)

  • this works for O(n^2) - asdf
  • In the worst case, yes. On average - for O(n log n) - Harry
  • In standard terminology, when giving asymptotics, they mean the worst case; + I made it clear in the comments - asdf
  • 2
    Yes, as many as you like. I don’t understand why with such a high level of theoretical knowledge a simple practical task caused difficulties ... - Harry
  • @Harry well for a linear build is no longer a trivial task) but it seems as possible. - pavel