Last active
August 29, 2015 14:21
-
-
Save Nonouf/fd6051c6bb4750ef28ab to your computer and use it in GitHub Desktop.
Simple Swift 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.swift | |
// AVLTree-Swift | |
// | |
// Created by Arnaud Schildknecht on 22/05/15. | |
// Copyright (c) 2015 Arnaud Schildknecht. All rights reserved. | |
// | |
class AVLTree<T: Comparable> { | |
var data: T? | |
var left: AVLTree? | |
var right: AVLTree? | |
init() { | |
} | |
func addValue(value: T) { | |
if (self.data == nil) { | |
self.data = value | |
} | |
else { | |
add(value) | |
} | |
} | |
private func add(value: T) { | |
if (value < self.data) { | |
if (self.left != nil) { | |
self.left?.addValue(value) | |
} | |
else { | |
self.left = AVLTree<T>() | |
self.left?.data = value | |
} | |
} | |
else { | |
if (self.right != nil) { | |
self.right?.addValue(value) | |
} | |
else { | |
self.right = AVLTree<T>() | |
self.right?.data = value | |
} | |
} | |
} | |
func inOrder() -> [T] { | |
var datas = Array<T>() | |
inOrder(self, datas: &datas) | |
return datas | |
} | |
private func inOrder(root: AVLTree<T>?, inout datas: [T]) { | |
if (root != nil) { | |
inOrder(root?.left, datas: &datas) | |
datas.append((root?.data)!) | |
inOrder(root?.right, datas: &datas) | |
} | |
} | |
func preOrder() -> [T] { | |
var datas = Array<T>() | |
preOrder(self, datas: &datas) | |
return datas | |
} | |
private func preOrder(root: AVLTree<T>?, inout datas: [T]) { | |
if (root != nil) { | |
datas.append((root?.data)!) | |
preOrder(root?.left, datas: &datas) | |
preOrder(root?.right, datas: &datas) | |
} | |
} | |
func postOrder() -> [T] { | |
var datas = Array<T>() | |
postOrder(self, datas: &datas) | |
return datas | |
} | |
private func postOrder(root: AVLTree<T>?, inout datas: [T]) { | |
if (root != nil) { | |
postOrder(root?.left, datas: &datas) | |
postOrder(root?.right, datas: &datas) | |
datas.append((root?.data)!) | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment