首页 > 代码库 > hdu-1255-覆盖的面积-线段树
hdu-1255-覆盖的面积-线段树
Splay树的插入操作,只需要处理好插入节点的孩子节点就可以了,最重要的是不要破坏了BST的基本规则。
因为高度并不是Splay树的首要因素,所以插入的时候也是使用splay操作,然后在根节点插入。
参考:http://www.geeksforgeeks.org/splay-tree-set-2-insert-delete/
对比一下使用插入创建的树和手工创建数的区别,先序遍历的结果:
#pragma once #include<stdio.h> #include <stdlib.h> class SplayTree_Insertion { struct Node { int key; Node *left, *right; Node(int k) : key(k), left(NULL), right(NULL) {} ~Node() { if (left) delete left, left = NULL; if (right) delete right, right = NULL; } }; Node *rightRotate(Node *x) { Node *y = x->left; x->left = y->right; y->right = x; return y; } Node *leftRotate(Node *x) { Node *y = x->right; x->right = y->left; y->left = x; return y; } Node *splay(Node *root, const int key) { if (!root || key == root->key) return root; if (key < root->key) { if (!root->left) return root; if (key < root->left->key) { root->left->left = splay(root->left->left, key); root = rightRotate(root);//不应root->left } else if (root->left->key < key) { root->left->right = splay(root->left->right, key); if (root->left->right) root->left = leftRotate(root->left); } return root->left? rightRotate(root) : root; } if (!root->right) return root; if (root->right->key < key) { root->right->right = splay(root->right->right, key); root = leftRotate(root); } else if (key < root->right->key) { root->right->left = splay(root->right->left, key); if (root->right->left) root->right = rightRotate(root->right); } return root->right? leftRotate(root) : root; } Node *insert(Node *root, int k) { if (!root) return new Node(k); root = splay(root, k); if (root->key == k) return root; Node *newNode = new Node(k); //learn how to handle the insertion is the best way. if (k < root->key) { newNode->right = root; newNode->left = root->left; root->left = NULL; } else { newNode->left = root; newNode->right = root->right; root->right = NULL; } return newNode; } void preOrder(Node *root) { if (root != NULL) { printf("%d ", root->key); preOrder(root->left); preOrder(root->right); } } public: SplayTree_Insertion() { Node *root = new Node(100); root->left = new Node(50); root->right = new Node(200); root->left->left = new Node(40); root->left->left->left = new Node(30); root->left->left->left->left = new Node(20); root = insert(root, 25); printf("Preorder traversal of the modified Splay tree is \n"); preOrder(root); putchar('\n'); delete root; runInsert(); } void runInsert() { Node *root = NULL; int keys[] = {100, 50, 200, 40, 30, 20, 25}; int n = sizeof(keys) / sizeof(keys[0]); for (int i = 0; i < n; i++) { root = insert(root, keys[i]); } printf("Inser create Preorder traversal Splay tree is \n"); preOrder(root); putchar('\n'); delete root; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。