Splay Tree的插入操作,搜索操作,和删除操作都实现了,那么就可以使用来解题了。
指针的删除操作的处理还是那么难的,很多坎需要避开.
同一个坎还是坑了我好多次,就是指针传递的问题,什么时候需要修改指针本身的值,就必须返回指针或者传递指针的指针,或者传递指针的的实参。
这里的删除操作就是需要改变传递到函数的指针本身的,所以我这里使用了返回指针操作。
还有删除树的问题,之前的代码没做删除操作,所以没问题,现在需要逐个节点删除,所以要小心不能把整个树都删除了。
至此, splay 树的功能差不多完善了。
代码中注释标明了几个坑都被我碰到了。
#pragma once #include <stdio.h> class SplayTreeComplete { struct Node { int key; Node *left, *right; explicit Node(int k):key(k),left(NULL),right(NULL){} /*~Node() {教训:这样的话整颗树都删除了,不能这么删除,要逐个节点删除 if (left) delete left, left = NULL; if (right) delete right, right = NULL; }*/ }; Node *leftRotate(Node *x) { Node *y = x->right; x->right = y->left; y->left = x; return y; } Node *rightRotate(Node *x) { Node *y = x->left; x->left = y->right; y->right = 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); } 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, const int key) { if (!root) return new Node((int)key);//别忘了创建新的节点 root = splay(root, key);//别忘了 root = if (key == root->key) return root; Node *newNode = new Node((int)key); if (key < 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; } Node *deleteNode(Node *root, const int key) { if (!root) return root; root = splay(root, key); if (key == root->key) { if (!root->left) { Node *x = root; root = root->right; delete x, x = NULL; } else { Node *x = root->right; Node *y = root->left; delete root; root = splay(y, key); root->right = x; } } return root; } void preOrder(Node *root) { if (root != NULL) { printf("%d ", root->key); preOrder(root->left); preOrder(root->right); } } bool search(Node *root, const int key) { root = splay(root, key); return root->key == key; } public: SplayTreeComplete() { 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("\nInser create Preorder traversal Splay tree is \n"); preOrder(root); putchar('\n'); root = splay(root, 50); bool found = root->key == 50; printf("\n50 is %s the tree\n", found? "in" : "not in"); root = deleteNode(root, 50);//root 发生改变了,所以必须返回新的指针值 root = splay(root, 50); found = root->key == 50; printf("\n50 is %s the tree\n", found? "in" : "not in"); printf("\nInser create Preorder traversal Splay tree is \n"); preOrder(root); putchar('\n'); deleteTree(root); } void deleteTree(Node *root) { if (root) { deleteTree(root->left); deleteTree(root->right); delete root, root = NULL; } } };
Splay Tree的删除操作,布布扣,bubuko.com
原文:http://blog.csdn.net/kenden23/article/details/27810357