Binary Search Trees

Structure of Binary Search Trees

class BinaryNode
class BinarySearchNode
class BinarySearchTree

template<typename Type>
class BinaryNode {
    private:
        Type _element;
        Type *_left_node;
        Type *_right_node;

    public:
        BinaryNode(Type const &);
        Type retrieve() const;
        BinaryNode *left() const;
        BinaryNode *right() const;
        bool is_empty() const; 
        bool is_leaf() const;
        int size() const;
        int height() const;
        void clear();
};

BinarySearchNode

template <typename Comparable>
class BinarySearchNode:public BinaryNode<Comparable> {
    private:
        using BinaryNode<Comparable>::_element;
        using BinaryNode<Comparable>::_left_node;
        using BinaryNode<Comparable>::_right_node;

    public:
        BinarySearchNode(Type cnst &);

        BinarySearchNode *left() const;
        BinarySearchNode *right() const;
        Comparable front() const;
        Comparable back() const;
        bool find(Comparable const &);

        void clear();
        void insert(Comparable const &);
        void erase(Comparable const &, BinarySearchNode *&);

        friend class BinarySearchTree<Comparable>;
}

Member functions

Constructor

template<typename Comparable>
BinarySearchNode<Comparable>::BinarySearchNode(Comprable const & obj):
    BinaryNode<Comparable> (obj) {
    // empty constructor
}

Finding Min and Max

Minimum: front of the left subtree

Maximum: back of the right subtree

front()

template<typename Comparable>
Comparable BinarySearchNode<Comparable>::front() {
    if (is_empty()) 
        throw underflow();
    return (left()->is_empty()) ? retrieve() : left()->front();
}

back()

template<typename Comparable>
Comparable BinarySearchNode<Comparable>::back() {
    if (is_empty()) 
        throw underflow();
    return (right()->is_empty()) ? retrieve() : right()->back();
}

Find if a value exists

template<typename Type>
    bool Binary_search_node<Type>::find(Type const &obj) const {

    }

Insert

template<typename Type>
    void Binary_search_node<Type>::insert(Type const &obj) {
        if (empty()) {

        } else if (obj < retriev()) {
            return ..
        } else if (obj > retrieve() ) {
            return 
        }
    }

Erase

Recursive call erase() on either left or right subtrees.
Once you find the node that needs to be deleted, we have three cases
- deleting a leaf node
- deleting a full node
- deleting a node with only one child

template<typename Type>
    bool Binary_search_node<Type>::erase(Type &obj, Binary_search_node *&ptr_to_this) {
        if (empty()) {
            return false;
        } else if ( obj == retrieve() ) { // leaf node
            if (is_leaf()) {
                ptr_to_this = nullptr;
                delete this;
            } else if (!left()->empty() && !right()->empty()) { // full node
                element = right()->front();   //min val in the right subtree -->  (logical successor)
                right()->erase(retrieve(), right_tree);
            } else { // only one child
                ptr_to_this = (!left()->empty()) ? left() : right();
                delete this;
            }

            return true;
        } else if (obj < retreive()) {
            return left()->erase(obj, left_tree);
        } else {
            return right()->erase(obj, right_tree);
        }
    }

In-order traversal of a binary search tree will result in sorting the elements.

Pre-order:

void IntBinaryTree::displayPreOrder(TreeNode *tree) const {

}

Post-order:

void IntBinaryTree::displayPostOrder(TreeNode *tree) const {

}



In [ ]: