Binary Search Trees, Splay Trees, AVL Trees

[lusty lagoon]

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.

[jagged sorrel]

Splay Tree finds:

bool find(const Comparable &c, SplayNode* &n, int &depth) {
    if (n == nullptr) {
        // Reached a dead end. Value not in tree.
        return false;
    }
    ++depth;
    if (c < n->value) {
        // Value is less than current node. Go to node's left child.
        return find(c, n->leftChild, depth);
    }
    if (n->value < c) {
        // Value is greater than current node. Go to node's right child.
        return find(c, n->rightChild, depth);
    }
    // If code reaches here, c == n->value. Node found!
    splay(n);
    return true;
}

bool find(const Comparable &c, int &depth) {
    // calls private helper function
    return find(c, root, depth);
}

AVL Tree finds:

bool find(const Comparable &c, AVLNode* n, int &depth) const {
    if (n == nullptr) {
        // Reached a dead end. Value not in tree.
        return false;
    }
    if (c < n->value) {
        // Value is less than current node. Go to node's left child.
        return find(c, n->leftChild, ++depth);
    }
    if (n->value < c) {
        // Value is greater than current node. Go to node's right child.
        return find(c, n->rightChild, ++depth);
    }
    // If code reaches here, c == n->value. Node found!
    return true;
}

int getNodeHeight(AVLNode* &n) const {
    return (n == nullptr) ? -1 : n->height;
}

bool find(const Comparable &c, int &depth) const {
    // calls private helper function
    return find(c, root, depth);
}

Main:
BinarySearchTree<int> bst1;
if (!bst1.add(8)) {
cout << "Could not add 8 to the tree." << endl;
}
if (!bst1.add(10)) {
cout << "Could not add 10 to the tree." << endl;
}
if (!bst1.add(100)) {
cout << "Could not add 8 to the tree." << endl;
}

int valueToFind = 8;
int depth = 0;
bool found = bst1.find(valueToFind, depth);
if (found) {
    cout << "Found " << valueToFind << " in the tree at depth " << depth << "." << endl;
} else {
    cout << "Did not find " << valueToFind << " in the tree. Last node visited at depth " << depth << "." << endl;
}
if (bst1.getSize() != 1) {
    cout << "There are " << bst1.getSize() << " nodes in the tree." << endl;
} else {
    cout << "There is one node in the tree." << endl;
}
bst1.timber();

SplayTree<int> test;
for (int i = 0; i < 100; ++i) {
    if (!test.add(i)) {
        cout << "Could not add " << i << endl;
    }
}
cout << "Size: " << test.getSize() << endl;
for (int i = 0; i < 100; ++i) {
    int depth = -2;
    if (test.find(i, depth)) {
        cout << "Found " << i << " at depth " << depth << endl;
    } else {
        cout << "Could not find " << i << ". Last node visited at depth " << depth << endl;
    }
}

AVLTree<int> avl1;
for (int i = 0; i < 100; ++i) {
    if (!avl1.add(i)) {
        cout << "Could not add " << i << endl;
    }
}

cout<< "Size: " << avl1.getSize() << endl;
for (int i = 0; i < 100; ++i) {
    int depth = -2;
    if (avl1.find(i, depth)) {
        cout << "Found " << i << " at depth " << depth << endl;
    } else {
        cout << "Could not find " << i << ". Last node visited at depth " << depth << endl;
    }
}



return 0;

}

i think my BST is fine but the other two are just a bit off