Codeforces Round #353 (Div. 2) D. Tree Construction 二叉搜索树

题目链接：

http://codeforces.com/contest/675/problem/D

题意：

给你一系列点，叫你构造二叉搜索树，并且按输入顺序输出除根节点以外的所有节点的父亲。

题解：

n有10^5，如果直接去建树，最会情况会O(n^2)t掉。

因此我们需要利用一些二叉搜索树的性质：

对于当前输入节点v，找出已经输入的最大的l和最小的r使得l<v<r。

由于输入v之前l和r中间是没有数的，所以l和r必定为祖先和后代的关系，如果不是的话，就会导致l和r中间还有数（l和r的公共祖先）

那么由于v必然会是l的右儿子或者r的左儿子，但现在这两个位置是不可能同时为空的（l和r的祖先和后代关系导致的），所以，真正能插入的地方就只有一个。

具体实现看代码。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<set>
 4 #include<map>
 5 #include<vector>
 6 using namespace std;
 7 
 8 set<int> numbers;
 9 map<int, int> lef, rig;
10 
11 int n;
12 void init() {
13     numbers.clear();
14     lef.clear(); rig.clear();
15 }
16 
17 int main() {
18     int v;
19     while (scanf("%d", &n) == 1 && n) {
20         init();
21         scanf("%d", &v);
22         numbers.insert(v);
23         vector<int> ans;
24         for (int i = 0; i < n - 1; i++) {
25             scanf("%d", &v);
26             set<int>::iterator it = numbers.upper_bound(v);
27             if (it != numbers.end() && lef[*it]==0) {
28                 ans.push_back(*it);
29                 lef[*it] = 1;
30             }
31             else {
32                 it--;
33                 ans.push_back(*it);
34                 rig[*it] = 1;
35             }
36             numbers.insert(v);
37         }
38         for (int i = 0; i < ans.size()-1; i++) printf("%d ", ans[i]);
39         printf("%d
", ans[ans.size() - 1]);
40     }
41     return 0;
42 }

贴一个avl模板代替set操作：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<set>
  4 #include<map>
  5 #include<vector>
  6 using namespace std;
  7 
  8 const int INF = 1e9+10;
  9 
 10 //AVL树节点信息
 11 class TreeNode
 12 {
 13 public:
 14     TreeNode() :lson(NULL), rson(NULL), freq(1), hgt(0) {}
 15     int data;//值
 16     int hgt;//高度
 17     unsigned int freq;//频率
 18     TreeNode* lson;//指向左儿子的地址
 19     TreeNode* rson;//指向右儿子的地址
 20 };
 21 //AVL树类的属性和方法声明
 22 class AVLTree
 23 {
 24 private:
 25     TreeNode* root;//根节点
 26     void insertpri(TreeNode* &node,int x,int &pre,int &aft);//插入
 27     int height(TreeNode* node);//求树的高度
 28     void SingRotateLeft(TreeNode* &k2);//左左情况下的旋转
 29     void SingRotateRight(TreeNode* &k2);//右右情况下的旋转
 30     void DoubleRotateLR(TreeNode* &k3);//左右情况下的旋转
 31     void DoubleRotateRL(TreeNode* &k3);//右左情况下的旋转
 32     int Max(int cmpa, int cmpb);//求最大值
 33 public:
 34     AVLTree() :root(NULL) {}
 35     void insert(int x,int &pre,int &aft);//插入接口
 36 };
 37 //计算节点的高度
 38 int AVLTree::height(TreeNode* node)
 39 {
 40     if (node != NULL)
 41         return node->hgt;
 42     return -1;
 43 }
 44 //求最大值
 45 int AVLTree::Max(int cmpa, int cmpb)
 46 {
 47     return cmpa>cmpb ? cmpa : cmpb;
 48 }
 49 //左左情况下的旋转
 50 void AVLTree::SingRotateLeft(TreeNode* &k2)
 51 {
 52     TreeNode* k1;
 53     k1 = k2->lson;
 54     k2->lson = k1->rson;
 55     k1->rson = k2;
 56 
 57     k2->hgt = Max(height(k2->lson), height(k2->rson)) + 1;
 58     k1->hgt = Max(height(k1->lson), k2->hgt) + 1;
 59     k2 = k1;
 60 }
 61 //右右情况下的旋转
 62 void AVLTree::SingRotateRight(TreeNode* &k2)
 63 {
 64     TreeNode* k1;
 65     k1 = k2->rson;
 66     k2->rson = k1->lson;
 67     k1->lson = k2;
 68 
 69     k2->hgt = Max(height(k2->lson), height(k2->rson)) + 1;
 70     k1->hgt = Max(height(k1->rson), k2->hgt) + 1;
 71     k2 = k1;
 72 }
 73 //左右情况的旋转
 74 void AVLTree::DoubleRotateLR(TreeNode* &k3)
 75 {
 76     SingRotateRight(k3->lson);
 77     SingRotateLeft(k3);
 78 }
 79 //右左情况的旋转
 80 void AVLTree::DoubleRotateRL(TreeNode* &k3)
 81 {
 82     SingRotateLeft(k3->rson);
 83     SingRotateRight(k3);
 84 }
 85 //插入
 86 void AVLTree::insertpri(TreeNode* &node, int x,int &pre,int &aft)
 87 {
 88     if (node == NULL)//如果节点为空,就在此节点处加入x信息
 89     {
 90         node = new TreeNode();
 91         node->data = x;
 92         return;
 93     }
 94     if (node->data>x)//如果x小于节点的值,就继续在节点的左子树中插入x
 95     {
 96         aft = node->data;
 97         insertpri(node->lson, x,pre,aft);
 98         if (2 == height(node->lson) - height(node->rson))
 99             if (x<node->lson->data)
100                 SingRotateLeft(node);
101             else
102                 DoubleRotateLR(node);
103     }
104     else if (node->data<x)//如果x大于节点的值,就继续在节点的右子树中插入x
105     {
106         pre = node->data;
107         insertpri(node->rson, x,pre,aft);
108         if (2 == height(node->rson) - height(node->lson))//如果高度之差为2的话就失去了平衡,需要旋转
109             if (x>node->rson->data)
110                 SingRotateRight(node);
111             else
112                 DoubleRotateRL(node);
113     }
114     else ++(node->freq);//如果相等,就把频率加1
115     node->hgt = Max(height(node->lson), height(node->rson)) + 1;
116 }
117 //插入接口
118 void AVLTree::insert(int x,int &pre,int &aft)
119 {
120     insertpri(root, x,pre,aft);
121 }
122 
123 map<int, int> lef, rig;
124 
125 int n;
126 void init() {
127     lef.clear(); rig.clear();
128 }
129 
130 int main() {
131     int v,pre,aft;
132     while (scanf("%d", &n) == 1 && n) {
133         AVLTree tree;
134         init();
135         scanf("%d", &v);
136         tree.insert(v, pre, aft);
137         vector<int> ans;
138         for (int i = 0; i < n - 1; i++) {
139             scanf("%d", &v);
140             pre = 0, aft = INF;
141             tree.insert(v, pre, aft);
142             //printf("pre:%d,aft:%d
", pre, aft);
143             if (aft!=INF && lef[aft] == 0) {
144                 ans.push_back(aft);
145                 lef[aft] = 1;
146             }
147             else {
148                 ans.push_back(pre);
149                 rig[pre] = 1;
150             }
151         }
152         for (int i = 0; i < ans.size() - 1; i++) printf("%d ", ans[i]);
153         printf("%d
", ans[ans.size() - 1]);
154     }
155     return 0;
156 }