u012637838的专栏

OneKdTree.h

#include <algorithm>#include <set>#include <iostream>using namespace std;class AvlTree;class AvlNode{friend class AvlTree;int data;int height;AvlNode *left;AvlNode *right;AvlNode(int _data) :data(_data), height(0), left(NULL), right(NULL){}};class AvlTree{AvlNode *root;public:AvlTree() :root(NULL){}int Height(AvlNode *node){ return node == NULL ? -1 : node->height; }void Insert(int _data){ _insert(root, _data); }void Delete(int _data){ _delete(root, _data); }bool Find(int _data);void print(){ travel(root); cout << endl; }void OneDRangeQuery(int low, int high);private:AvlTree(const AvlTree &);AvlTree& operator=(const AvlTree&);void LL(AvlNode* &node);void RR(AvlNode* &node);void RL(AvlNode* &node);void LR(AvlNode* &node);void _insert(AvlNode* &node,int _data);void _delete(AvlNode* &node, int _data);void travel(AvlNode *node);AvlNode *FindMin(AvlNode *node);AvlNode *FindParent(AvlNode *node, int _data);void ParentRotate(AvlNode* &node, AvlNode* &parent);void LeftHigherhanRight(AvlNode* &node);void RightHigherhanLeft(AvlNode* &node);AvlNode* FindSplitNode(int low, int high);};void AvlTree::OneDRangeQuery(int low, int high){AvlNode *node = FindSplitNode(low, high);if (node == NULL)return;if (node->left == NULL&&node->right == NULL){if (node->data >= low && node->data <= high)cout << node->data << " ";}else {AvlNode *temp = node->left;while (temp&&(temp->left != NULL || temp->right != NULL)){if (temp->data >= low){travel(temp->right);temp = temp->left;}else {temp = temp->right;}}if (temp&&temp->data >= low&&temp->data <= high)cout << temp->data << " ";temp = node->right;while (temp&&(temp->left != NULL || temp->right != NULL)){if (temp->data <= high){travel(temp->left);temp = temp->right;}else {temp = temp->left;}}if (temp&&temp->data >= low&&temp->data <= high)cout << temp->data << " ";}cout << endl;}AvlNode* AvlTree::FindSplitNode(int low, int high){if (low > high)return NULL;AvlNode *node = root;if (node == NULL)return NULL;while ((node->right != NULL || node->left != NULL) && (node->data >= high || node->data < low)){if (node->data >= high)node = node->left;elsenode = node->right;}return node;}void AvlTree::LeftHigherhanRight(AvlNode* &node){if (Height(node->left) – Height(node->right) == 2){if (node->left){if (Height(node->left->right) > Height(node->left->left))LR(node);elseLL(node);}}}void AvlTree::RightHigherhanLeft(AvlNode* &node){//调用次数多，封装成函数if (Height(node->right) – Height(node->left) == 2){if (node->right){if (Height(node->right->left)>Height(node->right->right))RL(node);elseRR(node);}}}void AvlTree::ParentRotate(AvlNode* &node, AvlNode* &parent){//旋转从node到parent路径上的每一个结点，使之平衡if (parent == NULL)return;if (node->data > parent->data){ParentRotate(node->left, parent);}else if (node->data<parent->data){ParentRotate(node->right, parent);}LeftHigherhanRight(node);RightHigherhanLeft(node);}AvlNode *AvlTree::FindParent(AvlNode *node, int _data){//找父亲结点if (node == NULL || node->data == _data)return NULL;if ((node->left && node->left->data == _data) || (node->right&&node->right->data == _data))return node;else if (node->data>_data)return FindParent(node->left, _data);else if (node->data<_data)return FindParent(node->right, _data);}AvlNode *AvlTree::FindMin(AvlNode *node){//找最小结点if (node){while (node->left)node = node->left;}return node;}void AvlTree::_delete(AvlNode* &node, int _data){if (node == NULL){//cout << "the element is not exit" << endl;return;}else {if (_data < node->data){_delete(node->left, _data);RightHigherhanLeft(node);//右子树高于左子树，，旋转}else if (_data > node->data){_delete(node->right, _data);LeftHigherhanRight(node);//左子树高于右子树，旋转}else {//定位到要删除的结点AvlNode *temp = FindMin(node->right);if (temp == NULL){//node没有右结点temp = node;node = node->left;delete temp;}else{if (temp == node->right){//node右结点没有左子树node->right = temp->right;node->data = temp->data;delete temp;LeftHigherhanRight(node);//删除后，可能左子树高于右子树}else{//node右结点有左子树AvlNode *parent = FindParent(node, temp->data);//寻找父节点node->data = temp->data;parent->left = temp->right;delete temp;//parent may not balenceParentRotate(node, parent);//使得node到parent路径上的每一个结点能够平衡}}}}if (node != NULL)node->height = std::max(Height(node->left), Height(node->right)) + 1;//更新高度}void AvlTree::_insert(AvlNode* &node, int _data){if (node == NULL){node = new AvlNode(_data);//找到插入点}else {if (_data <= node->data){_insert(node->left, _data);//插入到左子树后，判断其高度是否平衡if (Height(node->left) – Height(node->right) == 2){if (_data > node->left->data)LR(node);elseLL(node);}}else if (_data > node->data){//插入到右子树后，判断其高度是否平衡_insert(node->right, _data);if (Height(node->right) – Height(node->left) == 2){if (_data<node->right->data)RL(node);elseRR(node);}}}node->height = std::max(Height(node->left), Height(node->right)) + 1;//更新高度}void AvlTree::LL(AvlNode* &node){AvlNode *temp = node->left;node->left = temp->right;temp->right = node;node->height = std::max(Height(node->left), Height(node->right)) + 1;temp->height = std::max(Height(temp->left), Height(temp->right)) + 1;node = temp;}void AvlTree::RR(AvlNode* &node){AvlNode *temp = node->right;node->right = temp->left;temp->left = node;node->height = std::max(Height(node->left), Height(node->right)) + 1;temp->height = std::max(Height(temp->left), Height(temp->right)) + 1;node = temp;}void AvlTree::LR(AvlNode* &node){RR(node->left);LL(node);}void AvlTree::RL(AvlNode* &node){LL(node->right);RR(node);}void AvlTree::travel(AvlNode *node){if (node){if (node->right == NULL&&node->left == NULL){cout << node->data << " ";}else {travel(node->left);travel(node->right);}}}

test.cpp

如果爱，请深爱;如不爱，请离开。