AVL 树：从概念到手撕实现的核心详解

AVL 树的概念

AVL 树是二叉平衡搜索树中的一种，还有比如像红黑树也算二叉平衡搜索树的一种。 跟二叉搜索树的区别：二叉搜索树极端场景下会退化成类似链表的结构，AVL 树则不会。

概念：

一棵 AVL 树或者是空树，或者是具有以下性质的二叉搜索树：

1. 它的左右子树都是 AVL 树

2. 左右子树高度之差（简称平衡因子）的绝对值不超过 1（-1/0/1）

–每个节点都有它的平衡因子哈

AVL 树增删查改的时间复杂度都是 O(log n)–n 是元素个数

AVL 树的模拟实现

AVL 树和红黑树考手撕考的不多–但是会让你说整体模拟实现的思想或者考 eg: 旋转的手撕

template<class K, class V>
struct AVLTreeNode {
    pair<K, V> _kv;
    AVLTreeNode<K, V>* _left;
    AVLTreeNode<K, V>* _right;
    AVLTreeNode<K, V>* _parent;
    int _bf; // 平衡因子 也就是 balance factor

    AVLTreeNode(const pair<K, V>& kv) : _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0) {}
};

template<class K, class V>
class AVLTree {
    typedef AVLTreeNode<K, V> Node;
public:
    bool Insert(const pair<K, V>& kv) {
        if (_root == nullptr) {
            _root = new Node(kv);
            return true;
        }
        Node* parent = nullptr;
        Node* cur = _root;
         (cur) {
             (cur->_kv.first < kv.first) {
                parent = cur;
                cur = cur->_right;
            }   (cur->_kv.first > kv.first) {
                parent = cur;
                cur = cur->_left;
            }  {
                 ;
            }
        }
        cur =  (kv);
         (parent->_kv.first < kv.first) {
            parent->_right = cur;
        }  {
            parent->_left = cur;
        }
        cur->_parent = parent; 

        
         (parent) {
             (cur == parent->_left) {
                parent->_bf--;
            }  {
                parent->_bf++;
            }
             (parent->_bf == ) { 
                ;
            }   (parent->_bf ==  || parent->_bf == ) { 
                cur = parent;
                parent = parent->_parent;
            }   (parent->_bf ==  || parent->_bf == ) { 
                 (parent->_bf ==  || cur->bf == ) {
                    (parent);
                }   (parent->_bf ==  && cur->_bf == ) {
                    (parent);
                }   (parent->_bf ==  && cur->_bf == ) {
                    (parent);
                }   (parent->_bf ==  && cur->_bf == ) {
                    (parent);
                }
                ;
            }  {
                (); 
            }
        }
         ;
    }

    
    {
        Node* cur = parent->_right;
        Node* curleft = cur->_left;
        parent->_right = curleft;
         (curleft) 
            curleft->_parent = parent;
        cur->_left = parent; 
        Node* ppnode = parent->_parent;
        parent->_parent = cur; 
        
         (parent == _root) {
            _root = cur;
            cur->_parent = ;
        }  {
             (ppnode->_left == parent) {
                ppnode->_left = cur;
            }  {
                ppnode->_right = cur;
            }
            cur->_parent = ppnode;
        }
        parent->_bf = cur->_bf = ; 
    }

    
    {
        ++_rotateCount;
        Node* cur = parent->_left;
        Node* curright = cur->_right;
        parent->_left = curright;
         (curright) curright->_parent = parent;
        Node* ppnode = parent->_parent;
        cur->_right = parent;
        parent->_parent = cur;
         (ppnode == ) {
            _root = cur;
            cur->_parent = ;
        }  {
             (ppnode->_left == parent) {
                ppnode->_left = cur;
            }  {
                ppnode->_right = cur;
            }
            cur->_parent = ppnode;
        }
        parent->_bf = cur->_bf = ;
    }

    
    {
        Node* cur = parent->_right;
        Node* curleft = cur->_left;
         bf = curleft->_bf;
        (parent->_right);
        (parent);
         (bf == ) {
            cur->_bf = ;
            curleft->_bf = ;
            parent->_bf = ;
        }   (bf == ) {
            cur->_bf = ;
            curleft->_bf = ;
            parent->_bf = ;
        }   (bf == ) {
            cur->_bf = ;
            curleft->_bf = ;
            parent->_bf = ;
        }  {
            ();
        }
    }

    
    {
        Node* cur = parent->_left;
        Node* curright = cur->_right;
         bf = curright->_bf;
        (parent->_left);
        (parent);
         (bf == ) {
            parent->_bf = ;
            cur->_bf = ;
            curright->_bf = ;
        } 
          (bf == ) {
            parent->_bf = ;
            cur->_bf = ;
            curright->_bf = ;
        }   (bf == ) {
            parent->_bf = ;
            cur->_bf = ;
            curright->_bf = ;
        }
    }

:
    Node* _root = ;
};