数据结构实验14-二叉平衡树和amp;B-树

A. DS查找—二叉树平衡因子

题目描述

二叉树用数组存储，将二叉树的结点数据依次自上而下,自左至右存储到数组中，一般二叉树与完全二叉树对比，比完全二叉树缺少的结点在数组中用0来表示。

计算二叉树每个结点的平衡因子，并按后序遍历的顺序输出结点的平衡因子。

--程序要求--

若使用C 只能include一个头文件iostream；若使用C语言只能include一个头文件stdio

程序中若include多过一个头文件，不看代码，作0分处理

不允许使用第三方对象或函数实现本题的要求

输入

测试次数t

每组测试数据一行，数组元素个数n，后跟n个字符，二叉树的数组存储。

2
6 ABC00D
24 ABCD0EF0000H00000000000I

输出

对每组测试数据，按后序遍历的顺序输出树中结点的平衡因子（测试数据没有空树）

B 0
D 0
C 1
A -1
D 0
B 1
I 0
H 1
E 2
F 0
C 2
A -2
 

1.  
   #include <iostream>
2.  
   using namespace std;
3.  
    
4.  
   int max(int a, int b)
5.  
   {
6.  
   if (a > b)return a;
7.  
   else return b;
8.  
   }
9.  
    
10.  
    void display(int i, char* array, int* b)//递归
11.  
    {
12.  
    if (array[2 * i] != '0')
13.  
    {
14.  
    display(2 * i, array, b);
15.  
    }
16.  
    if (array[2 * i 1] != '0')
17.  
    {
18.  
    display(2 * i 1, array, b);
19.  
    }
20.  
    cout << array[i] << " " << b[i] << endl;//后序遍历，左子树后右子树，之后输出
21.  
    }
22.  
     
23.  
     
24.  
    int main()
25.  
    {
26.  
    int t;
27.  
    cin >> t;
28.  
    while (t--)
29.  
    {
30.  
    int n;
31.  
    cin >> n;
32.  
    char* array = new char[1000];//初始值都先赋值为零
33.  
    for (int i = 0; i < 1000; i )
34.  
    {
35.  
    array[i] = '0';
36.  
    }
37.  
    int* balance = new int[1000];
38.  
    int* depth = new int[1000];
39.  
    for (int i = 0; i < 1000; i )
40.  
    {
41.  
    balance[i] = depth[i] = 0;
42.  
    }
43.  
     
44.  
    for (int i = 1; i <= n; i )
45.  
    {
46.  
    cin >> array[i];
47.  
    }
48.  
     
49.  
    for (int i = n; i >= 1; i--)//从后往前进行高度的计算
50.  
    {
51.  
    if (array[i] == '0')depth[i] = 0;
52.  
    else depth[i] = max(depth[2 * i], depth[2 * i 1]) 1;
53.  
    }
54.  
     
55.  
    for (int i = 1; i <= n; i )
56.  
    {
57.  
    balance[i] = depth[2 * i] - depth[2 * i 1];//平衡因子的计算，左子树高度-右子树高度
58.  
    }
59.  
     
60.  
    display(1, array, balance);//递归
61.  
    }
62.  
     
63.  
    }
64.  
    //平衡因子，字面意思，其实就是探讨左右是否平衡，如果不是，那么其中差了多少。
65.  
    //然后规定了使用左子树的高度-右子树的高度=平衡因子，仅此而已！
66.  
    //深度和高度在平衡二叉树中的区别就是，判断是否为平衡二叉树一般说深度，计算平衡因子一般说高度

B. DS二叉平衡树构建

题目描述

在初始为空的平衡二叉树中依次插入n个结点，请输出最终的平衡二叉树。

要求实现平衡二叉树，不可以使用各类库函数。

1.  
   #include <iostream>
2.  
   using namespace std;
3.  
    
4.  
   #define LH 1 // 左高
5.  
   #define EH 0 // 等高
6.  
   #define RH -1 // 右高
7.  
    
8.  
   class BiNode
9.  
   {
10.  
    public:
11.  
    int key; // 关键值
12.  
    int bf; // 平衡因子
13.  
    BiNode *lChild, *rChild;
14.  
    BiNode(int kValue, int bValue)
15.  
    {
16.  
     
17.  
    key = kValue;
18.  
    bf = bValue;
19.  
    lChild = NULL;
20.  
    rChild = NULL;
21.  
    }
22.  
     
23.  
    ~BiNode()
24.  
    {
25.  
    key = 0;
26.  
    bf = 0;
27.  
    lChild = NULL;
28.  
    rChild = NULL;
29.  
    }
30.  
    };
31.  
     
32.  
    // 二叉排序树
33.  
    class BST
34.  
    {
35.  
    private:
36.  
    BiNode *root; // 根结点指针
37.  
    void rRotate(BiNode *&p);
38.  
    void lRotate(BiNode *&p);
39.  
    void leftBalance(BiNode *&t);
40.  
    void rightBalance(BiNode *&t);
41.  
    int insertAVL(BiNode *&t, int key, bool &taller); // 插入元素并做平衡处理
42.  
    void inOrder(BiNode *p);
43.  
    public:
44.  
    BST();
45.  
    void insertAVL(int key); // 二叉排序树插入元素
46.  
    ~BST();
47.  
    void inOrder(); // 中序遍历
48.  
    };
49.  
     
50.  
    // 以p为根的二叉排序树作右旋处理
51.  
    void BST::rRotate(BiNode *&p)
52.  
    {
53.  
    // 参考课本236页算法9.9
54.  
    }
55.  
     
56.  
    // 以p为根的二叉排序树作左旋处理
57.  
    void BST::lRotate(BiNode *&p)
58.  
    {
59.  
    // 参考课本236页算法9.10
60.  
    }
61.  
     
62.  
    // t为根的二叉排序树作左平衡旋转处理
63.  
    void BST::leftBalance(BiNode *&t)
64.  
    {
65.  
    // 参考课本238页算法9.12
66.  
    }
67.  
     
68.  
    // t为根的二叉排序树作右平衡旋转处理
69.  
    void BST::rightBalance(BiNode *&t)
70.  
    {
71.  
    // 参考课本238页算法9.12
72.  
    }
73.  
     
74.  
     
75.  
    int BST::insertAVL(BiNode *&t, int key, bool &taller)
76.  
    {
77.  
     
78.  
    // 参考课本237页算法9.11
79.  
    }
80.  
     
81.  
    void BST::inOrder(BiNode *p)
82.  
    {
83.  
    if(p)
84.  
    {
85.  
    inOrder(p->lChild);
86.  
    cout << p->key << ':' << p->bf << ' ';
87.  
    inOrder(p->rChild);
88.  
    }
89.  
     
90.  
    return;
91.  
    }
92.  
     
93.  
    // 二叉排序树初始化
94.  
    BST::BST()
95.  
    {
96.  
    root = NULL;
97.  
    }
98.  
     
99.  
    BST::~BST()
100.  
     {
101.  
     root = NULL;
102.  
     }
103.  
      
104.  
     // 插入元素并作平衡处理
105.  
     void BST::insertAVL(int key)
106.  
     {
107.  
     bool taller = false;
108.  
     insertAVL(root, key, taller);
109.  
     }
110.  
      
111.  
      
112.  
     // 中序遍历
113.  
     void BST::inOrder()
114.  
     {
115.  
     inOrder(root);
116.  
     }
117.  
      
118.  
     int main(void)
119.  
     {
120.  
     int t;
121.  
     cin >> t;
122.  
     while(t --)
123.  
     {
124.  
     // 构建二叉平衡树，并在插入元素时做平衡处理
125.  
     int n, elem;
126.  
     cin >> n;
127.  
     BST tree;
128.  
     while(n --)
129.  
     {
130.  
     cin >> elem;
131.  
     tree.insertAVL(elem);
132.  
     }
133.  
     tree.inOrder();
134.  
     cout << endl;
135.  
     }
136.  
      
137.  
     return 0;
138.  
     }

输入

第一行输入测试数据组数t；

每组测试数据，第一行输入结点数n, 第二行输入n个结点值。

8
3
64 5 1
3
64 5 13
6
64 78 5 1 13 15
6
64 78 5 1 13 10
3
64 78 100
3
64 80 70
6
64 30 80 90 70 68
6
64 30 80 90 70 75

输出

对每组测试数据，按中序遍历的顺序输出树中，结点值及平衡因子（测试数据没有空树），即结点值：平衡因子，不同结点之间间隔一个空格。

1:0 5:0 64:0
5:0 13:0 64:0
1:0 5:1 13:0 15:0 64:0 78:0
1:0 5:0 10:0 13:0 64:-1 78:0
64:0 78:0 100:0
64:0 70:0 80:0
30:0 64:0 68:0 70:0 80:-1 90:0
30:0 64:1 70:0 75:0 80:0 90:0

这道题纯粹的考察平衡二叉树的算法，非常纯粹，只需要照抄书上代码即可，但是同样有几点是需要注意的。

第一点是：输入输出问题，这题居然卡输出，main代码都给好了，居然卡输出，真是无语，但是我将中序遍历输入的那堆东西存到数组里面去了，分别是a数组和b数组，所以最后是用数组进行输出便于格式正确。

第二点是insertavl函数里太多弯弯绕绕了，容易看花眼，所以一定要小心检查。

第三点是insertavl函数里有个new t，注意看清楚自己的构造函数不要再傻傻的new了

1.  
   #include <iostream>
2.  
   using namespace std;
3.  
    
4.  
   #define LH 1 // 左高
5.  
   #define EH 0 // 等高
6.  
   #define RH -1 // 右高
7.  
   int a[1000];
8.  
   int b[1000];
9.  
   int z;
10.  
     
11.  
     
12.  
    class BiNode
13.  
    {
14.  
    public:
15.  
    int key; // 关键值
16.  
    int bf; // 平衡因子
17.  
    BiNode* lChild, * rChild;
18.  
    BiNode(int kValue, int bValue)
19.  
    {
20.  
     
21.  
    key = kValue;
22.  
    bf = bValue;
23.  
    lChild = NULL;
24.  
    rChild = NULL;
25.  
    }
26.  
     
27.  
    ~BiNode()
28.  
    {
29.  
    key = 0;
30.  
    bf = 0;
31.  
    lChild = NULL;
32.  
    rChild = NULL;
33.  
    }
34.  
    };
35.  
     
36.  
    // 二叉排序树
37.  
    class BST
38.  
    {
39.  
    private:
40.  
    BiNode* root; // 根结点指针
41.  
    void rRotate(BiNode*& p);
42.  
    void lRotate(BiNode*& p);
43.  
    void leftBalance(BiNode*& t);
44.  
    void rightBalance(BiNode*& t);
45.  
    int insertAVL(BiNode*& t, int key, bool& taller); // 插入元素并做平衡处理
46.  
    void inOrder(BiNode* p);
47.  
    public:
48.  
    BST();
49.  
    void insertAVL(int key); // 二叉排序树插入元素
50.  
    ~BST();
51.  
    void inOrder(); // 中序遍历
52.  
    };
53.  
     
54.  
    // 以p为根的二叉排序树作右旋处理
55.  
    void BST::rRotate(BiNode*& p)
56.  
    {
57.  
    // 参考课本236页算法9.9
58.  
    BiNode* lc;//建立一个新的节点
59.  
    lc = p->lChild;//lc指向的*p的左子树根节点
60.  
    p->lChild = lc->rChild;//lc的左子树挂接为*p的左子树
61.  
    lc->rChild = p;
62.  
    p = lc;//p指向新的节点
63.  
     
64.  
    }
65.  
     
66.  
    // 以p为根的二叉排序树作左旋处理
67.  
    void BST::lRotate(BiNode*& p)
68.  
    {
69.  
    // 参考课本236页算法9.10
70.  
    BiNode* rc;
71.  
    rc = p->rChild;//rc指向的*p的右子树根节点
72.  
    p->rChild = rc->lChild;
73.  
    rc->lChild = p;
74.  
    p = rc;
75.  
    }
76.  
     
77.  
    // t为根的二叉排序树作左平衡旋转处理
78.  
    void BST::leftBalance(BiNode*& t)
79.  
    {
80.  
    // 参考课本238页算法9.12
81.  
    BiNode* lc;
82.  
    lc = t->lChild;
83.  
    switch (lc->bf)
84.  
    {
85.  
    case LH:
86.  
    t->bf = lc->bf = EH;
87.  
    rRotate(t);
88.  
    break;
89.  
    case RH:
90.  
    BiNode* rd;
91.  
    rd = lc->rChild;
92.  
    switch (rd->bf)
93.  
    {
94.  
    case LH:
95.  
    t->bf = RH;
96.  
    lc->bf = EH;
97.  
    break;
98.  
    case EH:
99.  
    t->bf = lc->bf = EH;
100.  
     break;
101.  
     case RH:
102.  
     t->bf = EH;
103.  
     lc->bf = LH;
104.  
     break;
105.  
     }
106.  
     rd->bf = EH;
107.  
     lRotate(t->lChild);
108.  
     rRotate(t);
109.  
     }
110.  
     }
111.  
      
112.  
     // t为根的二叉排序树作右平衡旋转处理
113.  
     void BST::rightBalance(BiNode*& t)
114.  
     {
115.  
     // 参考课本238页算法9.12
116.  
     //对指针T所致节点为根的二叉树作平衡旋转处理
117.  
     BiNode* rc;
118.  
      
119.  
     rc = t->rChild;
120.  
     //检查T节点的右孩子，根据其平衡因子判断是左旋还是右左双旋
121.  
     switch (rc->bf)
122.  
     {
123.  
     //右孩子的平衡因子为-1，平衡因子是直线，左旋
124.  
     case RH:
125.  
     t->bf = EH;
126.  
     rc->bf = EH;
127.  
     lRotate(t);
128.  
     break;
129.  
     //右孩子平衡因子为-1，平衡因子为折线，右左双旋
130.  
     case LH:
131.  
     BiNode* ld;
132.  
     ld = rc->lChild;
133.  
     //修改T节点和其右孩子的平衡因子
134.  
     switch (ld->bf)
135.  
     {
136.  
     case LH:
137.  
     t->bf = EH;
138.  
     rc->bf = RH;
139.  
     break;
140.  
     case EH:
141.  
     t->bf = rc->bf = EH;
142.  
     break;
143.  
     case RH:
144.  
     t->bf = LH;
145.  
     rc->bf = EH;
146.  
     break;
147.  
     }
148.  
     ld->bf = EH;
149.  
     rRotate(t->rChild);
150.  
     lRotate(t);
151.  
     }
152.  
     }
153.  
      
154.  
      
155.  
     int BST::insertAVL(BiNode*& t, int key, bool& taller)
156.  
     {
157.  
      
158.  
     // 参考课本237页算法9.11
159.  
     if (!t)
160.  
     {
161.  
     t = new BiNode(key, EH);
162.  
     taller = true;
163.  
     }
164.  
     else
165.  
     {
166.  
     if (t->key==key)
167.  
     {
168.  
     taller = false;
169.  
     return 0;
170.  
     }
171.  
      
172.  
     if (key < t->key)
173.  
     {
174.  
     if (!insertAVL(t->lChild, key, taller)) {
175.  
     taller = false;
176.  
     return 0;
177.  
     }
178.  
     if (taller)
179.  
     {
180.  
     switch (t->bf)
181.  
     {
182.  
     case LH:
183.  
     leftBalance(t);
184.  
     taller = false;
185.  
     break;
186.  
     case EH:
187.  
     t->bf = LH;
188.  
     taller = true;
189.  
     break;
190.  
     case RH:
191.  
     t->bf = EH;
192.  
     taller = false;
193.  
     break;
194.  
     }
195.  
     }
196.  
     }
197.  
     else
198.  
     {
199.  
     if (!insertAVL(t->rChild, key, taller))
200.  
     {
201.  
     taller = false;
202.  
     return 0;
203.  
     }
204.  
     if (taller)
205.  
     {
206.  
     switch (t->bf)
207.  
     {
208.  
     case LH:
209.  
     t->bf = EH;
210.  
     taller = false;
211.  
     break;
212.  
     case EH:
213.  
     t->bf = RH;
214.  
     taller = true;
215.  
     break;
216.  
     case RH:
217.  
     rightBalance(t);
218.  
     taller = false;
219.  
     break;
220.  
     }
221.  
     }
222.  
     }
223.  
     }
224.  
     return 1;
225.  
     }
226.  
      
227.  
     void BST::inOrder(BiNode* p)
228.  
     {
229.  
     if (p)
230.  
     {
231.  
     inOrder(p->lChild);
232.  
     //cout << p->key << ':' << p->bf << ' ';
233.  
     a[z] = p->key;
234.  
     b[z] = p->bf;
235.  
     z ;
236.  
     inOrder(p->rChild);
237.  
     }
238.  
      
239.  
     return;
240.  
     }
241.  
      
242.  
     // 二叉排序树初始化
243.  
     BST::BST()
244.  
     {
245.  
     root = NULL;
246.  
     }
247.  
      
248.  
     BST::~BST()
249.  
     {
250.  
     root = NULL;
251.  
     }
252.  
      
253.  
     // 插入元素并作平衡处理
254.  
     void BST::insertAVL(int key)
255.  
     {
256.  
     bool taller = false;
257.  
     insertAVL(root, key, taller);
258.  
     }
259.  
      
260.  
      
261.  
     // 中序遍历
262.  
     void BST::inOrder()
263.  
     {
264.  
     inOrder(root);
265.  
     }
266.  
      
267.  
     int main(void)
268.  
     {
269.  
     int t;
270.  
     cin >> t;
271.  
     while (t--)
272.  
     {
273.  
     // 构建二叉平衡树，并在插入元素时做平衡处理
274.  
     int n, elem;
275.  
     cin >> n;
276.  
     BST tree;
277.  
     int n1 = n;
278.  
     while (n--)
279.  
     {
280.  
     cin >> elem;
281.  
     tree.insertAVL(elem);
282.  
     }
283.  
     tree.inOrder();
284.  
     for (int i = 0; i < n1; i )
285.  
     {
286.  
     cout << a[i] << ":" << b[i];
287.  
     if (i != n1 - 1)
288.  
     cout << " ";
289.  
     if(t)
290.  
     cout << endl;
291.  
     z = 0;
292.  
     }
293.  
      
294.  
     return 0;
295.  
     }

C. 二叉平衡树练习

题目描述

对二叉平衡树进行四种操作：

1. 1 D K 表示插入一个新数据，数据为D用于输出，关键值为K用于排序；
2. 2 输出当前树中最大关键值所带的数据，并删除该数据，如果没有这个关键值，则输出0；
3. 3 输出当前树中最小关键值所带的数据，并删除该数据，如果没有这个关键值，则输出0；
4. 4 K 输出关键值为 K 的数据，并删除该数据，如果没有这个关键值，则输出0。

要求必须实现平衡树，不可以使用各类库函数

AVL代码模板参考:

1.  
   #include<stdio.h>
2.  
   const int maxn = 1e5 10;
3.  
   struct Node
4.  
   {
5.  
   int key; // 关键值
6.  
   int data; // 携带的数据
7.  
   int left; // 左子树地址（数组下标）
8.  
   int right; // 右子树地址（数组下标）
9.  
   int height; // 当前结点为根的子树高度
10.  
    void Init(){data = key = left = right = height = -1;}
11.  
    void Init(int k_, int d_=0){Init(); key = k_; data = d_;}
12.  
    Node(){Init();}
13.  
    Node(int k_, int d_=0){Init(k_, d_);}
14.  
    };
15.  
     
16.  
    Node tr[maxn];
17.  
    int root, tp; // root标记根节点位置，tp全局结点分配下标
18.  
     
19.  
    inline int UpdateHeight(int now)
20.  
    {
21.  
    // 更新 tr[now] 结点的子树高度，即tr[now].height的值
22.  
    }
23.  
    inline int HeightDiff(int now)
24.  
    {
25.  
    // 计算 tr[now] 结点的平衡因子
26.  
    }
27.  
    int LL(int an)
28.  
    {
29.  
    }
30.  
    int RR(int an)
31.  
    {
32.  
    }
33.  
    int LR(int an)
34.  
    {
35.  
    }
36.  
    int RL(int an)
37.  
    {
38.  
    }
39.  
    void Insert(int &now, int key, int data=0)
40.  
    {
41.  
    if(now == -1)
42.  
    {
43.  
    // 传入指针为空，新建结点保存数据
44.  
    now = tp;
45.  
    tr[now].Init(key, data);
46.  
    }
47.  
    // 判断插入哪个子树，插入数据，判断平衡因子，做正确旋转，更新高度
48.  
    }
49.  
    void Delete(int &now, int key)
50.  
    {
51.  
    if(now == -1) return;
52.  
    else if(key < tr[now].key) Delete(tr[now].left, key);
53.  
    else if(key > tr[now].key) Delete(tr[now].right, key);
54.  
    else
55.  
    {
56.  
    // 删除当前结点
57.  
    }
58.  
    // 处理树平衡
59.  
    }
60.  
     
61.  
    int main()
62.  
    {
63.  
    int n, op, key, data;
64.  
    while(scanf("%d", &n) != EOF)
65.  
    {
66.  
    for(root = tp = -1; n --; ) // 初始化根结点和“内存指针”
67.  
    {
68.  
    scanf("%d", &op);
69.  
    if(op == 1)
70.  
    {
71.  
    }
72.  
    else if(op == 2)
73.  
    {
74.  
    }
75.  
    else if(op == 3)
76.  
    {
77.  
    }
78.  
    else
79.  
    {
80.  
    }
81.  
    }
82.  
    return 0;
83.  
    }

输入

每组数据第一行n表示有n个操作

接下来n行操作内容

8
2
1 20 14
1 30 3
2
1 10 99
3
2
2

输出

按操作规则输出对应内容

0
20
30
10
0

1.  
   #include<iostream>
2.  
   #include<cstdio>
3.  
   #include <vector>
4.  
   using namespace std;
5.  
    
6.  
   int Max(int a, int b)
7.  
   {
8.  
   if (a<b)
9.  
   {
10.  
    return b;
11.  
    }
12.  
    else
13.  
    {
14.  
    return a;
15.  
    }
16.  
    }
17.  
    const int maxn = 1e5 10;
18.  
    struct Node
19.  
    {
20.  
    int key; // 关键值
21.  
    int data; // 携带的数据
22.  
    int left; // 左子树地址（数组下标）
23.  
    int right; // 右子树地址（数组下标）
24.  
    int height; // 当前结点为根的子树高度
25.  
    void Init() { data = key = left = right = height = -1; }
26.  
    void Init(int k_, int d_ = 0) { Init(); key = k_; data = d_; }
27.  
    Node() { Init(); }
28.  
    Node(int k_, int d_ = 0) { Init(k_, d_); }
29.  
    };
30.  
     
31.  
    Node tr[maxn];
32.  
    int root, tp; // root标记根节点位置，tp全局结点分配下标
33.  
     
34.  
    inline int UpdateHeight(int now)
35.  
    {
36.  
    // 更新 tr[now] 结点的子树高度，即tr[now].height的值
37.  
    return tr[now].height = Max(tr[tr[now].left].height, tr[tr[now].right].height) 1;
38.  
    }
39.  
    inline int HeightDiff(int now)
40.  
    {
41.  
    // 计算 tr[now] 结点的平衡因子
42.  
    return tr[tr[now].left].height - tr[tr[now].right].height;
43.  
    }
44.  
    int LL(int an)
45.  
    {
46.  
    int bn = tr[an].left;
47.  
    tr[an].left = tr[bn].right;
48.  
    tr[bn].right = an;
49.  
    UpdateHeight(an);
50.  
    UpdateHeight(bn);
51.  
    return bn;
52.  
    }
53.  
    int RR(int an)
54.  
    {
55.  
    int bn = tr[an].right;
56.  
    tr[an].right = tr[bn].left;
57.  
    tr[bn].left = an;
58.  
    UpdateHeight(an);
59.  
    UpdateHeight(bn);
60.  
    return bn;
61.  
    }
62.  
    int LR(int an)
63.  
    {
64.  
    tr[an].left = RR(tr[an].left);
65.  
    return LL(an);
66.  
    }
67.  
    int RL(int an)
68.  
    {
69.  
    tr[an].right = LL(tr[an].right);
70.  
    return RR(an);
71.  
    }
72.  
    void Insert(int& now, int key, int data = 0)
73.  
    {
74.  
    if (now == -1)
75.  
    {
76.  
    // 传入指针为空，新建结点保存数据
77.  
    now = tp;
78.  
    tr[now].Init(key, data);
79.  
    }
80.  
    // 判断插入哪个子树，插入数据，判断平衡因子，做正确旋转，更新高度
81.  
    else if (key < tr[now].key)
82.  
    {
83.  
    Insert(tr[now].left, key, data);
84.  
    if (HeightDiff(now) == 2)
85.  
    {
86.  
    if (key < tr[tr[now].left].key) now = LL(now);
87.  
    else now = LR(now);
88.  
    }
89.  
    }
90.  
    else if (key > tr[now].key)
91.  
    {
92.  
    Insert(tr[now].right, key, data);
93.  
    if (HeightDiff(now) == -2)
94.  
    {
95.  
    if (key > tr[tr[now].right].key) now = RR(now);
96.  
    else now = RL(now);
97.  
    }
98.  
    }
99.  
     
100.  
     UpdateHeight(now);
101.  
     }
102.  
      
103.  
     int FindMax(int now)
104.  
     {
105.  
     if (tr[now].right == 0)return -1;
106.  
     while (tr[now].right != -1) now = tr[now].right;
107.  
     return now;
108.  
     }
109.  
      
110.  
     int FindMin(int now)
111.  
     {
112.  
     if (tr[now].left == 0)return -1;
113.  
     while (tr[now].left != -1) now = tr[now].left;
114.  
     return now;
115.  
     }
116.  
     void Delete(int& now, int key)
117.  
     {
118.  
     if (now == -1) return;
119.  
     else if (key < tr[now].key) Delete(tr[now].left, key);
120.  
     else if (key > tr[now].key) Delete(tr[now].right, key);
121.  
     else
122.  
     {
123.  
     // 删除当前结点
124.  
      
125.  
     if (tr[now].left == -1 && tr[now].right == -1)
126.  
     {
127.  
     now = -1;
128.  
     return;
129.  
     }
130.  
     else if (tr[now].left != -1 && tr[now].right == -1)
131.  
     {
132.  
     now = tr[now].left;
133.  
     return;
134.  
     }
135.  
     else if (tr[now].left == -1 && tr[now].right != -1)
136.  
     {
137.  
     now = tr[now].right;
138.  
     return;
139.  
     }
140.  
     else
141.  
     {
142.  
     int maxLeftIndex = FindMax(tr[now].left);
143.  
     swap(tr[now].key, tr[maxLeftIndex].key);
144.  
     swap(tr[now].data, tr[maxLeftIndex].data);
145.  
     Delete(tr[now].left, tr[maxLeftIndex].key);
146.  
     if (HeightDiff(now) == 2)
147.  
     {
148.  
     if (HeightDiff(tr[now].left) >= 0) now = LL(now);
149.  
     else now = LR(now);
150.  
     }
151.  
     UpdateHeight(now);
152.  
     }
153.  
     }
154.  
     // 处理树平衡
155.  
     if (HeightDiff(now) == 2)
156.  
     {
157.  
     if (HeightDiff(tr[now].left) >= 0) now = LL(now);
158.  
     else now = LR(now);
159.  
     }
160.  
     else if (HeightDiff(now) == -2)
161.  
     {
162.  
     if (HeightDiff(tr[now].right) <= 0) now = RR(now);
163.  
     else now = RL(now);
164.  
     }
165.  
     UpdateHeight(now);
166.  
     }
167.  
      
168.  
     void InorderTraversal(int now, vector<int>& res)
169.  
     {
170.  
     if (now == -1) return;
171.  
     InorderTraversal(tr[now].left, res);
172.  
     res.push_back(tr[now].key);
173.  
     InorderTraversal(tr[now].right, res);
174.  
     }
175.  
      
176.  
      
177.  
     int main()
178.  
     {
179.  
     int n, op, key, data;
180.  
     while (scanf("%d", &n) != EOF)
181.  
     {
182.  
     for (root = tp = -1; n--; ) // 初始化根结点和“内存指针”
183.  
     {
184.  
     scanf("%d", &op);
185.  
     if (op == 1)
186.  
     {
187.  
     scanf("%d%d", &data, &key);
188.  
     Insert(root, key, data);
189.  
      
190.  
     }
191.  
     else if (op == 2)
192.  
     {
193.  
     int maxNodeIndex = FindMax(root);
194.  
     if (maxNodeIndex == -1 || tr[maxNodeIndex].data < 0)
195.  
     {
196.  
     printf("0\n");
197.  
     }
198.  
     else
199.  
     {
200.  
     printf("%d\n", tr[maxNodeIndex].data);
201.  
     Delete(root, tr[maxNodeIndex].key);
202.  
     }
203.  
     }
204.  
     else if (op == 3)
205.  
     {
206.  
     int minNodeIndex = FindMin(root);
207.  
     if (minNodeIndex == -1 || tr[minNodeIndex].data < 0)
208.  
     {
209.  
     printf("0\n");
210.  
     }
211.  
     else
212.  
     {
213.  
     printf("%d\n", tr[minNodeIndex].data);
214.  
     Delete(root, tr[minNodeIndex].key);
215.  
     }
216.  
     }
217.  
     else
218.  
     {
219.  
     scanf("%d", &key);
220.  
     int nodeIndex = root;
221.  
     while (nodeIndex != -1 && tr[nodeIndex].key != key)
222.  
     {
223.  
     if (tr[nodeIndex].key < key)
224.  
     {
225.  
     nodeIndex = tr[nodeIndex].right;
226.  
     }
227.  
     else
228.  
     {
229.  
     nodeIndex = tr[nodeIndex].left;
230.  
     }
231.  
     }
232.  
     if (nodeIndex == -1 || tr[nodeIndex].data < 0)
233.  
     {
234.  
     printf("0\n");
235.  
     }
236.  
     else
237.  
     {
238.  
     printf("%d\n", tr[nodeIndex].data);
239.  
     Delete(root, key);
240.  
     }
241.  
     }
242.  
     }
243.  
     }
244.  
     return 0;
245.  
     }

D. 平衡树上的第k小

题目描述

二种操作：

1. 1 Key 表示插入一个新数据Key；
2. 2 K 输出当前数据从小到大排列的第 K个数，并删除这个数，不存在则输出-1。

要求使用平衡树实现

输入

每组数据第一行n表示有n个操作

接下来n行操作内容

1 <= n <= 10^5

8
1 1
1 2
1 3
1 4
1 5
2 2
2 2
2 6        

输出

按操作规则输出对应内容

2
3
-1

1.  
   #include <iostream>
2.  
   using namespace std;
3.  
    
4.  
   struct TreeNode {
5.  
   int key, height, size;
6.  
   TreeNode *left, *right;
7.  
   TreeNode(int k) : key(k), height(1), size(1), left(nullptr), right(nullptr) {}
8.  
   };
9.  
    
10.  
    int height(TreeNode *node) {
11.  
    return node ? node->height : 0;
12.  
    }
13.  
     
14.  
    int balanceFactor(TreeNode *node) {
15.  
    return height(node->right) - height(node->left);
16.  
    }
17.  
     
18.  
    void updateHeightAndSize(TreeNode *node) {
19.  
    node->height = max(height(node->left), height(node->right)) 1;
20.  
    node->size = (node->left ? node->left->size : 0) (node->right ? node->right->size : 0) 1;
21.  
    }
22.  
     
23.  
    void rotateRight(TreeNode *&node) {
24.  
    TreeNode *left = node->left;
25.  
    node->left = left->right;
26.  
    left->right = node;
27.  
    updateHeightAndSize(node);
28.  
    updateHeightAndSize(left);
29.  
    node = left;
30.  
    }
31.  
     
32.  
    void rotateLeft(TreeNode *&node) {
33.  
    TreeNode *right = node->right;
34.  
    node->right = right->left;
35.  
    right->left = node;
36.  
    updateHeightAndSize(node);
37.  
    updateHeightAndSize(right);
38.  
    node = right;
39.  
    }
40.  
     
41.  
    void balance(TreeNode *&node) {
42.  
    if (balanceFactor(node) == 2) {
43.  
    if (balanceFactor(node->right) < 0) {
44.  
    rotateRight(node->right);
45.  
    }
46.  
    rotateLeft(node);
47.  
    } else if (balanceFactor(node) == -2) {
48.  
    if (balanceFactor(node->left) > 0) {
49.  
    rotateLeft(node->left);
50.  
    }
51.  
    rotateRight(node);
52.  
    }
53.  
    updateHeightAndSize(node);
54.  
    }
55.  
     
56.  
    void insert(TreeNode *&node, int key) {
57.  
    if (!node) {
58.  
    node = new TreeNode(key);
59.  
    } else if (key < node->key) {
60.  
    insert(node->left, key);
61.  
    } else if (key > node->key) {
62.  
    insert(node->right, key);
63.  
    }
64.  
    balance(node);
65.  
    }
66.  
     
67.  
    int getKth(TreeNode *&node, int k) {
68.  
    int r = (node->left ? node->left->size : 0) 1;
69.  
    if (k == r) {
70.  
    int res = node->key;
71.  
    if (!node->left && !node->right) {
72.  
    delete node;
73.  
    node = nullptr;
74.  
    } else if (node->left && !node->right) {
75.  
    TreeNode *tmp = node;
76.  
    node = node->left;
77.  
    delete tmp;
78.  
    } else if (!node->left && node->right) {
79.  
    TreeNode *tmp = node;
80.  
    node = node->right;
81.  
    delete tmp;
82.  
    } else {
83.  
    TreeNode *p = node->right;
84.  
    while (p->left) {
85.  
    p = p->left;
86.  
    }
87.  
    node->key = p->key;
88.  
    getKth(node->right, 1);
89.  
    }
90.  
    return res;
91.  
    } else if (k < r) {
92.  
    return getKth(node->left, k);
93.  
    } else {
94.  
    return getKth(node->right, k - r);
95.  
    }
96.  
    }
97.  
     
98.  
    int main() {
99.  
    int n;
100.  
     cin >> n;
101.  
      
102.  
     TreeNode *root = nullptr;
103.  
     for (int i = 0; i < n; i ) {
104.  
     int op, k;
105.  
     cin >> op >> k;
106.  
      
107.  
     if (op == 1) { // 插入操作
108.  
     insert(root, k);
109.  
     } else if (op == 2) { // 查找并删除第 k 小的元素
110.  
     if (root && root->size >= k) {
111.  
     cout << getKth(root, k) << endl;
112.  
     } else {
113.  
     cout << -1 << endl;
114.  
     }
115.  
     }
116.  
     }
117.  
      
118.  
     return 0;
119.  
     }

这篇好文章是转载于：学新通技术网