平衡二叉搜索树的实现

分手后的思念是犯贱 2023-07-21 11:17 1阅读 0赞

### 文章目录 ###

*   *   *  概念介绍
         *  代码实现

### 概念介绍 ###

*  AVL树可以将高度控制在o(logn)以内
 *  平衡因子
    
     *  左孩子树高 - 右孩子树高
     *  AVL就是平衡因子受限的搜索树,其中各个节点的平衡因子的绝对值不超过1
 *  等价二叉搜索树
    
     *  两个二叉搜索树的中序遍历序列相同，则称它们等价；这个平衡算法的依据
 *  重新平衡的方法
    
     *  AVL的insert,remove导致的失衡通过单旋和双旋的方式实现重新平衡
 *  失衡传播
    
     *  AVL树删除节点重新平衡之后,祖先可能失衡，这时候需要由下而上的进行重新平衡操作
 *  `统一平衡算法rotateAt`
    
     *  `不在乎旋转的过程，而是穷举了旋转过后所有的情况；对，就是根据旋转之后的各个节点的位置关系做出来的`
     *  `平衡是3个节点(祖g 父p 子v)和四个子树的关系，而他们组合在一起总是可以实现下面的模型`![模型][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbWluZ2xhdGVseQ_size_16_color_FFFFFF_t_70_pic_center]
 *  zip 顺时针旋转  
    ![zip][]
 *  zap – zip 双旋转  
    ![zap-zip][]
 *  zap  
    ![zap][]
 *  zip – zap  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbWluZ2xhdGVseQ_size_16_color_FFFFFF_t_70_pic_center 1]

### 代码实现 ###

*  AVL树

// 引入搜索二叉树
    #include <BstTree.h>
    
    // 理想平衡条件 (左右孩子的高度一样)
    #define Balanced(x) (stature((x).rc) == stature((x).lc))
    
    // 平衡因子
    #define BalFac(x) (stature((x).lc) - stature((x).rc))
    
    // AVL平衡条件
    #define AvlBalanced(x) (BalFac(x) > -2 && BalFac(x) < 2)
    
    // 找到失衡节点g(x)对应的孩子和孩子的孩子
    template<typename T> BinNodePosi(T) tallerChild(BinNodePosi(T) x) {
        // 取孩子高度最高的那个,一样高的时候取同侧的那个
        if (stature(x->lc) > stature(x->rc)){
            return x->lc;
        }
    
        if (stature(x->lc) < stature(x->rc)) {
            return x->rc;
        }
    
        // 取同侧孩子
        return IsLChild(*x) ? x->lc : x->rc;
    }
    
    // 定义平衡二叉树模板类
    template <typename T> class AVL:public BST {
    public :
        BinNodePosi(T) insert(T const & e); // 插入(重写)
        // 删除(重写)
        bool remove(T const& e);
    };
    
    // 二叉平衡树 插入操作
    template <typename T> BinNodePosi(T) AVL<T>::insert(const T &e) {
        // e存在的话 没有插入的必要
        BinNodePosi(T) x = serach(e);
        if (x) {
            return x;
        }
    
        // 插入新节点
        BinNodePosi(T) new_child = new BinNode<T>(e, _hot);
        _size ++;
    
        // 解决因插入数据而导致的失衡的问题
        BinNodePosi(T) g = _hot;
        for (; g; g= g->parent){
            // 节点失衡
            if (!AvlBalanced(*g)){
                // 失衡节点的孙子节点
                BinNodePosi(T) v = tallerChild(tallerChild(g));
                FromParentTo(*g) = rotateAt(v);
    
                // 此时子树高度复原，g祖先的高度也是会复原, 调整结束
                break;
            } else {
                // 即使未失衡但是高度也可能变化
                updateHeight(g);
            }
        }
    
        return new_child;
    }
    
    // 删除算法
    template <typename T> bool AVL::remove(const T &e) {
        // 如果不存在 则不需要删除
        BinNodePosi(T)& x = search(e);
        if (!x) {
            return false;
        }
    
        // 按照二叉搜索树的规则删除
        removeAt(x, _hot);
        --size;
    
        // 平衡祖先节点
        BinNodePosi(T) g = _hot;
        for (; g ; g = g->parent) {
            // 失衡节点使用3+4平衡算法平衡
            if (!AvlBalanced(g)) {
                BinNodePosi(T) v = tallerChild(tallerChild(g));
    
                // 执行平衡算法，将新子树关联到原父亲;   但是g的位置也要更新成子树根节点
                g = FromParentTo(*g) = rotateAt(v);
    
                // 删除节点会造成祖先节点失衡传播,所以还是需要进行后续的轮询
            }
    
            // 即使未失衡但是高度也可能变化
            updateHeight(g);
        }
    
        return true;
    }

*  二叉搜索树

// 引入二叉树
    #include "BinTree.h"
    
    //定义二叉搜索树模板类
    template<typename T>
    class BST : public BinTree {
    protected:
        // 命中节点的父亲
        BinNodePosi(T)_hot;
    
        // 按照3+4结构连接3个节点和四颗子树
        BinNodePosi(T)connect34(BinNodePosi(T) a, BinNodePosi(T) b, BinNodePosi(T) c, BinNodePosi(T) T0,
                                BinNodePosi(T) T1, BinNodePosi(T) T2, BinNodePosi(T) T3);
    
        // 对父亲祖父做同意旋转调整
        BinNodePosi(T)rotateAt(BinNodePosi(T)x);
    
    public:
        // 基本接口
        // 查找
        virtual BinNodePosi(T)&search(T const &e);
    
        // 插入
        virtual BinNodePosi(T)insert(T const &e);
    
        // 删除
        virtual bool remove(T const &e);
    };
    
    // 二叉搜索树查找
    template<typename T>
    BinNodePosi(T)& BST::search(T const &e) {
        return searchIn(_root, _hot = NULL, e);
    }
    
    // 递归查找
    template <typename T> BinNodePosi(T)& searchIn(BinNodePosi(T)& v, BinNodePosi(T) & hot, T const &e){
        // 递归基
        if (!v || v->data == e) {
            return v;
        }
    
        // 设置父指针
        hot = v;
    
        // 做减法
        v = e > v->data ? v->rc : v->lc;
        return searchIn(v, hot, e);
    }
    
    // 插入操作
    template <typename T> BinNodePosi(T) BST<T>::insert(const T &e) {
        BinNodePosi(T) x = search(e);
        // 如果已经存在 则没有意义
        if (x) {
            return x;
        }
    
        // 创建新节点
        x = new BinNode(e, hot);
    
        // 更新规模
        _size++;
    
        // 更新x祖先高度
        updateHeightAbove(x);
    
        return x;
    }
    
    // 删除算法
    template <typename T> bool BST<T>::remove(const T &e) {
        BinNodePosi(T) x = search(e);
    
        // 目标不存在 则删除失败
        if (!x) {
            return false;
        }
    
        // 实施删除
        removeAt(x, _hot);
    
        // 更新规模
        _size --;
    
        // 更新祖先节点的高度
        updateHeightAbove(_hot);
    
        return true;
    };
    
    // 实际删除操作
    template <typename T> static BinNodePosi(T) removeAt(BinNodePosi(T) &x, BinNodePosi(T) & hot) {
        // 实际被删除的节点
        BinNodePosi(T) w = x;
    
        // 被删除节点的替换者
        BinNodePosi(T) succ = NULL;
    
      // 单分支直接删除
      if (!HasLChild(x)) {
          // *x替换成右子树
          x = succ = x->rc;
      } else if (!HasRChild(x)) {
          // *x替换成其左子树
          x = succ = x->rc;
      } else {
          // 双分支 被删除的是直接后继节点
          w = w->succ();
    
          // 置换x和直接后继之间的数据
          swap(x->data, w->data);
    
          // 直接后继肯定是没有左孩子的
          FromParentTo(w) = succ = w->rc;
    
      }
    
      // 记录实际被删除的孩子的父亲
      hot = w->parent;
    
      // 关联hot和替换者
      if (succ) {
          succ->parent = hot;
      }
    
      // 释放被删除的节点
      release(w->data);
      release(w);
      return succ;
    };
    
    // BST系欸但那旋转变化统一算法, 返回调整之后局部子树根节点的位置
    template <typename T> BinNodePosi(T) BST<T>::rotateAt(BinNodePosi(T) x) {
      // 父亲节点
      BinNodePosi(T) p = x->parent;
    
      // 祖父节点
      BinNodePosi(T) g = p->parent;
    
      if (IsLChild(*p)) { // zip
          if (IsLChild(*v)) { // zip--zip
              return connect34(v,p,g,v->lc, v->rc, p->rc,g->rc)
          } else {
              // zip --zap
            return connect34(p,v,g, p->lc,v->lc, v->rc, g->rc);
          }
      } else {
          if (IsRChild(*v)) {
            return connect34(g, p, v, g->lc, p->lc, v->lc, v->rc);
          } else {
            return connect34(g,v,p, g->lc, v->lc, v->rc, p->rc);
          }
      }
    };
    
    // 按照3+4的接口连接3个节点和4颗子树, 返回局部子树的根节点
    template <typename T> BinNodePosi(T) BST<T>::connect34(BinNode<T> *a, BinNode<T> *b, BinNode<T> *c, BinNode<T> *T0,
                                                           BinNode<T> *T1, BinNode<T> *T2, BinNode<T> *T3) {
        // 设置b,a,c之间关系
        b->lc = a;
        a->parent = b;
        b->rc = c;
        c->parent = b;
    
        // 设置a的左右孩子
        a->lc = T0;
        if (T0) {
            T0->parent = a;
        }
    
        a->rc = T1;
        if (T1) {
            T1->parent = a;
        }
    
        // 设置c的左右孩子
        c->lc = T2;
        if (T2) {
            T2->parent = c;
        }
    
        c->rc = T3;
        if (T3) {
            T3->parent = c;
        }
    
        return b;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbWluZ2xhdGVseQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/05569a1566e1431c802847954d3e69a8.png
[zip]: /images/20230528/fc76be50c4b646a89ecc44e1e687ee9f.png
[zap-zip]: /images/20230528/2050f96cfddb495caa6430b6e13e9293.png
[zap]: /images/20230528/c341cc0f40f54ecb8006f349691aa295.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbWluZ2xhdGVseQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230528/6e8c9bfff6804275a70f31f55a6f66f2.png