本文共 10441 字，大约阅读时间需要 34 分钟。

1.二叉搜索树（Binary Sort Tree）

二叉搜索树，又称之为二叉排序树（二叉查找树），它或许是一棵空树，或许是具有以下性质的二叉树：

• 若他的左子树不为空，则左子树上所有节点的值都小于根节点的值
• 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
• 它的左右子树也分别是二叉搜索树
  
  二叉搜索树的这种特性，使得我们在此二叉树上查找某个值就很方便了，从根节点开始，若要寻找的值小于根节点的值，则在左子树上去找，反之则去右子树查找，知道找到与值相同的节点。插入节点也是一样的道理，从根节点出发，所要插入的值，若小于根节点则去左子树寻找该节点所对应的位置，反之去右子树寻找，直到找到该节点合适的位置。
  
  至于删除操作以及其他操作，相对比较麻烦，我会另写一篇二叉搜索树的详解，这里我们只了解二叉搜索树的基本性质即可。

2.二叉平衡搜索树（AVL）

前面提到了二叉搜索树，我们知道，二叉搜索树的特性便于我们进行查找插入删除等一系列操作，其时间复杂度为O（logn），但是，如果遇见最差的情况，比如以下这棵树：

这棵树，说是树，其实它已经退化成链表了，但从概念上来看，它仍是一棵二叉搜索树，只要我们按照逐次增大，如1、2、3、4、5、6的顺序构造一棵二叉搜索树，则形如上图。那么插入的时间复杂度就变成了O(n)，导致这种糟糕的情况原因是因为这棵树极其不平衡，右树的重量远大于左树，因此我们提出了叫平衡二叉搜索树的结构，又称之为AVL树，是因为平衡二叉搜索树的发明者为Adel’son-Vel’skii 和Landis二人。 平衡二叉搜索树，它能保持二叉树的高度平衡，尽量降低二叉树的高度，减少树的平均查找长度。 AVL树的性质：

• 左子树与右子树高度之差的绝对值不超过1
• 树的每个左子树和右子树都是AVL树
• 每一个节点都有一个平衡因子（balance factor），任一节点的平衡因子是-1、0、1（每一个节点的平衡因子 = 右子树高度 - 左子树高度）

做到了这点，这棵树看起来就比较平衡了，那么如何生成一棵AVL树呢？算法相对来说复杂，随着新节点的加入，树自动调整自身结构，达到新的平衡状态，这就是我们想要的AVL树。我们先要分析，为什么树会失衡？是由于插入了一个新的元素

在AVL树中，插入一个节点是什么样的过程呢？

总结如下： 插入节点代码实现如下：

template 
   
    bool AVLTree
    
     ::AVLInsert(K key, V val){    //1.根节点为空，直接插入    if (_root == NULL)    {        _root = new Node(key, val);        return true;    }    //2.根节点不为空    else    {        Node* cur = _root;        Node* parent =NULL;        //a)找到要插入节点的位置        while (cur)        {            parent = cur;            if (cur->_key > key)                cur = cur->_left;            else if (cur->_key < key)                cur = cur->_right;            else                return false;   //不允许出现重复元素的节点        }        //b)插入新节点        cur = new Node(key, val);        if (parent->_key>key)        {            parent->_left = cur;            cur->_parent = parent;        }        else        {            parent->_right = cur;            cur->_parent = parent;        }        //c)插入完成后，调整平衡因子        while (parent)        {            if (cur == parent->_left)//插入节点在左子树父节点bf--，反之++            parent->_bf--;        else            parent->_bf++;            //1)插入新节点后，parent->bf==0;说明高度没变，平衡，返回            if (parent->_bf == 0)                break;            //2)插入节点后parent->_bf==-1||parent->_bf==1;说明子树高度改变，则继续向上调整            else if (parent->_bf == -1 || parent->_bf == 1)            {                cur = parent;                parent = parent->_parent;            }            //3)插入节点后parent->_bf==-2||parent->_bf==2；说明已经不平衡，需要旋转            else            {                if (parent->_bf == 2)                {                    if (cur->_bf == 1)                        RotateL(parent);                    else// (cur->_bf == -1)                        RotateRL(parent);                }                else//parent->_bf == -2                {                    if (cur->_bf == -1)                        RotateR(parent);                    else// (cur->_bf == 1)                        RotateLR(parent);                }                break;            }        }//end while (parent)        return true;    }}
    
   

当树不平衡时，我们需要做出旋转调整，有四种调整方法。

以下是节点调平的四种情况。

AVL树的自平衡操作——旋转

AVL树的旋转总体来说分为四种情况：

1. 左单旋
2. 右单旋
3. 左右双旋
4. 右左双旋

接下来，我们通过图解来认识这四种节点调平方式

1.左单旋（ 逆时针旋转）： 代码实现如下：

template 
   
    void AVLTree
    
     ::RotateL(Node* parent){    Node*subR = parent->_right;    Node*subRL = subR->_left;    Node*pParent = parent->_parent;    parent->_right = subRL;    if (subRL)        subRL->_parent = parent;    subR->_left = parent;    parent->_parent = subR;    if (parent == _root)    {        _root = subR;        _root->_parent = NULL;    }    else    {        if (pParent->_left = parent)            pParent->_left = subR;        else            pParent->_right = subR;        subR->_parent = pParent;    }    parent->_bf = subR->_bf = 0;}
    
   

2.右单旋（顺时针旋转）：

代码实现如下：

template 
   
    void AVLTree
    
     ::RotateR(Node* parent){    Node* subL = parent->_left;    Node* subLR = subL->_right;    Node* ppNode = parent->_parent;    parent->_left = subLR;    if (subLR)        subLR->_parent = parent;    subL->_right = parent;    parent->_parent = subL;    if (_root == parent)    {        _root = subL;        subL->_parent = NULL;    }    else    {        if (ppNode->_right == parent)        {            ppNode->_right = subL;        }        else        {            ppNode->_left = subL;        }        subL->_parent = ppNode;    }    subL->_bf = parent->_bf = 0;}
    
   

3.左右双旋：

代码实现如下：

template 
   
    void AVLTree
    
     ::RotateLR(Node* parent){    Node* subL = parent->_left;    Node* subLR = subL->_right;    int bf = subLR->_bf;    RotateL(parent->_left);    RotateR(parent);    if (bf == 0)    {        subLR->_bf = subL->_bf = parent->_bf = 0;    }    else if (bf == 1)    {        parent->_bf = 0;        subL->_bf = -1;        subLR->_bf = 0;    }    else if (bf == -1)    {        parent->_bf = 1;        subL->_bf = 0;        subLR->_bf = 0;    }    else    {        assert(false);    }}
    
   

4.右左双旋：

代码实现如下：

template 
   
    void AVLTree
    
     ::RotateRL(Node* parent){    Node* subR = parent->_right;    Node* subRL = subR->_left;    int bf = subRL->_bf;    RotateR(parent->_right);    RotateL(parent);    if (bf == 0)    {        subRL->_bf = subR->_bf = parent->_bf = 0;    }    else if (bf == 1)    {        subR->_bf = 0;        parent->_bf = -1;        subRL->_bf = 0;    }    else if (bf == -1)    {        parent->_bf = 0;        subR->_bf = 1;        subRL->_bf = 0;    }    else    {        assert(false);    }}
    
   

我们知道AVL树的每一个节点都有一个平衡因子，那么在AVL树插入节点时，其自平衡操作保证了AVL树始终保持平衡状态，但是在每一次插入节点时，都可能会导致节点平衡因子的改变，因此，当插入节点时，我们应当注意平衡因子的更新，这直接关系到之后判断插入节点后的数是否仍为AVL树。

平衡因子更新原则：

——平衡因子与节点本身无关，只与其左右子树相关

1. 新增节点bf恒为1
2. 右子树结点增加，父亲bf ++
   

3. 左子树结点增加，父亲bf - -

   
   4.若插入节点，更新平衡因子之后

   a）父亲节点bf==0：高度没变，结束更新，平衡，满足条件，返回

   
   b）父亲bf==1 （或者bf== -1），子树高度改变，继续往上更新
   
   c）父亲bf==2 （或者bf== -2），子树不再是平衡树，旋转，变成平衡
   

AVL树实现代码整体如下：

AVLTree.h

#pragma once//AVLTree树节点定义template 
   
    struct AVLTreeNode{    K _key;    V _val;    AVLTreeNode
    
     * _left;    AVLTreeNode
     
      * _right;    AVLTreeNode
      
       * _parent;    int _bf;    //平衡因子    AVLTreeNode(const K& key, const V& val)        :_key(key)        , _val(val)        , _left(NULL)        , _right(NULL)        , _parent(NULL)        , _bf(0)    {}};//AVLTree类的定义template 
       
        class AVLTree{    typedef AVLTreeNode
        
          Node;public: AVLTree() //构造函数 :_root(NULL) {} bool AVLInsert(K key,V val); //插入节点 void RotateL(Node* parent); // 左单旋 void RotateR(Node* parent); // 右单旋 void RotateLR(Node* parent); // 左右双旋 void RotateRL(Node* parent); // 右左双旋 bool _IsBalance(Node* root, int& height) //判断是否平衡 { if (root == NULL) { height = 0; return true; } int leftHeight = 0; int rightHeight = 0; if (_IsBalance(root->_left, leftHeight) && _IsBalance(root->_right, rightHeight)) { if (rightHeight - leftHeight != root->_bf) { cout << "平衡因子异常" << root->_key << endl; return false; } height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; return abs(leftHeight - rightHeight) < 2; } else { return false; } } bool IsBalance() { int height = 0; return _IsBalance(_root, height); } void _InOrder(Node* root) { if (root == NULL) { return; } _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); } void InOrder() { _InOrder(_root); cout << endl; }private: Node* _root;};template 
         
          bool AVLTree
          
           ::AVLInsert(K key, V val){ //1.根节点为空，直接插入 if (_root == NULL) { _root = new Node(key, val); return true; } //2.根节点不为空 else { Node* cur = _root; Node* parent =NULL; //a)找到要插入节点的位置 while (cur) { parent = cur; if (cur->_key > key) cur = cur->_left; else if (cur->_key < key) cur = cur->_right; else return false; //不允许出现重复元素的节点 } //b)插入新节点 cur = new Node(key, val); if (parent->_key>key) { parent->_left = cur; cur->_parent = parent; } else { parent->_right = cur; cur->_parent = parent; } //c)插入完成后，调整平衡因子 while (parent) { if (cur == parent->_left)//插入节点在左子树父节点bf--，反之++ parent->_bf--; else parent->_bf++; //1)插入新节点后，parent->bf==0;说明高度没变，平衡，返回 if (parent->_bf == 0) break; //2)插入节点后parent->_bf==-1||parent->_bf==1;说明子树高度改变，则继续向上调整 else if (parent->_bf == -1 || parent->_bf == 1) { cur = parent; parent = parent->_parent; } //3)插入节点后parent->_bf==-2||parent->_bf==2；说明已经不平衡，需要旋转 else { if (parent->_bf == 2) { if (cur->_bf == 1) RotateL(parent); else// (cur->_bf == -1) RotateRL(parent); } else//parent->_bf == -2 { if (cur->_bf == -1) RotateR(parent); else// (cur->_bf == 1) RotateLR(parent); } break; } }//end while (parent) return true; }}template 
           
            void AVLTree
            
             ::RotateL(Node* parent){ Node*subR = parent->_right; Node*subRL = subR->_left; Node*pParent = parent->_parent; parent->_right = subRL; if (subRL) subRL->_parent = parent; subR->_left = parent; parent->_parent = subR; if (parent == _root) { _root = subR; _root->_parent = NULL; } else { if (pParent->_left = parent) pParent->_left = subR; else pParent->_right = subR; subR->_parent = pParent; } parent->_bf = subR->_bf = 0;}template 
             
              void AVLTree
              
               ::RotateR(Node* parent){ Node* subL = parent->_left; Node* subLR = subL->_right; Node* ppNode = parent->_parent; parent->_left = subLR; if (subLR) subLR->_parent = parent; subL->_right = parent; parent->_parent = subL; if (_root == parent) { _root = subL; subL->_parent = NULL; } else { if (ppNode->_right == parent) { ppNode->_right = subL; } else { ppNode->_left = subL; } subL->_parent = ppNode; } subL->_bf = parent->_bf = 0;}template 
               
                void AVLTree
                
                 ::RotateLR(Node* parent){ Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; RotateL(parent->_left); RotateR(parent); if (bf == 0) { subLR->_bf = subL->_bf = parent->_bf = 0; } else if (bf == 1) { parent->_bf = 0; subL->_bf = -1; subLR->_bf = 0; } else if (bf == -1) { parent->_bf = 1; subL->_bf = 0; subLR->_bf = 0; } else { assert(false); }}template 
                 
                  void AVLTree
                  
                   ::RotateRL(Node* parent){ Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; RotateR(parent->_right); RotateL(parent); if (bf == 0) { subRL->_bf = subR->_bf = parent->_bf = 0; } else if (bf == 1) { subR->_bf = 0; parent->_bf = -1; subRL->_bf = 0; } else if (bf == -1) { parent->_bf = 0; subR->_bf = 1; subRL->_bf = 0; } else { assert(false); }}void TestAVLtree() //测试代码{ int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; //{16, 3, 7, 11, 9, 26, 18, 14, 15}; AVLTree
                   
                     t; for (size_t i = 0; i < sizeof(a) / sizeof(int); ++i) { t.AVLInsert(a[i], i); cout << a[i] << ":" << t.IsBalance() << endl; } t.InOrder(); cout << t.IsBalance() << endl;}
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

AVLTree.cpp

#include 
   
    using namespace std;#include 
    
     #include "AVLTree.h"int main(){    TestAVLtree();    return 0;}