# hashtest_avltree.zip

• 团团圆圆
了解作者
• C/C++
开发工具
• 7KB
文件大小
• zip
文件格式
• 0
收藏次数
• 1 积分
下载积分
• 2
下载次数
• 2018-12-29 15:29
上传日期

hashtest_avltree.zip
• hashtest_avltree
• DSLibrary
• Hash
• Hash.h
548B
• Hash.c
2KB
• AvlTree
• AvlTree.c
13.9KB
• AvlTree.h
913B
• main.c
7.7KB
• Makefile
584B

#include <stdio.h> #include <malloc.h> #include "AvlTree.h" #define Max(a,b) (((a) > (b)) ? (a) : (b)) #define Min(a,b) (((a) < (b)) ? (a) : (b)) typedef struct _tag_AvlTree TAvlTree; struct _tag_AvlTree { int count; AvlTreeNode *root; }; /* static int Max(int Lhs,int Rhs) { return Lhs > Rhs ? Lhs : Rhs; } */ static int Height(AvlTreeNode *P) { if(NULL == P) return -1; else return (P->height); } //RR旋转 static AvlTreeNode *SingleRotateWithLeft(AvlTreeNode *K2) { AvlTreeNode *K1 = NULL; K1 = K2->left; K2->left = K1->right; K1->right = K2; K2->height = Max(Height(K2->left), Height(K2->right)) + 1; K1->height = Max(Height(K1->left), K2->height) + 1; return K1; } //LL旋转 static AvlTreeNode *SingleRotateWithRight(AvlTreeNode *K1) { AvlTreeNode *K2 = NULL; K2 = K1->right; K1->right = K2->left; K2->left = K1; K1->height = Max(Height(K1->left), Height(K1->right)) + 1; K2->height = Max(Height(K2->right), K1->height) + 1; return K2; } //LR旋转 static AvlTreeNode *DoubleRotateWithLeft(AvlTreeNode *K3) { K3->left = SingleRotateWithRight(K3->left); return SingleRotateWithLeft(K3); } //RL旋转 static AvlTreeNode *DoubleRotateWithRight(AvlTreeNode *K3) { K3->right = SingleRotateWithLeft(K3->right); return SingleRotateWithRight(K3); } static int RecursiveInsert(AvlTreeNode **pRoot, AvlTreeNode* node, AvlTree_Compare* compare) { int s32Ret = -1; s32Ret = compare(node->key, (*pRoot)->key); if(s32Ret < 0) { if(NULL != (*pRoot)->left) { s32Ret = RecursiveInsert(&((*pRoot)->left), node, compare); if(s32Ret < 0) { s32Ret = -1; printf("[MSG::%s::%d]: RecursiveInsert error.\n", __func__, __LINE__); goto exit; } } else { (*pRoot)->left = node; (*pRoot)->left->height++; } if(2 == (Height((*pRoot)->left) - Height((*pRoot)->right))) { s32Ret = compare(node->key, (*pRoot)->left->key); if(s32Ret < 0) { (*pRoot) = SingleRotateWithLeft((*pRoot)); } else if(s32Ret > 0) { (*pRoot) = DoubleRotateWithLeft((*pRoot)); } } } else if(s32Ret > 0) { if(NULL != (*pRoot)->right) { s32Ret = RecursiveInsert(&((*pRoot)->right), node, compare); if(s32Ret < 0) { s32Ret = -1; printf("[MSG::%s::%d]: RecursiveInsert error.\n", __func__, __LINE__); goto exit; } } else { (*pRoot)->right = node; (*pRoot)->right->height++; } if(2 == (Height((*pRoot)->right) - Height((*pRoot)->left))) { s32Ret = compare(node->key, (*pRoot)->right->key); if(s32Ret > 0) { (*pRoot) = SingleRotateWithRight((*pRoot)); } else if(s32Ret < 0) { (*pRoot) = DoubleRotateWithRight((*pRoot)); } } } else if(0 == s32Ret) { //key in the tree already, do nothing. s32Ret= -1; goto exit; } (*pRoot)->height = Max(Height((*pRoot)->left), Height((*pRoot)->right)) + 1; s32Ret = 0; exit: return s32Ret; } static AvlTreeNode* RecursiveGet(AvlTreeNode* root, AvlKey* key, AvlTree_Compare* compare) { if(NULL == root) { printf("[MSG::%s::%d]: This Avl tree does not have the key.\n", __func__, __LINE__); return NULL; } AvlTreeNode* pAvlTreeNode = NULL; int s32Compare = compare(key, root->key); if(0 == s32Compare) { pAvlTreeNode = root; } else if(s32Compare == -1) { pAvlTreeNode = RecursiveGet(root->left, key, compare); } else if(s32Compare > 0) { pAvlTreeNode = RecursiveGet(root->right, key, compare); } return pAvlTreeNode; } static AvlTreeNode *RecursiveDelete(AvlTreeNode **pRoot, AvlKey *key, AvlTree_Compare *compare) { //printf("[MSG::%s::%d]: RecursiveDelete.\n", __func__, __LINE__); if(NULL == *pRoot) { printf("[MSG::%s::%d]: This Avl tree does not have the key.\n", __func__, __LINE__); return NULL; } AvlTreeNode *deleteNode = NULL; int s32Compare = compare(key, (*pRoot)->key); if(0 == s32Compare) { //printf("[MSG::%s::%d]: ==0.\n", __func__, __LINE__); deleteNode = (*pRoot); //printf("[MSG::%s::%d]: &deleteNode = 0x%x.\n", __func__, __LINE__, deleteNode); //printf("[MSG::%s::%d]: deleteNode->key = %d.\n", __func__, __LINE__, *((short *)(deleteNode->key))); if((NULL != (*pRoot)->left) && (NULL != (*pRoot)->right)) { //printf("[MSG::%s::%d]: debug_0001.\n", __func__, __LINE__); if(Height((*pRoot)->left) > Height((*pRoot)->right)) { //printf("[MSG::%s::%d]: debug_0002.\n", __func__, __LINE__); AvlTreeNode *tmpNode = (*pRoot); AvlTreeNode *maxNode = AvlTree_FindMax((*pRoot)->left); if(NULL != maxNode) { deleteNode = RecursiveDelete(&(tmpNode->left), maxNode->key, compare); maxNode->left = tmpNode->left; maxNode->right = (*pRoot)->right; maxNode->height = (*pRoot)->height; tmpNode = (*pRoot); (*pRoot) = maxNode; deleteNode = tmpNode; } } else { //printf("[MSG::%s::%d]: debug_0003.\n", __func__, __LINE__); AvlTreeNode *tmpNode = (*pRoot); AvlTreeNode *minNode = AvlTree_FindMin((*pRoot)->right); if(NULL != minNode) { deleteNode = RecursiveDelete(&(tmpNode->right), minNode->key, compare); minNode->right = tmpNode->right; minNode->left = (*pRoot)->left; minNode->height = (*pRoot)->height; tmpNode = (*pRoot); (*pRoot) = minNode; deleteNode = tmpNode; } } } else { (*pRoot) = ((*pRoot)->left) ? ((*pRoot)->left) : ((*pRoot)->right); } } else if(s32Compare == -1) { //printf("[MSG::%s::%d]: <0.\n", __func__, __LINE__); deleteNode = RecursiveDelete(&((*pRoot)->left), key, compare); if(Height((*pRoot)->right) - Height((*pRoot)->left) == 2) { if(Height((*pRoot)->right->left) > Height((*pRoot)->right->right)) { (*pRoot) = DoubleRotateWithRight((*pRoot)); } else { (*pRoot) = SingleRotateWithRight((*pRoot)); } } } else if(s32Compare > 0) { //printf("[MSG::%s::%d]: >0.\n", __func__, __LINE__); deleteNode = RecursiveDelete(&((*pRoot)->right), key, compare); if(Height((*pRoot)->left) - Height((*pRoot)->right) == 2) { if(Height((*pRoot)->left->right) > Height((*pRoot)->left->left)) { (*pRoot

相关推荐
• hash.zip
创建一个AVL树算法，并在此基础上完成部分功能
• 左程云leetcode-algorithm-and-data-structure:算法+数据结构=程序
左程云leetcode 数据结构和算法学习笔记 一、简介 1. 2. 3. 4. 5. 6. 二、数据结构 ...二维数组（Array2D） ...哈希Hash Table） 哈希函数（Hash Functions） 6. 优先队列（Priority Queue） 堆
• 数据结构名校课件压缩文件
高校数据结构的课件。比较概括的叙述了有关链表，，堆栈的基本概念，对初学者很有帮助。