平衡二叉树

/* avlNode.h */ #pragma once #include <string.h> #include <stdlib.h> #pragma pack(1) template<typename ValType> class AVL_NODE { private: static const int MAX_VALUE_SIZE = 1024; /* 值最大1024字节 */ public: AVL_NODE* left; AVL_NODE* right; unsigned int nodeHeight : 8; /* 最大树高255 */ unsigned int nodeCite : 24; /* 最大引用度2 ^ 24 - 1 */ ValType value; /* 一般情况 */ AVL_NODE(ValType _value) : left(NULL), right(NULL), nodeHeight(1), nodeCite(1), value(_value) {} /* 针对value长度不固定以及value无法直接赋值的情况 */ static AVL_NODE* newAvlNode(ValType* value, int valueSize) { if (!value || valueSize < 1 || valueSize > MAX_VALUE_SIZE) return NULL; AVL_NODE* newNode = (AVL_NODE*)malloc(sizeof(AVL_NODE) - sizeof(ValType) + valueSize); if (!newNode) return NULL; newNode->left = newNode->right = NULL; newNode->nodeCite = newNode->nodeHeight = 1; memcpy(&newNode->value, value, valueSize); return newNode; } }; #pragma pack() /* avlModel.h */ #pragma once #include "avlNode.h" template<typename ValType> class Avl { public: typedef AVL_NODE<ValType> AVL_NODE, * PAVL_NODE; Avl(); ~Avl(); PAVL_NODE insertValue(ValType* value, int valueSize); void deleteValue(ValType* value); unsigned int getTreeHeight(); unsigned int getNodeCount(); private: PAVL_NODE root; unsigned int nodeCount; unsigned int getNodeHeight(PAVL_NODE node); int cmpValue(ValType* thisValue, ValType* otherValue); int getBalanceFactor(PAVL_NODE node); void llRotate(PAVL_NODE& n); void rrRotate(PAVL_NODE& n); void lrRotate(PAVL_NODE& n); void rlRotate(PAVL_NODE& n); void adjustBalance(PAVL_NODE& root); void insertValue(PAVL_NODE& root, ValType* value, int valueSize, PAVL_NODE& newNode); void deleteValue(PAVL_NODE& root, ValType* value, bool isReal); void destroyTree(PAVL_NODE& root); }; template<typename ValType> inline Avl<ValType>::Avl() { root = NULL; nodeCount = 0; } template<typename ValType> inline Avl<ValType>::~Avl() { destroyTree(root); nodeCount = 0; } /* private: */ template<typename ValType> inline unsigned int Avl<ValType>::getNodeHeight(PAVL_NODE node) { if (!node) return 0; return node->nodeHeight; } /* value要实现减运算且返回int值，正数为大于，0为等于，负数为小于；解决复杂value直接比较大小时重复比较问题 */ template<typename ValType> inline int Avl<ValType>::cmpValue(ValType* thisValue, ValType* otherValue) { return *thisValue - *otherValue; } template<typename ValType> inline int Avl<ValType>::getBalanceFactor(PAVL_NODE node) { if (!node) return 0; return (int)getNodeHeight(node->left) - (int)getNodeHeight(node->right); } template<typename ValType> void Avl<ValType>::llRotate(PAVL_NODE& n) { PAVL_NODE x = n->left; n->left = x->right; x->right = n; x->nodeHeight = std::max(getNodeHeight(x->left), getNodeHeight(x->right)) + 1; n->nodeHeight = std::max(getNodeHeight(n->left), getNodeHeight(n->right)) + 1; n = x; } template<typename ValType> void Avl<ValType>::rrRotate(PAVL_NODE& n) { PAVL_NODE x = n->right; n->right = x->left; x->left = n; x->nodeHeight = std::max(getNodeHeight(x->left), getNodeHeight(x->right)) + 1; n->nodeHeight = std::max(getNodeHeight(n->left), getNodeHeight(n->right)) + 1; n = x; } template<typename ValType> inline void Avl<ValType>::lrRotate(PAVL_NODE& n) { rrRotate(n->left); llRotate(n); } template<typename ValType> inline void Avl<ValType>::rlRotate(PAVL_NODE& n) { llRotate(n->right); rrRotate(n); } template<typename ValType> void Avl<ValType>::adjustBalance(PAVL_NODE& root) { int balanceFactor = getBalanceFactor(root); if (balanceFactor < -1) { int rBalanceFactor = getBalanceFactor(root->right); if (rBalanceFactor <= 0) rrRotate(root); else rlRotate(root); } else if (balanceFactor > 1) { int lBalanceFactor = getBalanceFactor(root->left); if (lBalanceFactor >= 0) llRotate(root); else lrRotate(root); } root->nodeHeight = std::max(getNodeHeight(root->left), getNodeHeight(root->right)) + 1; } template<typename ValType> void Avl<ValType>::insertValue(PAVL_NODE& root, ValType* value, int valueSize, PAVL_NODE& newNode) { if (root == NULL) { root = AVL_NODE::newAvlNode(value, valueSize); newNode = root; if(newNode) nodeCount++; } else { int cmp = cmpValue(value, &root->value); if (cmp == 0) { root->nodeCite++; newNode = root; } else if (cmp > 0) { insertValue(root->right, value, valueSize, newNode); adjustBalance(root); } else { insertValue(root->left, value, valueSize, newNode); adjustBalance(root); } } } template<typename ValType> void Avl<ValType>::deleteValue(PAVL_NODE& root, ValType* value, bool isReal) { if (root == NULL) return; /* 待删除结点不存在 */ int cmp = cmpValue(value, &root->value); if (cmp < 0) deleteValue(root->left, value, isReal); else if (cmp > 0) deleteValue(root->right, value, isReal); /* 找到结点 */ else { /* 若isReal为false，不管引用数是多少一定要往下执行 */ if (isReal == true && root->nodeCite > 1) { root->nodeCite--; return; } if (!(root->left)) { PAVL_NODE temp = root; root = root->right; if (isReal) { free(temp); nodeCount--; } temp = NULL; } else if (!(root->right)) { PAVL_NODE temp = root; root = root->left; if (isReal) { free(temp); nodeCount--; } temp = NULL; } /* 对于待删除结点左右孩子都存在的情况，一般的操作时找到待删除结点的直接前驱或者直接 后继，然后使用直接前驱或者直接后继结点中的值代替待删除结点中的值，然后递归删除直接前 驱或者直接后继结点，此处针对到某些无法完成直接赋值的情况，采用指针替换操作，即：使指 向待删除结点的指针指向直接前驱或直接后继结点，然后直接删除待删除结点，递归删除这个直 接前驱或者直接后继结点时，是假删除，不释放其空间，只调整指向此结点的指针为NULL。 isReal参数代表了是否为假删除。 */ else { PAVL_NODE p = NULL; /* 左边高删左边 */ if (getNodeHeight(root->left) >= getNodeHeight(root->right)) { /* 找到直接前驱 */ p = root->left; while (p->right) p = p->right; /* 假删除p */ deleteValue(root->left, &p->value, false); } /* 右边高删右边 */ else { /* 找到直接后继 */ p = root->right; while (p->left) p = p->left; /* 假删除p */ deleteValue(root->right, &p->value, false); } /* 指针替换，高度不需更改，因为后续的平衡调整函数将会重置高度 */ p->left = root->left; p->right = root->right; free(root); root = p; nodeCount--; } } if (root) adjustBalance(root); } template<typename ValType> void Avl<ValType>::destroyTree(PAVL_NODE& root) { if (root) { destroyTree(root->left); destroyTree(root->right); free(root); root = NULL; } } /* public: */ template<typename ValType> typename Avl<ValType>::PAVL_NODE Avl<ValType>::insertValue(ValType* value, int valueSize) { PAVL_NODE newNode = NULL; insertValue(root, value, valueSize, newNode); return newNode; } template<typename ValType> void Avl<ValType>::deleteValue(ValType* value) { deleteValue(root, value, true); } template<typename ValType> unsigned int Avl<ValType>::getTreeHeight() { if (!root) return 0; return root->nodeHeight; } template<typename ValType> unsigned int Avl<ValType>::getNodeCount() { return nodeCount; }