Balance Binary Search Tree

Balance Binary Search Tree(构建平衡二叉搜索树)

题目描述：

例子：

解题思路：

代码如下：

//
// Created by mfzhu on 2017/4/10.
//
#include <iostream>
#include <memory>


using namespace std;
template <typename T>
class TreeNode{
public:
    T value;
    int height;
    TreeNode<T>* left;
    TreeNode<T>* right;
    TreeNode(T key): value(key),height(0),left(NULL),right(NULL){};
    TreeNode(T key, int h):value(key), height(h), left(NULL), right(NULL){};
};
template <typename T>
class AVLTree{
public:
    AVLTree():root(NULL){};
    ~AVLTree(){};

    int height();
    T maximum();
    T minimum();
    void inOrder();
    void preOrder();

    void insert(T value);
    TreeNode<T>* remove(TreeNode<T>* key);
    TreeNode<T>* search(T value);

private:
    TreeNode<T>* root;
    int height(TreeNode<T>* node);
    TreeNode<T>* maximum(TreeNode<T>* node);
    TreeNode<T>* minimum(TreeNode<T>* node);
    void inOrder(TreeNode<T>* node);
    void preOrder(TreeNode<T>* node);

    TreeNode<T>* insert(TreeNode<T>* &node, T value);
    TreeNode<T>* remove(TreeNode<T>* &node, TreeNode<T>* key);
    TreeNode<T>* search(TreeNode<T>* node, T val);

    TreeNode<T>* leftLeftRotation(TreeNode<T>* &node);
    TreeNode<T>* leftRightRotation(TreeNode<T>* &node);
    TreeNode<T>* rightLeftRotation(TreeNode<T>* &node);
    TreeNode<T>* rightRightRotation(TreeNode<T>* &node);

};
template <typename T>
int AVLTree<T>::height(TreeNode<T>* node){
    if (node) return node->height;
    return 0;
}
template <typename T>
int AVLTree<T>::height() {
    return height(root);
}


template <typename T>
TreeNode<T>* AVLTree<T>::maximum(TreeNode<T> *node) {
    if (!node)
        return NULL;
    while(node->right){
        node = node->right;
    }
    return node;
}
template <typename T>
T AVLTree<T>::maximum() {
    TreeNode<T>* p = maximum(root);
    if (p) return p->value;
    return T(NULL);
}


template<typename T>
TreeNode<T>* AVLTree<T>::minimum(TreeNode<T> *node) {
    if (!node)
        return NULL;
    while(node->left){
        node = node->left;
    }
    return node;
}
template <typename T>
T AVLTree<T>::minimum(){
    TreeNode<T>* p = minimum(root);
    if (p) return p->value;
    return T(NULL);
}

template <typename T>
void AVLTree<T>::inOrder(TreeNode<T> *node) {
    if (node){
        inOrder(node->left);
        cout << node->value << " ";
        inOrder(node->right);
    }
}
template <typename T>
void AVLTree<T>::inOrder() {
    inOrder(root);
}

template <typename T>
void AVLTree<T>::preOrder(TreeNode<T>* node) {
    if (node){
        cout << node->value << " ";
        preOrder(node->left);
        preOrder(node->right);
    }
}
template <typename T>
void AVLTree<T>::preOrder() {
    preOrder(root);
}

template <typename T>
TreeNode<T>* AVLTree<T>::insert(TreeNode<T>* &node, T value) {
    if (node == NULL){
        node = new TreeNode<T>(value);
    }
    else if (value < node->value){
        node->left = insert(node->left, value);
        if (height(node->left) - height(node->right) == 2){
            if (value < node->left->value){
                node = leftLeftRotation(node);
            }else{
                node = leftRightRotation(node);
            }
        }
    }
    else if (value > node->value){
        node->right = insert(node->right, value);
        if (height(node->right) - height(node->left) == 2){
            if (value > node->right->value){
                node = rightRightRotation(node);
            }else{
                node = rightLeftRotation(node);
            }
        }
    }
    else{
        cout << "can not insert existed value" << endl;
    }
    node->height = max(height(node->left), height(node->right)) + 1;
    return node;
}
template <typename T>
void AVLTree<T>::insert(T value) {
    insert(root, value);
}


template <typename T>
TreeNode<T>* AVLTree<T>::remove(TreeNode<T> *&node, TreeNode<T>* key) {
    if (node == NULL || key == NULL)
        return NULL;
    if (key->value < node->value){
        node->left = remove(node->left, key);
        if (height(node->right) - height(node->left) == 2){
            TreeNode<T>* l = node->right;
            if (height(l->right) > height(l->left)){
                node = rightRightRotation(node);
            }else{
                node = rightLeftRotation(node);
            }
        }
    }
    else if (key->value > node->value){
        node->right = remove(node->right, key);
        if (height(node->left) - height(node->right) == 2){
            TreeNode<T>* l = node->left;
            if (height(l->left) > height(l->right)){
                node = leftLeftRotation(node);
            }else{
                node = leftRightRotation(node);
            }
        }
    }
    else{
        if (node->left && node->right){
            if (height(node->left) > height(node->right)){
                TreeNode<T>* max = maximum(node->left);
                node->value = max->value;
                node->left = remove(node->left, max);
            }else{
                TreeNode<T>* min = minimum(node->right);
                node->value = min->value;
                node->right = remove(node->right, min);
            }

        }
        else{
            TreeNode<T>* tmp = node;
            node = node->left ? node->right : node->left;
            delete(tmp);
        }
    }
    return node;

}
template <typename T>
TreeNode<T>* AVLTree<T>::remove(TreeNode<T>* key) {
    return remove(root, key);
}


template <typename T>
TreeNode<T>* AVLTree<T>::search(TreeNode<T> *node, T val) {
    if (!node){
        cout << "the value is not in the tree" << endl;
        return NULL;
    }
    if (node->value == val) {
        cout << "the value is in the tree" <<endl;
        return node;
    }

    if (val < node->value){
        return search(node->left, val);
    }
    else{
        return search(node->right, val);
    }
}
template <typename T>
TreeNode<T>* AVLTree<T>::search(T value) {
    return search(root, value);
}

template <typename T>
TreeNode<T>* AVLTree<T>::leftLeftRotation(TreeNode<T>* &node) {
    TreeNode<T>* leftNode = node->left;
    node->left = leftNode->right;
    leftNode->right = node;

    node->height = max(height(node->left), height(node->right)) + 1;
    leftNode->height = max(height(leftNode->left), node->height) + 1;

    return leftNode;
}

template <typename T>
TreeNode<T>* AVLTree<T>::rightRightRotation(TreeNode<T>* &node) {
    TreeNode<T>* rightNode = node->right;
    node->right = rightNode->left;
    rightNode->left = node;

    node->height = max(height(node->left), height(node->right)) + 1;
    rightNode->height = max(node->height, height(rightNode->right)) + 1;

    return rightNode;
}

template <typename T>
TreeNode<T>* AVLTree<T>::leftRightRotation(TreeNode<T>* &node) {
    node->left = rightRightRotation(node->left);
    return leftLeftRotation(node);
}

template <typename T>
TreeNode<T>* AVLTree<T>::rightLeftRotation(TreeNode<T>* &node) {
    node->right = leftLeftRotation(node->right);
    return rightRightRotation(node);
}