Created
March 21, 2015 22:08
-
-
Save kmdarshan/ab8ccdb0640f252a0528 to your computer and use it in GitHub Desktop.
Insertion and deletion into a binary search tree in objective c
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#import | |
@interface Node : NSObject{ | |
Node *left; | |
Node *right; | |
NSObject *data; | |
} | |
@property (nonatomic, strong) Node *left; | |
@property (nonatomic, strong) Node *right; | |
@property (nonatomic, strong) NSObject *data; | |
@end | |
#import "Node.h" | |
@implementation Node | |
@synthesize left; | |
@synthesize right; | |
@synthesize data; | |
@end | |
-(Node*) insertNode:(Node*) root forObject:(NSObject*)data{ | |
Node *cur = root; | |
Node *prev = NULL, *temp; | |
temp = [[Node alloc] init]; | |
temp.data = data; | |
temp.left = temp.right = NULL; | |
if(root == NULL){ | |
root = temp; | |
}else{ | |
// iterate through the nodes | |
NSString *valStr = (NSString*) data; | |
NSInteger val = [valStr intValue]; | |
while (cur != NULL) { | |
prev = cur; | |
NSString *valStr2 = (NSString*) cur.data; | |
cur = (val < [valStr2 intValue]) ? cur.left: cur.right; | |
} | |
NSString *valStr2 = (NSString*)prev.data; | |
if(val < [valStr2 intValue]){ | |
prev.left = temp; | |
}else{ | |
prev.right = temp; | |
} | |
} | |
return root; | |
} | |
-(Node*) deleteNode:(Node*) root forValue:(NSObject*) value{ | |
if (root == NULL) { | |
return root; | |
} | |
Node *curr = root; | |
Node *parent; | |
int val = [(NSString*)value intValue]; | |
while (curr != NULL && val != [(NSString*)curr.data intValue]) { | |
parent = curr; | |
curr = (val < [(NSString*)curr.data intValue]) ? curr.left : curr.right; | |
} | |
if (curr == NULL) { | |
NSLog(@"item not found"); | |
return root; | |
} | |
Node *q, *suc; | |
if (curr.left == NULL) { | |
q = curr.right; | |
}else if (curr.right == NULL){ | |
q = curr.left; | |
}else{ | |
// obtain in order successor | |
suc = curr.right; | |
while (suc.left != NULL) { | |
suc = suc.left; | |
} | |
suc.left = curr.left; | |
q = curr.right; | |
} | |
if (parent == NULL) { | |
return q; | |
} | |
if (curr == parent.left) { | |
parent.left = q; | |
}else{ | |
parent.right = q; | |
} | |
curr = NULL; | |
return root; | |
} | |
-(void) displayInorder:(Node*)root{ | |
if(root != NULL){ | |
[self displayInorder:root.left]; | |
NSLog(@"%@ ", root.data); | |
[self displayInorder:root.right]; | |
} | |
} | |
// from your main program | |
- (void) main | |
{ | |
[super viewDidLoad]; | |
Node *root = NULL; | |
NSArray *array = [[NSArray alloc] initWithObjects:@"100",@"1", @"99", @"23", @"13", nil]; | |
for (NSObject *val in array) { | |
root = [self insertNode:root forObject:val]; | |
} | |
[self deleteNode:root forValue:@"23"]; | |
[self displayInorder:root]; | |
return; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment