Kylin/DataStructure/BinarySearchTree.h

#ifndef BINARYSEARCHTREE_H
#define BINARYSEARCHTREE_H

#include "BinaryTree.h"

namespace Kylin {

/**
 * @brief The BinarySearchTree class. 右子树永远比左子树要小
 * 1.若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
 * 2.任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
 * 3.任意节点的左、右子树也分别为二叉查找树。
 * 4.没有键值相等的节点（no duplicate nodes）
 */
template <typename T>
class BinarySearchTree : public BinaryTree<T> {
public:
    using NodeT = BinaryTreeNode<T>;

    class ConstIterator : public Object {
    public:
        ConstIterator() = default;
        ConstIterator(NodeT *pos) : pos(pos) {
        }
        ConstIterator &operator++() {
            if (pos == nullptr) return *this;
            if (pos->right) {
                pos = pos->right;
                while (pos->left) pos = pos->left;
            } else {
                while ((pos->parent != nullptr) && (dynamic_cast<NodeT *>(pos->parent)->right == pos))
                    pos = dynamic_cast<NodeT *>(pos->parent);
                pos = dynamic_cast<NodeT *>(pos->parent);
            }
            return *this;
        }

        const T &operator*() {
            return pos->value;
        }

        bool operator!=(const ConstIterator &iter) {
            return pos != iter.pos;
        }

        const NodeT *pos = nullptr;
    };

    ConstIterator begin() const {
        auto node = this->root();
        while (node->left != nullptr) node = node->left;
        return ConstIterator(node);
    }

    ConstIterator end() const {
        return ConstIterator();
    }

    BinaryTreeNode<T> *find(const T &value) const override {
        return find(dynamic_cast<BinaryTreeNode<T> *>(this->m_root), value);
    }

    T maximum() {
        auto node = maximumOfNode(dynamic_cast<BinaryTreeNode<T> *>(this->m_root));
        if (node != nullptr)
            return node->value;
        else
            return T();
    }

    T minimum() {
        auto node = minimumOfNode(dynamic_cast<BinaryTreeNode<T> *>(this->m_root));
        if (node != nullptr)
            return node->value;
        else
            return T();
    }

    /**
     * @brief Find the maxinum node which these node are smaller than arg node.
     * @param node
     * @return
     */
    BinaryTreeNode<T> *predecessor(BinaryTreeNode<T> *node) {
        if (node == nullptr) return node;
        if (node->left != nullptr) return maximumOfNode(node->left);
        auto parent = dynamic_cast<BinaryTreeNode<T> *>(node->parent);
        while ((parent != nullptr) && (parent->left == node)) {
            node = parent;
            parent = dynamic_cast<BinaryTreeNode<T> *>(node->parent);
        }
        return parent;
    }

    /**
     * @brief successor Find the mininum node which these node are bigger than arg node.
     * @param node
     * @return
     */
    BinaryTreeNode<T> *successor(BinaryTreeNode<T> *node) {
        if (node == nullptr) return node;
        if (node->right != nullptr) return minimumOfNode(node->right);
        auto parent = dynamic_cast<BinaryTreeNode<T> *>(node->parent);
        if (node->right == nullptr && parent->left == node) return parent;
        while ((parent != nullptr) && (parent->right == node)) {
            node = parent;
            parent = dynamic_cast<BinaryTreeNode<T> *>(node->parent);
        }
        return parent;
    }

    bool insert(const T &value) {
        auto node = new NodeT(value);
        if (node == nullptr) return false;
        return insert(node);
    }

    void remove(const T &value) {
        BinaryTreeNode<T> *node = find(value);
        if (node == nullptr) return;
        auto del = remove(node, dynamic_cast<BinaryTreeNode<T> *>(this->m_root));
        if (del != nullptr) delete del;
    }

protected:
    /**
     * @brief find
     * @param node the root of sub-tree
     * @param value
     * @return
     */
    BinaryTreeNode<T> *find(BinaryTreeNode<T> *node, const T &value) const {
        if ((node == nullptr) || (node->value == value)) return node;
        if (value < node->value)
            return find(node->left, value);
        else if (value > node->value)
            return find(node->right, value);
        return nullptr;
    }

    BinaryTreeNode<T> *find1(BinaryTreeNode<T> *node, const T &value) const {
        while ((node != nullptr) && (node->value != value)) {
            if (value > node->value)
                node = node->right;
            else if (value < node->value)
                node = node->left;
        }
        return node;
    }

    BinaryTreeNode<T> *maximumOfNode(BinaryTreeNode<T> *node) {
        if (node == nullptr) return node;
        while (node->right != nullptr) node = node->right;
        return node;
    }

    /**
     * @brief minimumOfNode Find the maxinum node of the sub-tree which root is arg node.
     * @param node
     * @return
     */
    BinaryTreeNode<T> *minimumOfNode(BinaryTreeNode<T> *node) {
        if (node == nullptr) return node;
        while (node->left != nullptr) node = node->left;
        return node;
    }

    /**
     * @brief insert Insert node to the sub-tree which root is arg node.
     */
    bool insert(NodeT *node) {
        if (node == nullptr) return false;
        auto n = reinterpret_cast<NodeT **>(&(this->m_root));
        NodeT *parent = nullptr;
        while (*n != nullptr) {
            parent = *n;
            n = (node->value <= (*n)->value) ? &((*n)->left) : &((*n)->right);
        }
        node->parent = parent;
        *n = node;
        return true;
    }

    /**
     * @brief remove
     * @param node The tree which we want remove
     * @param tree
     * @return
     */
    BinaryTreeNode<T> *remove(BinaryTreeNode<T> *node, BinaryTreeNode<T> *tree) {
        auto parent = dynamic_cast<BinaryTreeNode<T> *>(node->parent);
        if ((node->left == nullptr) || (node->right == nullptr)) {
        }

        if ((node->left == nullptr) && (node->right == nullptr)) { // node没有左右子树
            if (parent->left == node)
                parent->left = nullptr;
            else
                parent->right = nullptr;
        } else if ((node->left != nullptr) && (node->right == nullptr)) {
            if (parent->left == node)
                parent->left = node->left;
            else
                parent->right = node->left;
        } else if ((node->left == nullptr) && (node->right != nullptr)) {
            if (parent->left == node)
                parent->left = node->right;
            else
                parent->right = node->right;
        } else {
            auto n = successor(node);
            n->left = node->left;
            if (parent->left == node)
                parent->left = node->right;
            else
                parent->right = node->right;
        }
        return node;
        /*
    BinaryTreeNode<T> *del = nullptr;
    BinaryTreeNode<T> *n = nullptr;
    if((node->left==nullptr)||(node->right==nullptr)) del = node;
    else del = successor(node);

    if(del->left!=nullptr) n = del->left;
    else n =del->right;

    if(n != nullptr) n->parent = del->parent;

    if(del->parent==nullptr) tree = n;
    else if (del == del->parent->left) del->parent->left=n;
    else del->parent->right=n;
    if(del!=node) tree->value=del->value;
    return del;
*/
    }
};
} // namespace Kylin

#endif // BINARYSEARCHTREE_H