分类 数据结构 下的文章

B站讲解:
https://www.bilibili.com/video/av18735440?from=search&seid=10453551569484697640


C[i]代表 子树的叶子结点的权值之和// 这里以求和举例

如图可以知道

C[1]=A[1];

C[2]=A[1]+A[2];

C[3]=A[3];

C[4]=A[1]+A[2]+A[3]+A[4];

C[5]=A[5];

C[6]=A[5]+A[6];

C[7]=A[7];

C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];

下面观察如下图

将C[]数组的结点序号转化为二进制

1=(001) C[1]=A[1];

2=(010) C[2]=A[1]+A[2];

3=(011) C[3]=A[3];

4=(100) C[4]=A[1]+A[2]+A[3]+A[4];

5=(101) C[5]=A[5];

6=(110) C[6]=A[5]+A[6];

7=(111) C[7]=A[7];

8=(1000) C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];

对照式子可以发现 C[i]=A[i-2^k+1]+A[i-2^k+2]+......A[i]; (k为i的二进制中从最低位到高位连续零的长度)例如i=8时,k=3;

可以自行带入验证;

现在引入lowbit(x)

lowbit(x) 其实就是取出x的最低位1 换言之 lowbit(x)=2^k k的含义与上面相同 理解一下

下面说代码

int lowbit(int t)
{
return t&(-t);
}
//-t 代表t的负数 计算机中负数使用对应的正数的补码来表示
//例如 :
// t=6(0110) 此时 k=1
//-t=-6=(1001+1)=(1010)
// t&(-t)=(0010)=2=2^1
C[i]=A[i-2^k+1]+A[i-2^k+2]+......A[i];

C[i]=A[i-lowbit(i)+1]+A[i-lowbit(i)+2]+......A[i];

*分割线

区间查询

ok 下面利用C[i]数组,求A数组中前i项的和

举个例子 i=7;

sum[7]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7] ; 前i项和

C[4]=A[1]+A[2]+A[3]+A[4]; C[6]=A[5]+A[6]; C[7]=A[7];

可以推出: sum[7]=C[4]+C[6]+C[7];

序号写为二进制: sum[(111)]=C[(100)]+C[(110)]+C[(111)];

再举个例子 i=5

sum[5]=A[1]+A[2]+A[3]+A[4]+A[5] ; 前i项和

C[4]=A[1]+A[2]+A[3]+A[4]; C[5]=A[5];

可以推出: sum[5]=C[4]+C[5];

序号写为二进制: sum[(101)]=C[(100)]+C[(101)];

细细观察二进制 树状数组追其根本就是二进制的应用

结合代码

int getsum(int x)
{
int ans=0;
for(int i=x;i>0;i-=lowbit(i))
ans+=C[i];
return ans;
}
对于i=7 进行演示

                              7(111)          ans+=C[7]

lowbit(7)=001 7-lowbit(7)=6(110) ans+=C[6]

lowbit(6)=010 6-lowbit(6)=4(100) ans+=C[4]

lowbit(4)=100 4-lowbit(4)=0(000)

对于i=5 进行演示

                              5(101)           ans+=C[5]

lowbit(5)=001 5-lowbit(5)=4(100) ans+=C[4]

lowbit(4)=100 4-lowbit(4)=0(000)

*分割线

单点更新

当我们修改A[]数组中的某一个值时 应当如何更新C[]数组呢?

回想一下 区间查询的过程,再看一下上文中列出的图

结合代码分析

void add(int x,int y)
{
for(int i=x;i<=n;i+=lowbit(i))
tree[i]+=y;
}
//可以发现 更新过程是查询过程的逆过程
//由叶子结点向上更新C[]数组

参考文档:https://yq.aliyun.com/articles/50382



#include "stdafx.h"
#include <iostream>
using namespace std;

//节点用struct
template<int Size>
struct TrieNode {
public:
    bool terminable;
    int count;//子节点个数
    TrieNode* child[Size];//每个节点又有相同数目的子节点
    TrieNode():count(0),terminable(false) {
        memset(child, 0, sizeof(child));
    }
    ~TrieNode() {
        //delete [] child;
    }
};
//原理就是 字符通过index哈希函数返回一个id 然后这个id就是child的下标
template<int Size,class Index>//Size字符表大小 Index哈希函数
class Trie {
private:
    Index index;
    TrieNode<Size> root;
    template <class Iterator>
    void Insert(Iterator begin, Iterator end) {
        TrieNode<Size>* cur = &root;
        for (;begin != end; ++begin) {
            //如果此节点没有被新建
            if (cur->child[index[*begin]] == nullptr) {
                cur->child[index[*begin]] = new TrieNode<Size>;
                ++cur->count; //子节点数量+1
            }
            cur = cur->child[index[*begin]];
        }
        //是否可截断 因为有可能是tree 和 tre 在同一个节点 所以e要设置可截断
        cur->terminable = true;
    }
    //查询
    template <class Iterator>
    bool Find(Iterator begin, Iterator end) {
        TrieNode<Size>* cur = &root;
        for (; begin != end;++begin) {
            if (!cur->child[index[*begin]]) {//此节点不存在 返回假
                return false;
            }
            cur = cur->child[index[*begin]];
        }
        return cur->terminable;//是否可被截断
    }
    //删除节点
    template <class Iterator>
    bool DeleteNode(Iterator begin, Iterator end, TrieNode<Size> &cur, bool &result) {
        if (begin == end) {//当相等时结束递归
            result = cur.terminable;//如果当前节点可以作为终止符 则为真
            cur.terminable = false;
            return cur.count == 0;//如果节点为树叶 通知其父节点删除它
        }
        //无法匹配时候删除为假
        if (cur.child[index[*begin]] == 0) {
            return result = false;
        }
        else if (DeleteNode((++begin)--,end,*(cur.child[index[*begin]]),result)) {
            delete cur.child[index[*begin]];
            cur.child[index[*begin]] = 0;//子节点数-1
            //删完了
            if (--cur.count == 0 && cur.terminable == false) {
                return true;
            }
        }
        return false;
    }
    template <class Iterator>
    bool Delete(Iterator begin, Iterator end) {
        bool result;
        DeleteNode(begin,end,root,result);
        return result;
    }
    template<class Functor>
    void VisitNode(TrieNode<Size>* cur,Functor &execute) {
        execute(cur);
        for (int i = 0; i < Size; i++)
        {
            execute(cur);
            if (cur->child[i] == 0) {
                continue;
            }
            else {
                VisitNode(cur->child[i], execute);
            }
        }
    }
public:
    Trie(Index i = Index()):index(i) {
    }
    void Insert(const char* str) {
        Insert(str,str+strlen(str));
    }
    bool Find(const char* str) {
        return Find(str,str+strlen(str));
    }
    bool Delete(const char* str) {
        return Delete(str,str+strlen(str));
    }
    template <class Functor>
    void Traverse(Functor &execute = Functor())
    {
        VisitNode(root,execute);
    }
};

class IndexClass
{
public:
    int operator[](const char key)
    {
        return key % 26;
    }
};

int main()
{
    Trie<26, IndexClass> t;
    t.Insert("tree");
    t.Insert("tea");
    t.Insert("A");
    t.Insert("ABC");

    if (t.Find("tree"))
        cout << "find tree" << endl;
    else
        cout << "not find tree" << endl;

    if (t.Find("tre"))
        cout << "find tre" << endl;
    else
        cout << "not find tre" << endl;

    if (t.Delete("tree"))
        cout << "delete tree" << endl;
    else
        cout << "not find tree" << endl;

    if (t.Find("tree"))
        cout << "find tree" << endl;
    else
        cout << "not find tree" << endl;

    return 0;
}

参考文章:https://www.cnblogs.com/skywang12345/p/3624291.html
https://www.cnblogs.com/v-July-v/archive/2011/03/29/2002183.html

// RBTree.cpp: 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <iterator>
#include <algorithm> 
#include <vector>
using namespace std;
enum {
    Red,
    Black
};

template <typename T> class RBTree;
template <class T>
class RBTreeNode {
private:
    friend class RBTree<T>;
    RBTreeNode(){}
public:
    RBTreeNode * left;
    RBTreeNode* right;
    RBTreeNode* parent;
    T key;
    int color;
    RBTreeNode(T key) :left(nullptr), right(nullptr), parent(nullptr), key(key), color(Red) {

    }
    ~RBTreeNode() {

    }
};

template <class T>
class RBTree {
private:
    static RBTreeNode<T> *nil;
    RBTreeNode<T>* root;
    
public:
    RBTree():root(nil) {
        root->parent = nil;
        root->left = nil;
        root->right = nil;
        root->color = Black;
    }
    /*RB-INSERT(T, z)
    1  y ← nil[T]                 // y 始终指向 x 的父结点。
    2  x ← root[T]              // x 指向当前树的根结点,
    3  while x ≠ nil[T]
    4      do y ← x
    5         if key[z] < key[x]           //向左,向右..
    6            then x ← left[x]
    7            else x ← right[x]   //为了找到合适的插入点,x探路跟踪路径,直到x成为NIL 为止。
    8  p[z] ← y         //y置为 插入结点z 的父结点。
    9  if y = nil[T]
    10     then root[T] ← z
    11     else if key[z] < key[y]
    12             then left[y] ← z
    13             else right[y] ← z     //此 8-13行,置z 相关的指针。
    14  left[z] ← nil[T]
    15  right[z] ← nil[T]            //设为空,
    16  color[z] ← RED             //将新插入的结点z作为红色
    17  RB-INSERT-FIXUP(T, z)
    */
    //因为将z着为红色,可能会违反某一红黑性质,
    //所以需要调用下面的RB-INSERT-FIXUP(T, z)来保持红黑性质。
    bool Insert(T key) {
        RBTreeNode<T>* insertPoint = nil;
        RBTreeNode<T>* index = root;
        while (index != nil) {
            insertPoint = index;
            if (key < index->key) {
                index = index->left;
            }
            else if (key > index->key) {
                index = index->right;
            }
            else {
                return false;
            }
        }
        RBTreeNode<T>* insertNode = new RBTreeNode<T>(key);
        if (insertPoint == nil) { //空树
            root = insertNode;
            root->parent = insertPoint;
        }
        else {//如果不是空树则判断大小 插入左才是右
            if (key < insertPoint->key) {
                insertPoint->left = insertNode;
            }
            else {
                insertPoint->right = insertNode;
            }
            insertNode->parent = insertPoint;
        }
        insertNode->left = nil;
        insertNode->right = nil;
        InsertFixUp(insertNode);
    }
    RBTreeNode<T>* find(T key) {
        RBTreeNode<T>* index = root;
        while (index != nil) {
            if (key < index->key) {
                index = index->left;
            }
            else if (key > index->key) {
                index = index->right;
            }
            else {
                break;
            }
        }
        return index;
    }
    //3种插入情况,都在下面的伪代码中(未涉及到所有全部的插入情况)。
    /*
    RB-INSERT-FIXUP(T, z)
    1 while color[p[z]] = RED
    2     do if p[z] = left[p[p[z]]]
    3           then y ← right[p[p[z]]]
    4                if color[y] = RED
    5                   then color[p[z]] ← BLACK                    ? Case 1
    6                        color[y] ← BLACK                       ? Case 1
    7                        color[p[p[z]]] ← RED                   ? Case 1
    8                        z ← p[p[z]]                            ? Case 1
    9                   else if z = right[p[z]]
    10                           then z ← p[z]                       ? Case 2
    11                                LEFT-ROTATE(T, z)              ? Case 2
    12                           color[p[z]] ← BLACK                 ? Case 3
    13                           color[p[p[z]]] ← RED                ? Case 3
    14                           RIGHT-ROTATE(T, p[p[z]])            ? Case 3
    15           else (same as then clause with "right" and "left" exchanged)
    16 color[root[T]] ← BLACK
    */
    void InsertFixUp(RBTreeNode<T>* node)
    {
        while (node->parent->color == Red)
        {
            //父亲为红节点时才需要调整
            if (node->parent == node->parent->parent->left)   //
            {
                RBTreeNode<T>* uncle = node->parent->parent->right;
                if (uncle != nil && uncle->color == Red)   //插入情况1,z的叔叔y是红色的。
                {
                    node->parent->color = Black;
                    uncle->color = Black;
                    node->parent->parent->color = Red;
                    node = node->parent->parent;
                }
                else if (node == node->parent->right)  //插入情况2:z的叔叔y是黑色的,。
                {
                        node = node->parent;
                        LeftRotate(node);
                }else                 //插入情况3:z的叔叔y是黑色的,但z是左孩子。
                {
                    node->parent->color = Black;
                    node->parent->parent->color = Red;
                    RightRotate(node->parent->parent);
                }
            }
            else //这部分是针对为插入情况1中,z的父亲现在作为祖父的右孩子了的情况,而写的。
                 //15 else (same as then clause with "right" and "left" exchanged)
            {
                RBTreeNode<T>* uncle = node->parent->parent->left;
                if (uncle != nil && uncle->color == Red)
                {//情况1
                    node->parent->color = Black;
                    uncle->color = Black;
                    uncle->parent->color = Red;
                    node = node->parent->parent;
                }
                else if (node == node->parent->left)
                {//情况2
                    node = node->parent;
                    RightRotate(node);     //与上述代码相比,左旋改为右旋
                }
                else
                {//情况3
                    node->parent->color = Black;
                    node->parent->parent->color = Red;
                    LeftRotate(node->parent->parent);   //右旋改为左旋,即可。
                }
            }
        }
        root->color = Black;
    }
    bool LeftRotate(RBTreeNode<T>* node) {
        if (node == nil || node->right == nil) {
            return false;
        }
        RBTreeNode<T>* lower_right = node->right;
        lower_right->parent = node->parent;
        node->right = lower_right->left;
        if (lower_right->left != nil) {
            lower_right->left->parent = node;
        }
        if (node->parent == nil) {
            root = lower_right;
        }
        else {
            if (node == node->parent->left) {
                node->parent->left = lower_right;
            }
            else {
                node->parent->right = lower_right;
            }
        }
        node->parent = lower_right;
        lower_right->left = node;
        return true;
    }
    bool RightRotate(RBTreeNode<T>* node) {
        if (node == nil || node->left == nil) {
            return false;
        }
        RBTreeNode<T>* lower_left = node->left;
        node->left = lower_left->right;
        lower_left->parent = node->parent;
        if (lower_left->right != nil) {
            lower_left->right->parent = node;
        }
        if (node == root) { //如果是root节点
            root = lower_left;
        }
        else {
            //是右分支
            if (node == node->parent->right) {
                node->parent->right = lower_left;
            }
            else {
                node->parent->left = lower_left;
            }
        }
        node->parent = lower_left;
        lower_left->right = node;
        return true;
    }
    /*
    RB-DELETE(T, z)
     1 if left[z] = nil[T] or right[z] = nil[T]
     2    then y ← z
     3    else y ← TREE-SUCCESSOR(z)
     4 if left[y] ≠ nil[T]
     5    then x ← left[y]
     6    else x ← right[y]
     7 p[x] ← p[y]
     8 if p[y] = nil[T]
     9    then root[T] ← x
    10    else if y = left[p[y]]
    11            then left[p[y]] ← x
    12            else right[p[y]] ← x
    13 if y 3≠ z
    14    then key[z] ← key[y]
    15         copy y's satellite data into z
    16 if color[y] = BLACK               //如果y是黑色的,
    17    then RB-DELETE-FIXUP(T, x)   //则调用RB-DELETE-FIXUP(T, x) 
    18 return y              //如果y不是黑色,是红色的,则当y被删除时,红黑性质仍然得以保持。不做操作,返回。
    //因为:1.树种各结点的黑高度都没有变化。2.不存在俩个相邻的红色结点。
    //3.因为入宫y是红色的,就不可能是根。所以,根仍然是黑色的。
    */
    bool Delete(T key) {
        RBTreeNode<T>* deletePoint = find(key);
        if (deletePoint == nil) {
            return false;
        }
        //有左右分支则遍历找一个替代的
        if (deletePoint->left != nil && deletePoint->right != nil) {
            RBTreeNode<T>* successor = InOrderSuccessor(deletePoint);
            deletePoint->key = successor->key;
            deletePoint = successor;
        }
        RBTreeNode<T>* deletePointChild;
        if (deletePoint->left != nil) {
            deletePointChild = deletePoint->left;
        }
        else if (deletePoint->right != nil) {
            deletePointChild = deletePoint->right;
        }
        else {
            deletePointChild = nil;
        }
        deletePointChild->parent = deletePoint->parent; //提高一级
        if (deletePoint->parent == nil) {
            root = deletePointChild;
        }
        else if (deletePoint == deletePoint->parent->right) {
            deletePoint->parent->right = deletePointChild;
        }
        else {
            deletePoint->parent->left = deletePointChild;
        }
        if (deletePoint->color == Black) {
            DeleteFixUp(deletePointChild);
        }
        delete deletePoint;
        return true;
    }
    /*
    RB-DELETE-FIXUP(T, x)
    1 while x ≠ root[T] and color[x] = BLACK
    2     do if x = left[p[x]]
    3           then w ← right[p[x]]
    4                if color[w] = RED
    5                   then color[w] ← BLACK                        ?  Case 1
    6                        color[p[x]] ← RED                       ?  Case 1
    7                        LEFT-ROTATE(T, p[x])                    ?  Case 1
    8                        w ← right[p[x]]                         ?  Case 1
    9                if color[left[w]] = BLACK and color[right[w]] = BLACK
    10                   then color[w] ← RED                          ?  Case 2
    11                        x p[x]                                  ?  Case 2
    12                   else if color[right[w]] = BLACK
    13                           then color[left[w]] ← BLACK          ?  Case 3
    14                                color[w] ← RED                  ?  Case 3
    15                                RIGHT-ROTATE(T, w)              ?  Case 3
    16                                w ← right[p[x]]                 ?  Case 3
    17                         color[w] ← color[p[x]]                 ?  Case 4
    18                         color[p[x]] ← BLACK                    ?  Case 4
    19                         color[right[w]] ← BLACK                ?  Case 4
    20                         LEFT-ROTATE(T, p[x])                   ?  Case 4
    21                         x ← root[T]                            ?  Case 4
    22        else (same as then clause with "right" and "left" exchanged)
    23 color[x] ← BLACK
    */
    void DeleteFixUp(RBTreeNode<T>* x) {
        while (x != root && x->color == Black) {
            //如果x是在左节点
            if (x == x->parent->left) {
                RBTreeNode<T>* w = x->parent->right;
                if (w->color == Red) {
                    //情况1,兄弟是红色,转变为情况2,3,4
                    w->color = Black;
                    x->parent->color = Red;
                    LeftRotate(x->parent);
                    w = x->parent->right;
                }
                if (w->left->color == Black && w->right->color == Black) {
                    //情况2,兄弟是黑色,且两孩子也是黑色,将当前节点和兄弟去一重黑色
                        w->color = Red;
                        x = x->parent;
                }
                else if (w->right->color == Black) {
                    //情况3,兄弟左孩子为红,右孩子为黑,转变为情况4
                    w->left->color = Black;
                    w->color = Red;
                    RightRotate(w);
                    w = x->parent->right;
                }
                else{
                    //情况4,右孩子为黑色,左孩子随意
                    w->color = x->parent->color;
                    x->parent->color = Black;
                    w->right->color = Black;
                    LeftRotate(x->parent);
                    x = root;
                }
            }
            else {
                RBTreeNode<T>* w = x->parent->left;
                if (w->color == Red) {
                    //情况1
                    w->color = Black;
                    x->parent->color = Red;
                    LeftRotate(x->parent);
                    w = x->parent->left;
                }
                if (w->right->color == Black && w->left->color == Black) {
                    //情况2
                    w->color = Red;
                    x = x->parent;
                }
                else if (w->left->color == Black) {
                    //情况3
                    w->right->color = Black;
                    w->color = Red;
                    LeftRotate(w);
                    w = x->parent->left;
                }
                else{
                    //情况4
                    w->color = x->parent->color;
                    x->parent->color = Black;
                    w->left->color = Black;
                    RightRotate(x->parent);
                    x = root;
                }
                
            }
        }
        root->color = Black;
    }
    RBTreeNode<T>* InOrderSuccessor(RBTreeNode<T>* node) {
        if (node == nil) {
            return nullptr;
        }
        RBTreeNode<T>* result = node->right;
        while (result != nil) {
            if (result->left != nil) {
                result = result->left;
            }
            else {
                break;
            }
        }
        if (result == nil) {
            RBTreeNode<T>* index = node->parent;
            result = node;
            while (index != nil && result == index->right) {
                result = index;
                index = index->parent;
            }
            result = index;
        }
        return result;
    }
    void InOrderTraverse(RBTreeNode<T>* node)
    {
        if (node == nil)
        {
            return;
        }
        else
        {
            InOrderTraverse(node->left);
            cout << node->key << endl;
            InOrderTraverse(node->right);
        }
    }
    void InOrderTraverse() {
        InOrderTraverse(root);
    }
};
template <typename T> RBTreeNode<T> *RBTree<T>::nil = new RBTreeNode<T>;
int main() {
    std::cout << "Hello, World!" << std::endl;
    RBTree<int> tree;
    vector<int> v;

    for (int i = 0; i<20; ++i)
    {
        v.push_back(i);
    }
    random_shuffle(v.begin(), v.end());
    copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
    for (int i = 0; i<v.size(); ++i)
    {
        tree.Insert(v[i]);
        cout << "insert:" << v[i] << endl;   //添加结点
    }
    tree.InOrderTraverse();
    for (int i = 0; i<v.size(); ++i)
    {
        cout << "Delete:" << v[i] << endl;
        tree.Delete(v[i]);             //删除结点
        tree.InOrderTraverse();
    }
    cout << endl;
    tree.InOrderTraverse();
    return 0;
    return 0;
}

参考文章:https://www.cnblogs.com/QG-whz/p/5167238.html

#include <iostream>
using namespace std;

template <class T>
class AVLTreeNode{
public:
    T data;
    int height;//gaodu
    AVLTreeNode* left;
    AVLTreeNode* right;
    AVLTreeNode(T data,AVLTreeNode* left,AVLTreeNode* right):data(data),height(0),left(left),right(right)
    {}
};

template <class T>
class AVLTree{
private:
    AVLTreeNode<T>* root = nullptr;
    int depth = 0;
    void PreOrder(AVLTreeNode<T>* node){
        if(node != nullptr){
            cout<<node->data<<endl;
            PreOrder(node->left);
            PreOrder(node->right);
        }
    }
    void InOrder(AVLTreeNode<T>* node){
        if(node != nullptr){
            InOrder(node->left);
            cout<<node->data<<endl;
            InOrder(node->right);
        }
    }
    void PostOrder(AVLTreeNode<T>* node){
        if(node != nullptr){
            PostOrder(node->left);
            PostOrder(node->right);
            cout<<node->data<<endl;
        }
    }
    int GetDepth(AVLTreeNode<T>* node){
        if(node == NULL)
            return 0;
        else{
            int depL = GetDepth(node->left);
            int depR = GetDepth(node->right);
            return (depL > depR) ? depL+1 : depR+1;
        }
    };
    int GetSize(AVLTreeNode<T>* node){
        if(node == NULL)
            return 0;
        else{
            int L = GetSize(node->left);
            int R = GetSize(node->right);
            return 1+R+L;
        }
    }
public:
    AVLTree(){

    };
    ~AVLTree(){
        delete root;
    };
    int height(AVLTreeNode<T>* node){
        if(node != nullptr){
            return node->height;
        }else{
            return 0;
        }
    }
    int height(){
        return root->height;
    }
    int max(int a,int b){
        return a>b ? a: b;
    }
    bool IsEmpty(){
        return root->left == nullptr && root->right== nullptr;
    };
    AVLTreeNode<T>* Remove(T data){
        return Remove(root,data);
    }
    AVLTreeNode<T>* GetRoot(){
        return root;
    };

    AVLTreeNode<T>* Insert(T data){
        return Insert(root,data);
    }

    AVLTreeNode<T>* Search(T data){
        return Search(root,data);
    }
    void destory(){
        destory(root);
    }
    void PreOrder(){
        PreOrder(root);
    }
    void InOrder(){
        InOrder(root);
    }
    void PostOrder(){
        PostOrder(root);
    }
    int GetDepth(){
        return GetDepth(root);
    }
    int GetSize(){
        return GetSize(root);
    }

private:
    //删除 后序遍历
    void destory(AVLTreeNode<T>* pNode){
        if(pNode != nullptr){
            destory(pNode->left);
            destory(pNode->right);
            delete pNode;
            pNode = nullptr;
        }
    }
    AVLTreeNode<T>* Insert(AVLTreeNode<T>* &tree,T data){
        if(tree == nullptr){
            tree = new AVLTreeNode<T>(data, nullptr, nullptr);//如果当前树是空的则插入
            if(tree == nullptr){
                throw "Error:create avltree node failed!";
            }
        }else if(data < tree->data){//如果数比当前的小 则在左边
            tree->left = Insert(tree->left,data);//插入完后判断高度是否需要调整
            if(height(tree->left) - height(tree->right) == 2){
                if(data < tree->left->data){//如果插入的数比左子树小 则左边更长 则为左左 所以要左旋
                    tree = LeftLeftRotation(tree);
                }else{//如果在右边则左右旋
                    tree = LeftRightRototation(tree);
                }
            }
        }else if(data > tree->data){//同理
            tree->right = Insert(tree->right,data);
            if(height(tree->right) - height(tree->left) == 2){
                if(data > tree->right->data){
                    tree = RightRightRotation(tree);
                }else{
                    tree = RightLeftRototation(tree);
                }
            }
        }else{  //key == tree->key)
            cout << "添加失败:不允许添加相同的节点!" << endl;
        }
        tree->height = max(height(tree->left),height(tree->right))+1;//设置高度
        return tree;
    }
    //左旋
    AVLTreeNode<T>* LeftLeftRotation(AVLTreeNode<T>* k2){
        AVLTreeNode<T>* k1;
        k1 = k2->left;
        k2->left = k1->right;
        k1->right = k2;
        k2->height = max(height(k2->left),height(k2->right))+1;
        k1->height = max(height(k1->left),k2->height)+1;
        return k1;
    }
    //右旋
    AVLTreeNode<T>* RightRightRotation(AVLTreeNode<T>* k1){
        AVLTreeNode<T>* k2;
        k2 = k1->right;
        k1->right = k2->left;
        k2->left = k1;
        k1->height = max(height(k1->left),height(k1->right))+1;
        k2->height = max(height(k2->right),k1->height)+1;
        return k2;
    }
    //左右旋
    AVLTreeNode<T>* LeftRightRototation(AVLTreeNode<T>* k3){
        AVLTreeNode<T>* k1;
        k3->left = RightRightRotation(k3->left);
        return LeftLeftRotation(k3);
    }
    //右左旋
    AVLTreeNode<T>* RightLeftRototation(AVLTreeNode<T>* k1){
        k1->right = LeftLeftRotation(k1->right);
        return RightRightRotation(k1);
    }
    //取最大数的节点
    AVLTreeNode<T>* MaxNumNode(AVLTreeNode<T>* node) const{
        if(node != nullptr){
            while(node->right != nullptr){
                node = node->right;
            }
            return node;
        }
        return nullptr;
    }
    //取最小数的节点
    AVLTreeNode<T>* MinNumNode(AVLTreeNode<T>* node) const{
        if(node != nullptr){
            while(node->left != nullptr){
                node = node->left;
            }
            return node;
        }
        return nullptr ;
    }
    //取最小数
    T MinNum() const{
        AVLTreeNode<T>* pResult = MinNumNode(root);
        if(pResult != nullptr){
            return pResult->data;
        }
        return -1;
    }
    //取最大数
    T MaxNum() const{
        AVLTreeNode<T>* pResult = MaxNumNode(root);
        if(pResult != nullptr){
            return pResult->data;
        }
        return -1;
    }
    //查找
    AVLTreeNode<T>* Search(AVLTreeNode<T>* pNode,T data){
        if(pNode == nullptr){
            return nullptr;
        }
        if(pNode->data > data){//如果节点数比查找数大则在左边找
            return Search(pNode->left,data);
        }else if(pNode->data < data){//同理
            return Search(pNode->right,data);
        }else{//pNode->data = data
            return pNode;
        }
    }
    AVLTreeNode<T>* Remove(AVLTreeNode<T>* &tree,T data){
        if(tree == nullptr){
            return nullptr;
        }
        //如果删除的数在左边
        if(data < tree->data){
            tree->left = Remove(tree->left,data);
            //删除完之后 比较高度 如果右边比左边高
            if(height(tree->right) - height(tree->left) == 2){
                AVLTreeNode<T>* r = tree->right;
                //如果左边比右边高 则右左 否则右右
                if(height(r->left) > height(r->right)){
                    tree = RightLeftRototation(tree);
                }else{
                    tree = RightRightRotation(tree);
                }
            }
            //同理
        }else if(data > tree->data){
            tree->right = Remove(tree->right,data);
            if(height(tree->left) - height(tree->right) == 2){
                AVLTreeNode<T>* r = tree->left;
                if(height(r->right) > height(r->left)){
                    tree = LeftRightRototation(tree);
                }else{
                    tree = LeftLeftRotation(tree);
                }
            }
        }else{
            //如果找到删除的 切左子树右子树都存在
            if(tree->left != nullptr && tree->right != nullptr){
                if(height(tree->left) > height(tree->right)){
                    // 如果tree的左子树比右子树高;
                    // 则(01)找出tree的左子树中的最大节点
                    //   (02)将该最大节点的值赋值给tree。
                    //   (03)删除该最大节点。
                    // 这类似于用"tree的左子树中最大节点"做"tree"的替身;
                    // 采用这种方式的好处是:删除"tree的左子树中最大节点"之后,AVL树仍然是平衡的。
                    AVLTreeNode<T>* max = MaxNumNode(tree->left);
                    tree->data = max->data;
                    tree->left = Remove(tree->left,max->data);
                }else{
                    AVLTreeNode<T>* min = MinNumNode(tree->right);
                    tree->data = min->data;
                    tree->right = Remove(tree->right,min->data);
                }
            }else{
                //如果存在左子或者右子 则往上提就完事了
                AVLTreeNode<T>* tmp = tree;
                tree = (tree->left != nullptr) ? tree->left : tree->right;
                delete tmp;
            }
        }
        return tree;
    }

};


int main() {
    AVLTree<int> *bt = new AVLTree<int>;
    for (int i = 0; i < 10; i++)
        bt->Insert(i);
    cout << "树高:" << bt->height() << endl;
    cout << "中序遍历:" << endl;
    bt->InOrder();
    cout << "删除元素10" << endl;
    bt->Remove(10);

    AVLTreeNode<int> *b = bt->Search(10);

    if (b != nullptr)
        cout << b->data;
    else
        cout << "无此元素" << endl;
    return 0;
}

#include <iostream>
using namespace std;

template <class T>
class BinaryTreeNode{
public:
    T data;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
};

template <class T>
class BinaryTree{
private:
    BinaryTreeNode<T>* root;
    int depth = 0;
    void PreOrder(BinaryTreeNode<T>* node){
        if(node != nullptr){
            cout<<node->data<<endl;
            PreOrder(node->left);
            PreOrder(node->right);
        }
    }
    void InOrder(BinaryTreeNode<T>* node){
        if(node != nullptr){
            InOrder(node->left);
            cout<<node->data<<endl;
            InOrder(node->right);
        }
    }
    void PostOrder(BinaryTreeNode<T>* node){
        if(node != nullptr){
            PostOrder(node->left);
            PostOrder(node->right);
            cout<<node->data<<endl;
        }
    }
    int GetDepth(BinaryTreeNode<T>* node){
        if(node == NULL)
            return 0;
        else{
            int depL = GetDepth(node->left);
            int depR = GetDepth(node->right);
            return (depL > depR) ? depL+1 : depR+1;
        }
    };
    int GetSize(BinaryTreeNode<T>* node){
        if(node == NULL)
            return 0;
        else{
            int L = GetSize(node->left);
            int R = GetSize(node->right);
            return 1+R+L;
        }
    }
public:
    BinaryTree(){
        root = new BinaryTreeNode<T>;
    };
    ~BinaryTree(){
        delete root;
    };
    bool IsEmpty(){
        return root->left == nullptr && root->right== nullptr;
    };

    BinaryTreeNode<T>* GetRoot(){
        return root;
    };
    void SetRoot(BinaryTreeNode<T>* node){
        root = node;
    }
    BinaryTreeNode<T>* CreateNode(T data){
        return new BinaryTreeNode<T>(data);
    }
    BinaryTreeNode<T>* Create(){
        T val;
        cin >> val;
        if(val == -1){
            return nullptr;
        }else{
            BinaryTreeNode<T>* current = new BinaryTreeNode<T>;
            current->data = val;
            current->left = Create();
            current->right = Create();
        }
    }
    void PreOrder(){
        PreOrder(root);
    }
    void InOrder(){
        InOrder(root);
    }
    void PostOrder(){
        PostOrder(root);
    }
    int GetDepth(){
        return GetDepth(root);
    }
    int GetSize(){
        return GetSize(root);
    }
};


int main(){
    BinaryTree<int>* bt = new BinaryTree<int>;
    bt->SetRoot(bt->Create());
    bt->PostOrder();
    cout << bt->GetDepth()<<endl;
    cout << bt->GetSize()<<endl;
    return 0;
}