Skip to content

Instantly share code, notes, and snippets.

@weskerhluffy

weskerhluffy/.cproject

Forked from tonious/avl.c
Last active April 22, 2017 15:05
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save weskerhluffy/4dfa8f9956db2d977c6b to your computer and use it in GitHub Desktop.
Save weskerhluffy/4dfa8f9956db2d977c6b to your computer and use it in GitHub Desktop.
Download ZIP
A quick AVL tree implementation in c.
Raw
.cproject
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<?fileVersion 4.0.0?><cproject storage_type_id="org.eclipse.cdt.core.XmlProjectDescriptionStorage">
<storageModule moduleId="org.eclipse.cdt.core.settings">
<cconfiguration id="cdt.managedbuild.config.gnu.macosx.exe.debug.731461427">
<storageModule buildSystemId="org.eclipse.cdt.managedbuilder.core.configurationDataProvider" id="cdt.managedbuild.config.gnu.macosx.exe.debug.731461427" moduleId="org.eclipse.cdt.core.settings" name="Debug">
<externalSettings/>
<extensions>
<extension id="org.eclipse.cdt.core.GmakeErrorParser" point="org.eclipse.cdt.core.ErrorParser"/>
<extension id="org.eclipse.cdt.core.CWDLocator" point="org.eclipse.cdt.core.ErrorParser"/>
<extension id="org.eclipse.cdt.core.GCCErrorParser" point="org.eclipse.cdt.core.ErrorParser"/>
<extension id="org.eclipse.cdt.core.GASErrorParser" point="org.eclipse.cdt.core.ErrorParser"/>
<extension id="org.eclipse.cdt.core.GLDErrorParser" point="org.eclipse.cdt.core.ErrorParser"/>
<extension id="org.eclipse.cdt.core.MachO64" point="org.eclipse.cdt.core.BinaryParser"/>
</extensions>
</storageModule>
<storageModule moduleId="cdtBuildSystem" version="4.0.0">
<configuration artifactName="${ProjName}" buildArtefactType="org.eclipse.cdt.build.core.buildArtefactType.exe" buildProperties="org.eclipse.cdt.build.core.buildType=org.eclipse.cdt.build.core.buildType.debug,org.eclipse.cdt.build.core.buildArtefactType=org.eclipse.cdt.build.core.buildArtefactType.exe" cleanCommand="rm -rf" description="" id="cdt.managedbuild.config.gnu.macosx.exe.debug.731461427" name="Debug" parent="cdt.managedbuild.config.gnu.macosx.exe.debug">
<folderInfo id="cdt.managedbuild.config.gnu.macosx.exe.debug.731461427." name="/" resourcePath="">
<toolChain id="cdt.managedbuild.toolchain.gnu.macosx.exe.debug.120980287" name="MacOSX GCC" superClass="cdt.managedbuild.toolchain.gnu.macosx.exe.debug">
<targetPlatform id="cdt.managedbuild.target.gnu.platform.macosx.exe.debug.901683888" name="Debug Platform" superClass="cdt.managedbuild.target.gnu.platform.macosx.exe.debug"/>
<builder buildPath="${workspace_loc:/avl_apuntadores}/Debug" id="cdt.managedbuild.target.gnu.builder.macosx.exe.debug.499127438" keepEnvironmentInBuildfile="false" managedBuildOn="true" name="Gnu Make Builder" superClass="cdt.managedbuild.target.gnu.builder.macosx.exe.debug">
<outputEntries>
<entry flags="VALUE_WORKSPACE_PATH|RESOLVED" kind="outputPath" name="Debug"/>
<entry flags="VALUE_WORKSPACE_PATH|RESOLVED" kind="outputPath" name="Release"/>
</outputEntries>
</builder>
<tool id="cdt.managedbuild.tool.macosx.c.linker.macosx.exe.debug.2130271181" name="MacOS X C Linker" superClass="cdt.managedbuild.tool.macosx.c.linker.macosx.exe.debug">
<option id="macosx.c.link.option.paths.385747633" superClass="macosx.c.link.option.paths" valueType="libPaths">
<listOptionValue builtIn="false" value="/Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.7.sdk/usr/lib"/>
</option>
<inputType id="cdt.managedbuild.tool.macosx.c.linker.input.2123302936" superClass="cdt.managedbuild.tool.macosx.c.linker.input">
<additionalInput kind="additionalinputdependency" paths="$(USER_OBJS)"/>
<additionalInput kind="additionalinput" paths="$(LIBS)"/>
</inputType>
</tool>
<tool id="cdt.managedbuild.tool.macosx.cpp.linker.macosx.exe.debug.155605699" name="MacOS X C++ Linker" superClass="cdt.managedbuild.tool.macosx.cpp.linker.macosx.exe.debug"/>
<tool id="cdt.managedbuild.tool.gnu.assembler.macosx.exe.debug.1039458498" name="GCC Assembler" superClass="cdt.managedbuild.tool.gnu.assembler.macosx.exe.debug">
<option id="gnu.both.asm.option.include.paths.265618426" superClass="gnu.both.asm.option.include.paths" valueType="includePath">
<listOptionValue builtIn="false" value="/Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.7.sdk/usr/include"/>
</option>
<inputType id="cdt.managedbuild.tool.gnu.assembler.input.1524473748" superClass="cdt.managedbuild.tool.gnu.assembler.input"/>
</tool>
<tool id="cdt.managedbuild.tool.gnu.archiver.macosx.base.810033194" name="GCC Archiver" superClass="cdt.managedbuild.tool.gnu.archiver.macosx.base"/>
<tool id="cdt.managedbuild.tool.gnu.cpp.compiler.macosx.exe.debug.825236135" name="GCC C++ Compiler" superClass="cdt.managedbuild.tool.gnu.cpp.compiler.macosx.exe.debug">
<option id="gnu.cpp.compilermacosx.exe.debug.option.optimization.level.788305178" name="Optimization Level" superClass="gnu.cpp.compilermacosx.exe.debug.option.optimization.level" value="gnu.cpp.compiler.optimization.level.none" valueType="enumerated"/>
<option id="gnu.cpp.compiler.macosx.exe.debug.option.debugging.level.1465848957" name="Debug Level" superClass="gnu.cpp.compiler.macosx.exe.debug.option.debugging.level" value="gnu.cpp.compiler.debugging.level.max" valueType="enumerated"/>
</tool>
<tool id="cdt.managedbuild.tool.gnu.c.compiler.macosx.exe.debug.1465485062" name="GCC C Compiler" superClass="cdt.managedbuild.tool.gnu.c.compiler.macosx.exe.debug">
<option defaultValue="gnu.c.optimization.level.none" id="gnu.c.compiler.macosx.exe.debug.option.optimization.level.1733952803" name="Optimization Level" superClass="gnu.c.compiler.macosx.exe.debug.option.optimization.level" valueType="enumerated"/>
<option id="gnu.c.compiler.macosx.exe.debug.option.debugging.level.348355481" name="Debug Level" superClass="gnu.c.compiler.macosx.exe.debug.option.debugging.level" value="gnu.c.debugging.level.max" valueType="enumerated"/>
<option id="gnu.c.compiler.option.include.paths.877795920" superClass="gnu.c.compiler.option.include.paths" valueType="includePath">
<listOptionValue builtIn="false" value="/Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.7.sdk/usr/include"/>
</option>
<inputType id="cdt.managedbuild.tool.gnu.c.compiler.input.1372149070" superClass="cdt.managedbuild.tool.gnu.c.compiler.input"/>
</tool>
</toolChain>
</folderInfo>
</configuration>
</storageModule>
<storageModule moduleId="org.eclipse.cdt.core.externalSettings"/>
</cconfiguration>
<cconfiguration id="cdt.managedbuild.config.macosx.exe.release.932730591">
<storageModule buildSystemId="org.eclipse.cdt.managedbuilder.core.configurationDataProvider" id="cdt.managedbuild.config.macosx.exe.release.932730591" moduleId="org.eclipse.cdt.core.settings" name="Release">
<externalSettings/>
<extensions>
<extension id="org.eclipse.cdt.core.GmakeErrorParser" point="org.eclipse.cdt.core.ErrorParser"/>
<extension id="org.eclipse.cdt.core.CWDLocator" point="org.eclipse.cdt.core.ErrorParser"/>
<extension id="org.eclipse.cdt.core.GCCErrorParser" point="org.eclipse.cdt.core.ErrorParser"/>
<extension id="org.eclipse.cdt.core.GASErrorParser" point="org.eclipse.cdt.core.ErrorParser"/>
<extension id="org.eclipse.cdt.core.GLDErrorParser" point="org.eclipse.cdt.core.ErrorParser"/>
<extension id="org.eclipse.cdt.core.MachO64" point="org.eclipse.cdt.core.BinaryParser"/>
</extensions>
</storageModule>
<storageModule moduleId="cdtBuildSystem" version="4.0.0">
<configuration artifactName="${ProjName}" buildArtefactType="org.eclipse.cdt.build.core.buildArtefactType.exe" buildProperties="org.eclipse.cdt.build.core.buildType=org.eclipse.cdt.build.core.buildType.release,org.eclipse.cdt.build.core.buildArtefactType=org.eclipse.cdt.build.core.buildArtefactType.exe" cleanCommand="rm -rf" description="" id="cdt.managedbuild.config.macosx.exe.release.932730591" name="Release" parent="cdt.managedbuild.config.macosx.exe.release">
<folderInfo id="cdt.managedbuild.config.macosx.exe.release.932730591." name="/" resourcePath="">
<toolChain id="cdt.managedbuild.toolchain.gnu.macosx.exe.release.1123049511" name="MacOSX GCC" superClass="cdt.managedbuild.toolchain.gnu.macosx.exe.release">
<targetPlatform id="cdt.managedbuild.target.gnu.platform.macosx.exe.release.299819847" name="Debug Platform" superClass="cdt.managedbuild.target.gnu.platform.macosx.exe.release"/>
<builder buildPath="${workspace_loc:/avl_apuntadores}/Release" id="cdt.managedbuild.target.gnu.builder.macosx.exe.release.407785103" keepEnvironmentInBuildfile="false" managedBuildOn="true" name="Gnu Make Builder" superClass="cdt.managedbuild.target.gnu.builder.macosx.exe.release"/>
<tool id="cdt.managedbuild.tool.macosx.c.linker.macosx.exe.release.443886142" name="MacOS X C Linker" superClass="cdt.managedbuild.tool.macosx.c.linker.macosx.exe.release">
<inputType id="cdt.managedbuild.tool.macosx.c.linker.input.1036582477" superClass="cdt.managedbuild.tool.macosx.c.linker.input">
<additionalInput kind="additionalinputdependency" paths="$(USER_OBJS)"/>
<additionalInput kind="additionalinput" paths="$(LIBS)"/>
</inputType>
</tool>
<tool id="cdt.managedbuild.tool.macosx.cpp.linker.macosx.exe.release.2103621995" name="MacOS X C++ Linker" superClass="cdt.managedbuild.tool.macosx.cpp.linker.macosx.exe.release"/>
<tool id="cdt.managedbuild.tool.gnu.assembler.macosx.exe.release.210710037" name="GCC Assembler" superClass="cdt.managedbuild.tool.gnu.assembler.macosx.exe.release">
<inputType id="cdt.managedbuild.tool.gnu.assembler.input.671781664" superClass="cdt.managedbuild.tool.gnu.assembler.input"/>
</tool>
<tool id="cdt.managedbuild.tool.gnu.archiver.macosx.base.80538790" name="GCC Archiver" superClass="cdt.managedbuild.tool.gnu.archiver.macosx.base"/>
<tool id="cdt.managedbuild.tool.gnu.cpp.compiler.macosx.exe.release.1186636101" name="GCC C++ Compiler" superClass="cdt.managedbuild.tool.gnu.cpp.compiler.macosx.exe.release">
<option id="gnu.cpp.compiler.macosx.exe.release.option.optimization.level.786861570" name="Optimization Level" superClass="gnu.cpp.compiler.macosx.exe.release.option.optimization.level" value="gnu.cpp.compiler.optimization.level.most" valueType="enumerated"/>
<option id="gnu.cpp.compiler.macosx.exe.release.option.debugging.level.765350346" name="Debug Level" superClass="gnu.cpp.compiler.macosx.exe.release.option.debugging.level" value="gnu.cpp.compiler.debugging.level.none" valueType="enumerated"/>
</tool>
<tool id="cdt.managedbuild.tool.gnu.c.compiler.macosx.exe.release.376036830" name="GCC C Compiler" superClass="cdt.managedbuild.tool.gnu.c.compiler.macosx.exe.release">
<option defaultValue="gnu.c.optimization.level.most" id="gnu.c.compiler.macosx.exe.release.option.optimization.level.1492102237" name="Optimization Level" superClass="gnu.c.compiler.macosx.exe.release.option.optimization.level" valueType="enumerated"/>
<option id="gnu.c.compiler.macosx.exe.release.option.debugging.level.936445824" name="Debug Level" superClass="gnu.c.compiler.macosx.exe.release.option.debugging.level" value="gnu.c.debugging.level.none" valueType="enumerated"/>
<inputType id="cdt.managedbuild.tool.gnu.c.compiler.input.1257748817" superClass="cdt.managedbuild.tool.gnu.c.compiler.input"/>
</tool>
</toolChain>
</folderInfo>
<sourceEntries>
<entry flags="VALUE_WORKSPACE_PATH|RESOLVED" kind="sourcePath" name=""/>
</sourceEntries>
</configuration>
</storageModule>
<storageModule moduleId="org.eclipse.cdt.core.externalSettings"/>
</cconfiguration>
</storageModule>
<storageModule moduleId="cdtBuildSystem" version="4.0.0">
<project id="avl_apuntadores.cdt.managedbuild.target.macosx.exe.2072253717" name="Executable" projectType="cdt.managedbuild.target.macosx.exe"/>
</storageModule>
<storageModule moduleId="scannerConfiguration">
<autodiscovery enabled="true" problemReportingEnabled="true" selectedProfileId=""/>
<scannerConfigBuildInfo instanceId="cdt.managedbuild.config.gnu.macosx.exe.debug.731461427;cdt.managedbuild.config.gnu.macosx.exe.debug.731461427.;cdt.managedbuild.tool.gnu.c.compiler.macosx.exe.debug.1465485062;cdt.managedbuild.tool.gnu.c.compiler.input.1372149070">
<autodiscovery enabled="true" problemReportingEnabled="true" selectedProfileId=""/>
</scannerConfigBuildInfo>
<scannerConfigBuildInfo instanceId="cdt.managedbuild.config.macosx.exe.release.932730591;cdt.managedbuild.config.macosx.exe.release.932730591.;cdt.managedbuild.tool.gnu.c.compiler.macosx.exe.release.376036830;cdt.managedbuild.tool.gnu.c.compiler.input.1257748817">
<autodiscovery enabled="true" problemReportingEnabled="true" selectedProfileId=""/>
</scannerConfigBuildInfo>
</storageModule>
<storageModule moduleId="org.eclipse.cdt.core.LanguageSettingsProviders"/>
</cproject>
Raw
.project
<?xml version="1.0" encoding="UTF-8"?>
<projectDescription>
<name>avl_apuntadores</name>
<comment></comment>
<projects>
</projects>
<buildSpec>
<buildCommand>
<name>org.eclipse.cdt.managedbuilder.core.genmakebuilder</name>
<triggers>clean,full,incremental,</triggers>
<arguments>
</arguments>
</buildCommand>
<buildCommand>
<name>org.eclipse.cdt.managedbuilder.core.ScannerConfigBuilder</name>
<triggers>full,incremental,</triggers>
<arguments>
</arguments>
</buildCommand>
</buildSpec>
<natures>
<nature>org.eclipse.cdt.core.cnature</nature>
<nature>org.eclipse.cdt.managedbuilder.core.managedBuildNature</nature>
<nature>org.eclipse.cdt.managedbuilder.core.ScannerConfigNature</nature>
</natures>
</projectDescription>
Raw
avl.c
#define _XOPEN_SOURCE 500 /* Enable certain library functions (strdup) on linux. See feature_test_macros(7) */
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include <string.h>
#include <assert.h>
struct avl_node_s {
struct avl_node_s *left;
struct avl_node_s *right;
int value;
};
typedef struct avl_node_s avl_node_t;
struct avl_tree_s {
struct avl_node_s *root;
};
typedef struct avl_tree_s avl_tree_t;
/* Create a new AVL tree. */
avl_tree_t *avl_create() {
avl_tree_t *tree = NULL;
if( ( tree = malloc( sizeof( avl_tree_t ) ) ) == NULL ) {
return NULL;
}
tree->root = NULL;
return tree;
}
/* Initialize a new node. */
avl_node_t *avl_create_node() {
avl_node_t *node = NULL;
if( ( node = malloc( sizeof( avl_node_t ) ) ) == NULL ) {
return NULL;
}
node->left = NULL;
node->right = NULL;
node->value = 0;
return node;
}
/* Find the height of an AVL node recursively */
int avl_node_height( avl_node_t *node ) {
int height_left = 0;
int height_right = 0;
if( node->left ) height_left = avl_node_height( node->left );
if( node->right ) height_right = avl_node_height( node->right );
return height_right > height_left ? ++height_right : ++height_left;
}
/* Find the balance of an AVL node */
int avl_balance_factor( avl_node_t *node ) {
int bf = 0;
if( node->left ) bf += avl_node_height( node->left );
if( node->right ) bf -= avl_node_height( node->right );
return bf ;
}
/* Left Left Rotate */
avl_node_t *avl_rotate_leftleft( avl_node_t *node ) {
avl_node_t *a = node;
avl_node_t *b = a->left;
a->left = b->right;
b->right = a;
return( b );
}
/* Left Right Rotate */
avl_node_t *avl_rotate_leftright( avl_node_t *node ) {
avl_node_t *a = node;
avl_node_t *b = a->left;
avl_node_t *c = b->right;
a->left = c->right;
b->right = c->left;
c->left = b;
c->right = a;
return( c );
}
/* Right Left Rotate */
avl_node_t *avl_rotate_rightleft( avl_node_t *node ) {
avl_node_t *a = node;
avl_node_t *b = a->right;
avl_node_t *c = b->left;
a->right = c->left;
b->left = c->right;
c->right = b;
c->left = a;
return( c );
}
/* Right Right Rotate */
avl_node_t *avl_rotate_rightright( avl_node_t *node ) {
avl_node_t *a = node;
avl_node_t *b = a->right;
a->right = b->left;
b->left = a;
return( b );
}
/* Balance a given node */
avl_node_t *avl_balance_node( avl_node_t *node ) {
avl_node_t *newroot = NULL;
/* Balance our children, if they exist. */
if( node->left )
node->left = avl_balance_node( node->left );
if( node->right )
node->right = avl_balance_node( node->right );
int bf = avl_balance_factor( node );
if( bf >= 2 ) {
/* Left Heavy */
if( avl_balance_factor( node->left ) <= -1 )
newroot = avl_rotate_leftright( node );
else
newroot = avl_rotate_leftleft( node );
} else if( bf <= -2 ) {
/* Right Heavy */
if( avl_balance_factor( node->right ) >= 1 )
newroot = avl_rotate_rightleft( node );
else
newroot = avl_rotate_rightright( node );
} else {
/* This node is balanced -- no change. */
newroot = node;
}
return( newroot );
}
/* Balance a given tree */
void avl_balance( avl_tree_t *tree ) {
avl_node_t *newroot = NULL;
newroot = avl_balance_node( tree->root );
if( newroot != tree->root ) {
tree->root = newroot;
}
}
/* Insert a new node. */
void avl_insert( avl_tree_t *tree, int value ) {
avl_node_t *node = NULL;
avl_node_t *next = NULL;
avl_node_t *last = NULL;
/* Well, there must be a first case */
if( tree->root == NULL ) {
node = avl_create_node();
node->value = value;
tree->root = node;
/* Okay. We have a root already. Where do we put this? */
} else {
next = tree->root;
while( next != NULL ) {
last = next;
if( value < next->value ) {
next = next->left;
} else if( value > next->value ) {
next = next->right;
/* Have we already inserted this node? */
} else if( value == next->value ) {
/* This shouldn't happen. */
}
}
node = avl_create_node();
node->value = value;
if( value < last->value ) last->left = node;
if( value > last->value ) last->right = node;
}
avl_balance( tree );
}
/* Find the node containing a given value */
avl_node_t *avl_find( avl_tree_t *tree, int value ) {
avl_node_t *current = tree->root;
while( current && current->value != value ) {
if( value > current->value )
current = current->right;
else
current = current->left;
}
return current;
}
/* Do a depth first traverse of a node. */
void avl_traverse_node_dfs( avl_node_t *node, int depth ) {
int i = 0;
if( node->left ) avl_traverse_node_dfs( node->left, depth + 2 );
for( i = 0; i < depth; i++ ) putchar( ' ' );
printf( "%d: %d\n", node->value, avl_balance_factor( node ) );
if( node->right ) avl_traverse_node_dfs( node->right, depth + 2 );
}
/* Do a depth first traverse of a tree. */
void avl_traverse_dfs( avl_tree_t *tree ) {
avl_traverse_node_dfs( tree->root, 0 );
}
int main( int argc, char **argv ) {
avl_tree_t *tree = NULL;
int i = 0;
int r = 0;
tree = avl_create();
/* Insert 1-20 in random order -- this is suboptimal, but easy */
srand( time( NULL ) );
for( i = 0; i < 20; i++ ) {
do {
r = rand() % 20 + 1;
} while( avl_find( tree, r ) );
avl_insert( tree, r );
}
avl_traverse_dfs( tree );
return 0;
}
Raw
avl_apuntadores.c
/*
============================================================================
Name : avl_apuntadores.c
Author : ernesto
Version :
Copyright : a veces siento que
Description : Hello World in C, Ansi-style
============================================================================
*/
#define _XOPEN_SOURCE 500 /* Enable certain library functions (strdup) on linux. See feature_test_macros(7) */
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include <string.h>
#include <assert.h>
struct avl_node_s {
struct avl_node_s *left;
struct avl_node_s *right;
int value;
};
typedef struct avl_node_s avl_node_t;
struct avl_tree_s {
struct avl_node_s *root;
};
typedef struct avl_tree_s avl_tree_t;
/* Create a new AVL tree. */
avl_tree_t *avl_create() {
avl_tree_t *tree = NULL;
if ((tree = malloc(sizeof(avl_tree_t))) == NULL ) {
return NULL ;
}
tree->root = NULL;
return tree;
}
/* Initialize a new node. */
avl_node_t *avl_create_node() {
avl_node_t *node = NULL;
if ((node = malloc(sizeof(avl_node_t))) == NULL ) {
return NULL ;
}
node->left = NULL;
node->right = NULL;
node->value = 0;
return node;
}
/* Find the height of an AVL node recursively */
int avl_node_height(avl_node_t *node) {
int height_left = 0;
int height_right = 0;
if (node->left)
height_left = avl_node_height(node->left);
if (node->right)
height_right = avl_node_height(node->right);
return height_right > height_left ? ++height_right : ++height_left;
}
/* Find the balance of an AVL node */
int avl_balance_factor(avl_node_t *node) {
int bf = 0;
if (node->left)
bf += avl_node_height(node->left);
if (node->right)
bf -= avl_node_height(node->right);
return bf;
}
/* Left Left Rotate */
avl_node_t *avl_rotate_leftleft(avl_node_t *node) {
avl_node_t *a = node;
avl_node_t *b = a->left;
a->left = b->right;
b->right = a;
return (b);
}
/* Left Right Rotate */
avl_node_t *avl_rotate_leftright(avl_node_t *node) {
avl_node_t *a = node;
avl_node_t *b = a->left;
avl_node_t *c = b->right;
a->left = c->right;
b->right = c->left;
c->left = b;
c->right = a;
return (c);
}
/* Right Left Rotate */
avl_node_t *avl_rotate_rightleft(avl_node_t *node) {
avl_node_t *a = node;
avl_node_t *b = a->right;
avl_node_t *c = b->left;
a->right = c->left;
b->left = c->right;
c->right = b;
c->left = a;
return (c);
}
/* Right Right Rotate */
avl_node_t *avl_rotate_rightright(avl_node_t *node) {
avl_node_t *a = node;
avl_node_t *b = a->right;
a->right = b->left;
b->left = a;
return (b);
}
/* Balance a given node */
avl_node_t *avl_balance_node(avl_node_t *node) {
avl_node_t *newroot = NULL;
/* Balance our children, if they exist. */
if (node->left)
node->left = avl_balance_node(node->left);
if (node->right)
node->right = avl_balance_node(node->right);
int bf = avl_balance_factor(node);
if (bf >= 2) {
/* Left Heavy */
if (avl_balance_factor(node->left) <= -1)
newroot = avl_rotate_leftright(node);
else
newroot = avl_rotate_leftleft(node);
} else if (bf <= -2) {
/* Right Heavy */
if (avl_balance_factor(node->right) >= 1)
newroot = avl_rotate_rightleft(node);
else
newroot = avl_rotate_rightright(node);
} else {
/* This node is balanced -- no change. */
newroot = node;
}
return (newroot);
}
/* Balance a given tree */
void avl_balance(avl_tree_t *tree) {
avl_node_t *newroot = NULL;
newroot = avl_balance_node(tree->root);
if (newroot != tree->root) {
tree->root = newroot;
}
}
/* Insert a new node. */
void avl_insert(avl_tree_t *tree, int value) {
avl_node_t *node = NULL;
avl_node_t *next = NULL;
avl_node_t *last = NULL;
/* Well, there must be a first case */
if (tree->root == NULL ) {
node = avl_create_node();
node->value = value;
tree->root = node;
/* Okay. We have a root already. Where do we put this? */
} else {
next = tree->root;
while (next != NULL ) {
last = next;
if (value < next->value) {
next = next->left;
} else if (value > next->value) {
next = next->right;
/* Have we already inserted this node? */
} else if (value == next->value) {
/* This shouldn't happen. */
}
}
node = avl_create_node();
node->value = value;
if (value < last->value)
last->left = node;
if (value > last->value)
last->right = node;
}
avl_balance(tree);
}
/* Find the node containing a given value */
avl_node_t *avl_find(avl_tree_t *tree, int value) {
avl_node_t *current = tree->root;
while (current && current->value != value) {
if (value > current->value)
current = current->right;
else
current = current->left;
}
return current;
}
/* Do a depth first traverse of a node. */
void avl_traverse_node_dfs(avl_node_t *node, int depth) {
int i = 0;
if (node->left)
avl_traverse_node_dfs(node->left, depth + 2);
for (i = 0; i < depth; i++)
putchar(' ');
printf("%d: %d\n", node->value, avl_balance_factor(node));
if (node->right)
avl_traverse_node_dfs(node->right, depth + 2);
}
/* Do a depth first traverse of a tree. */
void avl_traverse_dfs(avl_tree_t *tree) {
avl_traverse_node_dfs(tree->root, 0);
}
int main(int argc, char **argv) {
avl_tree_t *tree = NULL;
int i = 0;
int r = 0;
tree = avl_create();
/* Insert 1-20 in random order -- this is suboptimal, but easy */
srand(time(NULL ));
for (i = 0; i < 20; i++) {
do {
r = rand() % 20 + 1;
} while (avl_find(tree, r));
avl_insert(tree, r);
}
avl_traverse_dfs(tree);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment