Skip to content

Instantly share code, notes, and snippets.

@Nonouf
Created June 17, 2015 10:28
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Nonouf/6e9e41bd977328bbb763 to your computer and use it in GitHub Desktop.
Save Nonouf/6e9e41bd977328bbb763 to your computer and use it in GitHub Desktop.
Simple Objective-C AVL Tree
//
// 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
//
// 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