Skip to content

Instantly share code, notes, and snippets.

@pocketkk

pocketkk/avl.swift

Last active November 3, 2015 16:48
Show Gist options
  • Save pocketkk/43173a267eae1718f83c to your computer and use it in GitHub Desktop.
Save pocketkk/43173a267eae1718f83c to your computer and use it in GitHub Desktop.
Download ZIP
AVL Tree
Raw
avl.swift
import UIKit
class Thing {
var value : Int
init(v: Int) {
value = v
}
}
class ThingBST {
var parent : ThingBST? = nil
var index : Thing? = nil
var left : ThingBST? = nil
var right : ThingBST? = nil
var height : Int = 0
func setHeight() {
var value = 1 // Value of current node
if right != nil && left != nil {
if right!.height >= left!.height {
value += right!.height
} else {
value += left!.height
}
}
if left == nil && right != nil{
value += right!.height
}
if right == nil && left != nil{
value += left!.height
}
if height != value {
height = value
}
}
func reverseUpTreeSetHeights() {
if self.parent != nil {
parent?.setHeight()
parent?.reverseUpTreeSetHeights()
}
}
func balanceBst() {
println("BALANCE BST! \(index?.value)")
// convert nils to zero
var leftHeight = 0
var rightHeight = 0
if left != nil {
leftHeight = left!.height
}
if right != nil {
rightHeight = right!.height
}
if abs(leftHeight - rightHeight) >= 2 {
if rightHeight > leftHeight {
if right?.left?.height > right?.right?.height {
rotateLeftRight()
} else {
rotateLeft()
}
} else {
if left?.right?.height > left?.left?.height {
rotateRightLeft()
} else {
rotateRight()
}
}
}
}
func bstFromComponents(index: Thing, right: ThingBST?, left: ThingBST?, parent: ThingBST) -> ThingBST{
var thingy = ThingBST()
thingy.index = index
thingy.right = right
thingy.left = left
thingy.parent = parent
thingy.setHeight()
return thingy
}
func rotateLeft() {
println("ROTATE LEFT")
var lefty = left?
var righty = right?
var parenty = parent?
var indexy = index!
index = right?.index
left = bstFromComponents(indexy, right: right?.left, left: lefty, parent: self)
right = right?.right
}
func rotateRight() {
println("ROTATE RIGHT")
var lefty = left?
var righty = right?
var parenty = parent?
var indexy = index!
index = left?.index
right = bstFromComponents(indexy, right: righty, left: left?.left, parent: self)
left = left?.left
}
func rotateRightLeft() {
println("ROTATE RIGHT-LEFT")
left?.rotateLeft()
rotateRight()
}
func rotateLeftRight() {
println("ROTATE LEFT-RIGHT")
right?.rotateRight()
rotateLeft()
}
func addThing(thing: Thing) {
// If the node is empty thing is initial value
if index == nil {
index = thing
height = 1
reverseUpTreeSetHeights()
parent?.parent?.balanceBst()
return
}
// If thing value is less than value then split left
if thing.value < index?.value {
if left == nil {
left = ThingBST()
left?.parent = self
}
left!.addThing(thing)
return
}
// If thing value is greater than value then split right
if thing.value > index?.value {
if right == nil {
right = ThingBST()
right?.parent = self
}
right!.addThing(thing)
return
}
}
// Take a child BST and add elements to root BST
private func processBST(bst: ThingBST) {
addThing(bst.index!)
if bst.left != nil { processBST(bst.left!) }
if bst.right != nil { processBST(bst.right!) }
}
private func deleteThing(thing: Thing, bst: ThingBST) {
// if thing is root of tree
if parent == nil {
if bst.right? != nil {
var leftTemp = bst.left?
var childLeft = bst.right?.left
bst.index = bst.right?.index
bst.right = bst.right?.right
bst.left = childLeft
if leftTemp != nil { processBST(leftTemp!) }
}
}
// if thing value is on left side of parent
if parent?.index?.value > thing.value {
if bst.right? != nil {
parent?.left = bst.right!
}
if bst.left? != nil {
parent?.left?.processBST(bst.left!)
}
if bst.right? == nil && bst.left? == nil {
parent?.left = nil
}
}
// if thing value is on right side of parent
if parent?.index?.value < thing.value {
if bst.right? != nil {
parent?.right = bst.right!
}
if bst.left? != nil {
parent?.right?.processBST(bst.left!)
}
if bst.left? == nil && bst.right? == nil {
parent?.right = nil
}
}
}
func deleteThingbyValue(value: Int) -> Bool? {
if value == index?.value {
deleteThing(index!, bst: self)
return true
} else if value < index?.value {
return left?.deleteThingbyValue(value)
} else if value > index?.value {
return right?.deleteThingbyValue(value)
}
return false
}
func findThingbyValue(value: Int) -> Thing? {
if value == index?.value {
return index
} else if (value < index?.value) {
return left?.findThingbyValue(value)
} else if (value > index?.value) {
return right?.findThingbyValue(value)
} else {
return nil
}
}
func findBstByValue(value: Int) -> ThingBST? {
if value == index?.value {
printValues(self)
return self
} else if (value < index?.value) {
return left?.findBstByValue(value)
} else if (value > index?.value) {
return right?.findBstByValue(value)
} else {
return nil
}
}
func printValues(forBST: ThingBST) {
println("Parent: \(forBST.parent?.index?.value) Index: \(forBST.index?.value), Height: \(forBST.height), Left: \(forBST.left?.height), Right: \(forBST.right?.height), Right-Val: \(forBST.right?.index?.value)")
if forBST.right? != nil {
println("RIGHT")
printValues(forBST.right!)
}
if forBST.left? != nil {
println("LEFT")
printValues(forBST.left!)
}
}
func printTree() -> [Int]{
var arr = [Int]()
if let a = index?.value {
println("\(a): Height: \(height)")
arr.append(a)
}
if let l = left? {
arr += l.printTree()
}
if let r = right? {
arr += r.printTree()
}
return arr
}
func print(bst: ThingBST) {
println("Index: \(index?.value) L: \(left?.index?.value) R: \(right?.index?.value)")
}
}
//BST Tests
class BstTest {
var result = [Int: Bool]()
func assert(value: Int, inBst: ThingBST) -> Bool {
return value == inBst.findThingbyValue(value)?.value
}
func assert(arrayOfThings: [Thing], inBst: ThingBST) -> Bool {
for thing in arrayOfThings {
let num = thing.value
if num != inBst.findThingbyValue(num)?.value {
return false
}
}
return true
}
func assert(eachIndexValue: [Int], inBst: ThingBST) -> [Int: Bool]{
for num in eachIndexValue {
if num != inBst.findThingbyValue(num)?.value {
println("\(num) is not in BST")
result[num] = false
} else {
result[num] = true
}
}
return result
}
func assertNot(eachIndexValue: [Int], inBst: ThingBST) -> Bool {
for num in eachIndexValue {
if num == inBst.findThingbyValue(num)?.value {
return false
}
}
return true
}
func assertBalanced(bst: ThingBST) -> Bool {
// convert nils to zero
var leftHeight = 0
var rightHeight = 0
if bst.left != nil {
leftHeight = bst.left!.height
}
if bst.right != nil {
rightHeight = bst.right!.height
}
if abs(leftHeight - rightHeight) >= 2 {
println("BST is balanced: FALSE for \(bst.index?.value)")
return false
} else {
if bst.left != nil {
return assertBalanced(bst.left!)
}
if bst.right != nil {
return assertBalanced(bst.right!)
}
}
return false
}
}
println("***************************************")
extension Array{
func contains<T: Comparable>(val: T) -> Bool{
for x in self {
if val == x as T { return true }
}
return false
}
}
let y : [Int] = [1,2,3]
y.contains(1)
func uniqueItemsInArrays<T: Comparable>(left: [T], right: [T]) -> [T] {
var result = [T]()
for item in left {
if !right.contains(item) {
result.append(item)
}
}
for item in right {
if !left.contains(item) {
result.append(item)
}
}
return result
}
let x = uniqueItemsInArrays([1,2,3], [3,4,5])
//Build test bst with values from arr
//let arr = [5,2,1]
let arr = [10,15,12,34,101,2,15,21,67,99,1234,34]
var thingBST = ThingBST()
var things = [Thing]()
for num in arr {
let t = Thing(v: num)
println("Order created: \(num)")
things.append(t)
thingBST.addThing(t)
}
//thingBST.printTree()
BstTest().assertBalanced(thingBST)
//Check to see if all things are findable in thingBST
BstTest().assert(things, inBst: thingBST)
BstTest().assert(arr, inBst: thingBST)
thingBST.print(thingBST)
thingBST.printTree()
var sixtyseven = thingBST.findBstByValue(12)
thingBST.findBstByValue(1234)
////Check delete thing
//
//let arr2 = [10,50,101,130,2,15,19,36,23]
//
//thingBST.deleteThingbyValue(22)
//thingBST.deleteThingbyValue(35)
//thingBST.deleteThingbyValue(21)
//thingBST.deleteThingbyValue(121)
//
//BstTest().assert(arr2, inBst: thingBST)
//BstTest().assertNot(uniqueItemsInArrays(arr, arr2), inBst: thingBST)
//
//thingBST.addThing(Thing(v: 1234))
//BstTest().assert(1234, inBst: thingBST)
//
//thingBST.addThing(Thing(v: 1234))
//BstTest().assert(1234, inBst: thingBST)
//thingBST.deleteThingbyValue(1234)
//BstTest().assert(1234, inBst: thingBST)
//BstTest().assertBalanced(thingBST)
//thingBST.printTree()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment