binary search tree


See On Github

Data

Tags

search, tree

Source Code

//
//  BST.h
//  Algorithms
//
//  Created by Greg Price on 5/28/15.
//  Copyright (c) 2015 Gregory Price. All rights reserved.
//

#import <Foundation/Foundation.h>

@interface BST : NSObject

- (instancetype)initWithValue:(NSInteger)value;
- (void)addLeafIteratively:(BST *)leaf;
- (BST *)addLeafRecursively:(BST *)tree
                       leaf:(BST *)leaf;
- (BOOL)containsNodeRecursively:(BST *)tree value:(NSInteger)value;
- (BOOL)containsNodeIteratively:(BST *)tree value:(NSInteger)value;
- (void)transplant:(BST *)tree
              leaf:(BST *)leaf
       replacement:(BST *)replacement;

- (void)deleteFromTree:(BST *)tree
                  leaf:(BST *)leaf;
- (BOOL)isBalanced:(BST *)tree;
- (void)print;

@property (readonly) NSInteger minimum;
@property (readonly) NSInteger maximum;

- (BST *)minumumNode:(BST *)tree;
- (BST *)maximumNode:(BST *)tree;

@end
//
//  BST.m
//  Algorithms
//
//  Created by Greg Price on 5/28/15.
//  Copyright (c) 2015 Gregory Price. All rights reserved.
//

#import "BST.h"

@interface BST()

@property (assign) NSInteger value;
@property (assign) NSInteger height;
@property (nonatomic) BST *left;
@property (nonatomic) BST *right;
@property (nonatomic) BST *parent;
@property (nonatomic) BST *root;

@end

@implementation BST

- (instancetype)initWithValue:(NSInteger)value {
    self = [super init];
    if (self) {
        _value = value;
        _root = self;
    }
    return self;
}

- (NSInteger)minimum {
    BST *tractor = self;
    while (tractor.left != nil) {
        tractor = tractor.left;
    }
    return tractor.value;
}

- (NSInteger)maximum {
    BST *tractor = self;
    while (tractor.right != nil) {
        tractor = tractor.right;
    }
    return tractor.value;
}

- (BOOL)isBalanced:(BST *)tree {
    BOOL retval = true;
    if (tree != nil) {
        [self isBalanced:tree.left];
        if ((tree.left.left != nil) && (tree.right.right == nil)) {
            retval = false;
        }
        
        if ((tree.right.right != nil) && (tree.left.left == nil)) {
            retval = false;
        }
        [self isBalanced:tree.right];
    }
    return retval;
}


- (void)addLeafIteratively:(BST *)leaf {
    BST *runner = self.root;
    BST *trailer = nil;
    while (runner != nil) {
        trailer = runner;
        if (leaf.value <= runner.value) {
            runner = runner.left;
        } else {
            runner = runner.right;
        }
    }
    
    if (leaf.value <= trailer.value) {
        trailer.left = leaf;
    } else {
        trailer.right = leaf;
    }
    
    leaf.parent = trailer;
}

- (BST *)addLeafRecursively:(BST *)tree
                       leaf:(BST *)leaf {
    if (tree != nil) {
        if (leaf.value < tree.value) {
            tree.left = [self addLeafRecursively:tree.left
                                            leaf:leaf];
        } else {
            tree.right = [self addLeafRecursively:tree.right
                                             leaf:leaf];
        }
        return tree;
    }
    
    leaf.parent = tree;
    
    return leaf;
}

- (BOOL)containsNodeRecursively:(BST *)tree value:(NSInteger)value {
    BOOL cn = false;
    if (!tree) {
        cn = false;
    }
    if (tree.value == value) {
        cn = true;
    }
    if (tree.left) {
        cn = [self containsNodeRecursively:tree.left value:value];
    }
    if (tree.right) {
        cn = [self containsNodeRecursively:tree.right value:value];
    }
    
    return cn;
}

- (BST *)minumumNode:(BST *)tree {
    while (tree.left != nil) {
        tree = tree.left;
    }
    return tree;
}

- (BST *)maximumNode:(BST *)tree {
    while (tree.right != nil) {
        tree = tree.right;
    }
    return tree;
}

- (BOOL)containsNodeIteratively:(BST *)tree value:(NSInteger)value {
    BOOL cn = false;
    BST *tractor = tree;
    while (tractor != nil) {
        if (tractor.value == value) {
            cn = true;
            break;
        }
        if (value < tractor.value) {
            tractor = tractor.left;
        } else {
            tractor = tractor.right;
        }
    }
    return cn;
}

- (void)transplant:(BST *)tree
              leaf:(BST *)leaf
       replacement:(BST *)replacement {
    if (leaf.parent == nil) {
        tree.root = replacement;
    }
    else if (leaf == leaf.parent.left) {
        leaf.parent.left = replacement;
    } else {
        leaf.parent.right = replacement;
    }
    
    if (replacement) {
        replacement.parent = leaf.parent;
    }
}

- (void)deleteFromTree:(BST *)tree
                  leaf:(BST *)leaf {
    if (leaf.left == nil) {
        [self transplant:tree
                    leaf:leaf
             replacement:leaf.right];
    } else if (leaf.right == nil) {
        [self transplant:tree
                    leaf:leaf
             replacement:leaf.left];
    } else {
        BST *left = [self minumumNode:leaf.right];
        if (left.parent != leaf) {
            [self transplant:tree
                        leaf:left
                 replacement:left.right];
            left.right = leaf.right;
            leaf.right.parent = left;
        }
        
        [self transplant:tree
                    leaf:leaf
             replacement:left];
        left.left = leaf.left;
        left.left.parent = left;
    }
    
}

- (void)print {
    [self print:self];
}

- (void)print:(BST *)tree {
    if (tree != nil) {
        [self print:tree.left];
        NSLog(@"node = %lu", tree.value);
        [self print:tree.right];
    }
}

@end
//
//  BSTTests.m
//  Algorithms
//
//  Created by Greg Price on 8/9/15.
//  Copyright (c) 2015 Gregory Price. All rights reserved.
//

#import <UIKit/UIKit.h>
#import <XCTest/XCTest.h>
#import "BST.h"

@interface BSTTests : XCTestCase

@end

@implementation BSTTests

- (void)testIterativeTreeBuild {
    BST *tree = [[BST alloc] initWithValue:2];
    [tree addLeafIteratively:[[BST alloc] initWithValue:5]];
    [tree addLeafIteratively:[[BST alloc] initWithValue:4]];
    [tree addLeafIteratively:[[BST alloc] initWithValue:10]];
    [tree addLeafIteratively:[[BST alloc] initWithValue:8]];
    [tree print];
}

- (void)testRecursiveTreeBuild {
    BST *tree = [[BST alloc] initWithValue:2];
    [tree addLeafRecursively:tree leaf:[[BST alloc] initWithValue:3]];
    [tree addLeafRecursively:tree leaf:[[BST alloc] initWithValue:8]];
    [tree addLeafRecursively:tree leaf:[[BST alloc] initWithValue:15]];
    [tree addLeafRecursively:tree leaf:[[BST alloc] initWithValue:9]];
    [tree addLeafRecursively:tree leaf:[[BST alloc] initWithValue:2]];
    [tree print];
}

- (void)testPrint {
    BST *tree = [[BST alloc] initWithValue:2];
    [tree addLeafRecursively:tree leaf:[[BST alloc] initWithValue:3]];
    [tree addLeafRecursively:tree leaf:[[BST alloc] initWithValue:8]];
    [tree addLeafRecursively:tree leaf:[[BST alloc] initWithValue:15]];
    [tree addLeafRecursively:tree leaf:[[BST alloc] initWithValue:9]];
    [tree addLeafRecursively:tree leaf:[[BST alloc] initWithValue:2]];
    [tree print];
}

- (void)testContainsNode {
    BST *tree = [[BST alloc] initWithValue:2];
    [tree addLeafRecursively:tree leaf:[[BST alloc] initWithValue:3]];
    [tree addLeafRecursively:tree leaf:[[BST alloc] initWithValue:8]];
    [tree addLeafRecursively:tree leaf:[[BST alloc] initWithValue:15]];
    [tree addLeafRecursively:tree leaf:[[BST alloc] initWithValue:9]];
    [tree addLeafRecursively:tree leaf:[[BST alloc] initWithValue:2]];
    XCTAssertTrue([tree containsNodeRecursively:tree value:9]);
    
}

- (void)testContainsNodeIter {
    BST *tree = [[BST alloc] initWithValue:2];
    [tree addLeafRecursively:tree leaf:[[BST alloc] initWithValue:3]];
    [tree addLeafRecursively:tree leaf:[[BST alloc] initWithValue:8]];
    [tree addLeafRecursively:tree leaf:[[BST alloc] initWithValue:15]];
    [tree addLeafRecursively:tree leaf:[[BST alloc] initWithValue:9]];
    [tree addLeafRecursively:tree leaf:[[BST alloc] initWithValue:2]];
    [tree print];
    
    XCTAssertTrue([tree containsNodeIteratively:tree value:9]);
}

- (void)testMinMax {
    BST *tree = [[BST alloc] initWithValue:2];
    [tree addLeafRecursively:tree leaf:[[BST alloc] initWithValue:3]];
    [tree addLeafRecursively:tree leaf:[[BST alloc] initWithValue:8]];
    [tree addLeafRecursively:tree leaf:[[BST alloc] initWithValue:15]];
    [tree addLeafRecursively:tree leaf:[[BST alloc] initWithValue:9]];
    [tree addLeafRecursively:tree leaf:[[BST alloc] initWithValue:2]];
    XCTAssert([tree minimum] == 2);
    XCTAssert([tree maximum] == 15);
}

- (void)testTransplant {
    BST *tree = [[BST alloc] initWithValue:2];
    BST *leaf = [[BST alloc] initWithValue:3];
    [tree addLeafIteratively:leaf];
    [tree addLeafIteratively:[[BST alloc] initWithValue:8]];
    [tree print];
    [tree transplant:tree leaf:leaf replacement:[[BST alloc] initWithValue:20]];
    [tree print];
    
}

- (void)testIsBalanced {
    BST *tree = [[BST alloc] initWithValue:2];
    [tree addLeafIteratively:[[BST alloc] initWithValue:1]];
    [tree addLeafIteratively:[[BST alloc] initWithValue:3]];
    BOOL isBalanced = [tree isBalanced:tree];
    XCTAssert(isBalanced);
}

- (void)testTreeDelete {
    BST *tree = [[BST alloc] initWithValue:2];
    BST *leaf = [[BST alloc] initWithValue:3];
    BST *leaf2 = [[BST alloc] initWithValue:4];
    BST *leaf3 = [[BST alloc] initWithValue:5];
    [tree addLeafIteratively:leaf];
    [tree addLeafIteratively:leaf2];
    [tree addLeafIteratively:leaf3];
    [tree addLeafIteratively:[[BST alloc] initWithValue:6]];
    [tree addLeafIteratively:[[BST alloc] initWithValue:15]];
    [tree addLeafIteratively:[[BST alloc] initWithValue:6]];
    [tree addLeafIteratively:[[BST alloc] initWithValue:12]];
    [tree print];
    [tree deleteFromTree:tree leaf:leaf3];
    [tree print];
}

@end