Created
June 17, 2015 10:28
-
-
Save Nonouf/6e9e41bd977328bbb763 to your computer and use it in GitHub Desktop.
Simple Objective-C AVL Tree
This file contains hidden or 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
// | |
// AVLTree.h | |
// AVLTree-ObjC | |
// | |
// Created by Arnaud Schildknecht on 17/06/15. | |
// Copyright (c) 2015 Arnaud Schildknecht. All rights reserved. | |
// | |
#import <Foundation/Foundation.h> | |
@interface AVLTree : NSObject | |
@property (strong, nonatomic) id data; | |
@property (strong, nonatomic) AVLTree *right; | |
@property (strong, nonatomic) AVLTree *left; | |
@property (nonatomic) int count; | |
- (void)addValue: (id)value; | |
- (NSArray*)inOrder; | |
- (NSArray*)preOrder; | |
- (NSArray*)postOrder; | |
@end |
This file contains hidden or 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
// | |
// AVLTree.m | |
// AVLTree-ObjC | |
// | |
// Created by Arnaud Schildknecht on 17/06/15. | |
// Copyright (c) 2015 Arnaud Schildknecht. All rights reserved. | |
// | |
#import "AVLTree.h" | |
@implementation AVLTree | |
- (id)init | |
{ | |
self = [super init]; | |
if (self) { | |
_count = 0; | |
} | |
return self; | |
} | |
- (void)addValue: (id)value { | |
if (!self.data) | |
self.data = value; | |
else | |
[self add:value]; | |
++_count; | |
} | |
- (void)add: (id)value { | |
if (value < self.data) { | |
if (self.left) | |
[self.left addValue:value]; | |
else { | |
self.left = [[AVLTree alloc] init]; | |
[self.left setData:value]; | |
} | |
} | |
else { | |
if (self.right) | |
[self.right addValue:value]; | |
else { | |
self.right = [[AVLTree alloc] init]; | |
[self.right setData:value]; | |
} | |
} | |
} | |
- (NSArray*)inOrder { | |
NSMutableArray *datas = [[NSMutableArray alloc] init]; | |
[self inOrder:self datas:datas]; | |
return datas; | |
} | |
- (void)inOrder: (AVLTree*)root datas:(NSMutableArray*)datas { | |
if (root) { | |
[self inOrder:root.left datas:datas]; | |
[datas addObject:root.data]; | |
[self inOrder:root.right datas:datas]; | |
} | |
} | |
- (NSArray*)preOrder { | |
NSMutableArray *datas = [[NSMutableArray alloc] init]; | |
[self preOrder:self datas:datas]; | |
return datas; | |
} | |
- (void)preOrder: (AVLTree*)root datas:(NSMutableArray*)datas { | |
if (root) { | |
[datas addObject:root.data]; | |
[self preOrder:root.left datas:datas]; | |
[self preOrder:root.right datas:datas]; | |
} | |
} | |
- (NSArray*)postOrder { | |
NSMutableArray *datas = [[NSMutableArray alloc] init]; | |
[self postOrder:self datas:datas]; | |
return datas; | |
} | |
- (void)postOrder: (AVLTree*)root datas:(NSMutableArray*)datas { | |
if (root) { | |
[self postOrder:root.left datas:datas]; | |
[self postOrder:root.right datas:datas]; | |
[datas addObject:root.data]; | |
} | |
} | |
@end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment