#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h> typedef struct AVLTree{ char name[31];
int nCount;
int nHeight; struct AVLTree* pLeft;
struct AVLTree* pRight; }AVLTree; int Max( int a, int b );
int Height( AVLTree* pNode );
AVLTree* Insert( char* s, AVLTree* pNode );
AVLTree* LLRotate( AVLTree* pNode );
AVLTree* RRRotate( AVLTree* pNode );
AVLTree* LRRotate( AVLTree* pNode );
AVLTree* RLRotate( AVLTree* pNode );
void PrintTree( AVLTree* pNode ); int n = 0; int main(){ char s[31];
AVLTree* pRoot = NULL; while( gets( s ) != NULL ){ pRoot = Insert( s, pRoot );
n++; } PrintTree( pRoot ); return 0;
} int Max( int a, int b ){
return ( a > b ) ? a : b;
} int Height( AVLTree* pNode ){ if( pNode == NULL )
return -1; return pNode->nHeight;
} AVLTree* Insert( char* s, AVLTree* pNode ){ if( pNode == NULL ){
pNode = ( AVLTree* ) malloc( sizeof( AVLTree ) );
strcpy( pNode->name, s );
pNode->nCount = 1;
pNode->nHeight = 0;
pNode->pLeft = NULL;
pNode->pRight = NULL;
}
else if( strcmp( s, pNode->name ) == 0 ){
pNode->nCount++;
}
else if( strcmp( s, pNode->name ) < 0 ){ pNode->pLeft = Insert( s, pNode->pLeft ); if( Height( pNode->pLeft ) - Height( pNode->pRight ) == 2 ){
if( strcmp( s, pNode->pLeft->name ) < 0 ){
pNode = LLRotate( pNode );
}
else{
pNode = LRRotate( pNode );
}
}
}
else if( strcmp( s, pNode->name ) > 0 ){ pNode->pRight = Insert( s, pNode->pRight ); if( Height( pNode->pRight ) - Height( pNode->pLeft ) == 2 ){
if( strcmp( s, pNode->pRight->name ) > 0 ){
pNode = RRRotate( pNode );
}
else{
pNode = RLRotate( pNode );
}
} } pNode->nHeight = Max( Height( pNode->pLeft ), Height( pNode->pRight ) ) + 1; return pNode;
} AVLTree* LLRotate( AVLTree* pNode ){ AVLTree* pNodeLeft = pNode->pLeft;
pNode->pLeft = pNodeLeft->pRight;
pNodeLeft->pRight = pNode;
pNode->nHeight = Max( Height( pNode->pLeft ), Height( pNode->pRight ) ) + 1;
pNodeLeft->nHeight = Max( Height( pNodeLeft->pLeft ), pNode->nHeight ) + 1; return pNodeLeft; } AVLTree* RRRotate( AVLTree* pNode ){ AVLTree* pNodeRight = pNode->pRight;
pNode->pRight = pNodeRight->pLeft;
pNodeRight->pLeft = pNode;
pNode->nHeight = Max( Height( pNode->pLeft ), Height( pNode->pRight ) ) + 1;
pNodeRight->nHeight = Max( Height( pNodeRight->pRight ), pNode->nHeight ) + 1; return pNodeRight; } AVLTree* LRRotate( AVLTree* pNode ){ pNode->pLeft = RRRotate( pNode->pLeft ); return LLRotate( pNode );
} AVLTree* RLRotate( AVLTree* pNode ){ pNode->pRight = LLRotate( pNode->pRight ); return RRRotate( pNode );
} void PrintTree( AVLTree* pRoot ){ if( pRoot == NULL )
return; PrintTree( pRoot->pLeft );
printf( "%s %.4f\n", pRoot->name, ( ( double )( pRoot->nCount ) / ( double )n ) * 100 );
PrintTree( pRoot->pRight ); }

POJ 2418 Hardwood Species( AVL-Tree ) More articles about

  1. [ Dictionary tree ] poj 2418 Hardwood Species

    Topic link : id=2418">http://poj.org/problem?id=2418 Hardwood Species Time Limit: 10000MS   Memory ...

  2. POJ 2418 Hardwood Species

                                                     Hardwood Species Time Limit: 10000MS   Memory Limit ...

  3. [ACM] POJ 2418 Hardwood Species (Trie Tree or map)

    Hardwood Species Time Limit: 10000MS   Memory Limit: 65536K Total Submissions: 17986   Accepted: 713 ...

  4. POJ 2418 Hardwood Species(STL stay map application )

    Position address :id=2418">POJ 2418 Through this question, I checked a lot of information .. I know a lot of things I didn't know before . . .. Look at the instructions in the code . The code is as follows : #include <ios ...

  5. POJ - 2418 Hardwood Species(map,trie,BST)

    1. Enter several row tree names , After input , Output the tree name and its percentage in dictionary order . 2. many-ways :map,trie,BST 3. map: #include<iostream> #include<st ...

  6. poj 2418 Hardwood Species (map)

    subject :http://poj.org/problem?id=2418 stay poj There are always all kinds of mistakes in turn in questions , Once again, all compilers . c++ AC Code ,G++ Timeout , Code up : #include<cstdio ...

  7. POJ 2418 Hardwood Species ( Hash ,%f and %lf)

    My fault : Originally, it was %f Output , I used it %lf, As a result, the compiler decides that it is an error ( Some compilers think that lf There's nothing wrong with it ). I thought it was hash Something went wrong .. There's more than one way : Method Time    Space Hash 891ms 5 ...

  8. Binary search tree POJ 2418 Hardwood Species

    Subject portal The question : Enter a bunch of strings , Ask the dictionary order to output the percentage of each string analysis : Binary search tree insertion , Then the middle order traversal is the dictionary order , here root By new When you come out, point to NULL,RE Several times . The violence sort It's also possible to live ...

  9. POJ 2418 Hardwood Species 【Trie Trees 】

    < Topic link > The main idea of the topic : Here's a bunch of strings , Let you output their frequency in dictionary order . Problem solving analysis : First , This is a Trie The topic of statistics of number word frequency , With Trie The edge of the tree stores letters , Node stores the string represented by the chain ending with the node ...

Random recommendation

  1. C#: Judge whether the environment in which the software runs is Pad(PC)

    One . demand :Pad A function block is displayed on the screen ,PC Hidden on board . Two . Method : Get the value from the peripheral device to judge whether it is Pad. 3、 ... and . The specific reference code is as follows : 1. The peripheral value types are as follows : public enum ChassisTypes { O ...

  2. linux Driving development HelloWorld

    Recent internship , The company's project is flat development , And my assignment is to load the driver into the kernel . preparation , Necessary knowledge to understand : There are two ways to load , One is dynamic loading and unloading, that is, module loading , The other is to compile directly into the kernel :Linux The kernel divides drivers into ...

  3. High imitation and fine imitation of wechat application ios Source download

    WeChat , exceed 3 Billion people use , Can send voice to friends through mobile network . Text message . expression . Pictures and videos , You can also share photos with your friends . By shaking . Check out the people around , You can make new friends . Use a sweep , You can scan the QR code . bar code . Books and streetscape . ...

  4. JavaMail Learning notes ( 7、 ... and )、 Account activation and password forgetting example (zhuan)

    One . Account activation   In many cases , After registering a user on some sites , The website will give this user to fill in when registering email Address to send an account activation email , The content of this email is a link to activate the account and a short text description , If the user doesn't go to the mailbox, it will ...

  5. C Language to C++(1) - Basic changes

    Speaking of C++ and C The difference of language , Most people think of object-oriented and process oriented . However, this statement is not accurate . Object oriented and process oriented are two different programming ideas , and C++ And C It's two programming languages , Don't C++ Can't it be used for process oriented problem solving ...

  6. Zabbix actual combat - API Tutorial -- Alarm shielding (Maintenances)

    Zabbix Maintenance One .Zabbix Maintenance(zabbix Alarm shielding ) A lot of times , We need to update and maintain the online environment at some time , At this point, you know the trigger will trigger an alarm , So at this point you can say ...

  7. Open source agreement bullshit , What is? MIT agreement ?[ turn ]

    picture source :http://ruby-china.org/topics/15979

  8. Redis Master slave synchronization needs deep understanding ? One article is enough !

    Preface : I want to share with you today about Redis Master slave synchronization ( Also known as 「 Copy 」) The content of . We know , When there are more than one Redis Server time , There must be one master server and several slave servers . Generally speaking , The master server writes , Read from the server ...

  9. java Design patterns -----20、 Template method pattern

    Concept : Template Method Patterns are also called template method patterns , It's one of the patterns of behavior , It delegates some of the necessary processing in algorithms with specific steps to abstract methods , Through subclass inheritance, different implementations of abstract methods can change the behavior of the whole algorithm . The template method pattern should ...

  10. React note - Event distribution

    Event distribution I talked about how events are bound to document On , How to distribute specific events to specific listeners when they are triggered ? Let's take a look at the last registered event agent . When I click update counter Button , Trigger registered click things ...