devbox
爱喝兽奶帝天荒
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构实验14-二叉平衡树&B-树_在初始为空的平衡二叉树中依次插入n个结点,请输出最终的平衡二叉树。 要求实现平

作者：爱喝兽奶帝天荒 | 2024-06-28 14:37:59

赞

踩

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

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. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/爱喝兽奶帝天荒/article/detail/766294
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号