高级数据结构_平衡搜索树

发表于2022-03-13更新于2025-11-04阅读次数

内容

AVL - 平衡搜索树
单旋转
双旋转

平衡搜索树

在计算机科学中，AVL树（以发明者Adelson-Velsky和Landis 命名）是一种自平衡-二叉搜索树(BST)。在AVL树中，任何节点的两个子树的高度最多相差1；如果在任何时候它们的差异超过1，则会进行重新平衡以恢复此属性。在平均情况和最坏情况下，查找、插入和删除都需要 $O(\log n)$ 时间，其中 $n$ 是操作之前树中的节点数。插入和删除可能需要通过一个或多个树旋转来重新平衡树。

AVL树以其两位苏联发明家Georgy Adelson-Velsky和Evgenii Landis的名字命名;

AVL树经常与红黑树进行比较，因为它们都支持相同的操作集并且采用 $O(\log n)$ 基本操作的时间。对于查找密集型应用程序，AVL树比红黑树更快，因为它们更严格地平衡。

类C实现方式

节点结构

可以看到, 相比于二叉搜索树只多出一个balance因子, 这个平衡因子将带来什么魔力呢?

typedef int KeyType;
typedef struct AVLNode
{
    struct AVLNode* leftchild;
    struct AVLNode* parent;
    struct AVLNode* rightchild;
	KeyType key;
    int balance;	//-1,0,1
}AVLNode, *AVLTree;

旋转

如果在一棵平衡的二叉搜索树中插入一个新节点，造成了不平衡。此时必须调整树的结构，使之平衡化。

平衡化旋转有两类：

单旋转（左旋和右旋）
双旋转（左平衡和右平衡）

每插入一个新节点时，AVL树中相关节点的平衡状态会发生改变。因此，在插入一个新节点后，需要从插入位置沿通向根的路径回溯，检查各结点的平衡因子（左、右子树的高度差）。
- 如果在某一节点发现高度不平衡，停止回溯。
- 从发生不平衡的节点起，沿刚才回溯的路径取直接下两层的节点。
- 如果这三个节点处于一条直线上，则采用单旋转进行平衡化。单旋转可按其方向分为左单旋转和右单旋转，其中一个是另一个的镜像，其方向与不平衡的形状相关。
- 如果这三个节点处于一条折线上，则采用双旋转进行平衡化。双旋转分为先左后右和先右后左两类。

单旋转

要达到平衡需要的旋转操作	例子	原因
右单旋转(顺时针)		左孩子的左子树高 - 左左旋转
左单旋转(逆时针)		右孩子的右子树高 - 右右旋转

左单旋转(右右旋转) - 逆时针

此图为例，插入100后，56的平衡因子为2，78为1，89为1。则我们需要以78为轴，将56进行左单旋转。

左单旋转会是什么效果？先看简单的情况

以此为启发，进行旋转

再来看一个与代码步骤有关的图例

newroot指针指向ptr的右子树（轴）
ptr的右孩子指针指向newroot的左子树（承）
newroot的左孩子指针指向ptr（揽）

以下为最基本的三步走：

void RotateLeft(AVLTree& tree, AVLNode* ptr)
{
	AVLNode* newroot = ptr->rightchild;	  //1:以ptr右子树为轴
	ptr->rightchild = newroot->leftchild; //2:ptr的右指针承接newroot的左孩子
	newroot->leftchild = ptr;             //3:newroot的左指针包揽ptr为首的子树，揽为已有
}

在这三步中，每一步的后面都要做相应的对parent的维护

newroot的父指针指向ptr的父节点（ptr的父节点代替了newroot的父）
若newroot有左孩子，则左孩子的父指针指向ptr的节点
ptr的父指针指向newroot

void RotateLeft(AVLTree& tree, AVLNode* ptr)
{
	AVLNode* newroot = ptr->rightchild;		//1.1:
    newroot->parent = ptr->parent			//1.2:

	ptr->rightchild = newroot->leftchild;	//2.1:ptr右指针承接newroot左孩
    if(newroot->left != nullptr)newroot->leftchild->parent = ptr;//2.2:
	
    newroot->leftchild = ptr;				//3.1:newroot左指针包揽ptr子树
    ptr->parent = newroot;					//3.2
}

在最后一步，处理ptr的parent指针之前，还要处理ptr的父节点的某一孩子指针指向问题，原本是指向50的(即ptr)，但70(newroot)包揽了50(ptr)的地位，则原本50(ptr)的父节点的一个孩子指针就要指向70(newroot)，至于是左孩子指针还是右孩子指针，需要根据是否和ptr地址是否相等判断。

void RotateLeft(AVLTree& tree, AVLNode* ptr)
{
	AVLNode* newroot = ptr->rightchild;		//1.1:
    newroot->parent = ptr->parent;			//1.2:

	ptr->rightchild = newroot->leftchild;	//2.1:ptr右指针承接newroot左孩
    if(newroot->left != nullptr)newroot->leftchild->parent = ptr;//2.2:
	
    newroot->leftchild = ptr;				//3.1:newroot左指针包揽ptr子树
    
    //??? : 此处是否需要判空
    if(ptr->parent->leftchild == ptr)ptr->parent->leftchild = newroot;
    else ptr->parent->rightchild = newroot;	//4:
    
    ptr->parent = newroot;					//3.2:
}

代码还没完，还要处理根节点的变化

void RotateLeft(AVLTree& tree, AVLNode* ptr)
{
	AVLNode* newroot = ptr->rightchild;		//1.1:
    newroot->parent = ptr->parent;			//1.2:

	ptr->rightchild = newroot->leftchild;	//2.1:ptr右指针承接newroot左孩
    if(newroot->left != nullptr)newroot->leftchild->parent = ptr;//2.2:
	
    newroot->leftchild = ptr;				//3.1:newroot左指针包揽ptr子树
    
    if(ptr == tree)tree = newroot;			//4:如果ptr正好是根，则newroot替代root
    else									//5:若ptr不是根，则处理其父节点的左右孩子指针
    {	//此处不用判空，既然ptr不是根则ptr->parent一定不为空！
        if(ptr->parent->leftchild == ptr)ptr->parent->leftchild = newroot;
        else ptr->parent->rightchild = newroot;	
    }

    ptr->parent = newroot;					//3.2:
}

双旋转

旋转方向	例子	原因
左右双旋转		左孩子的右子树高
右左双旋转		右孩子的左子树高

左右旋转 - 先左旋后右旋

先以左孩子节点为根节点, 左孩子节点的右孩子节点为轴, 进行左单旋转;

再, 以父节点为根节点, 左孩子节点为轴, 进行右单旋转;

Insert

在向一棵本来是高度平衡 $(balance = 0,1,-1)$ 的AVL树中插入一个新节点和在BST树一样，区别是如果树中某个节点的平衡因子 $|balance| > 1$ ，则出现了不平衡，需要做平衡化处理，使得树中各节点重新平衡化。

AVLNode * Buynode(KeyType kx)
{
    AVLNode * s = (AVLNode*)malloc(sizeof(AVLNode));
    if(nullptr == s) exit(1);
    memset(s, 0, sizeof(AVLNode));
    s->key = kx;
    s->balance = 0;
    return s;
}
bool Insert(AVLNode *& tree, KeyType kx)
{
    if(tree == nullptr)
    {
        tree = MakeRoot(val);
        return true;
    }
    AVLNode * pa = nullptr;
    AVLNode * p = tree;
    while(p != nullptr && p->key != kx)
    {
        pa = p;
        p = kx < p->key ? p->leftchild : p->rightchild;
    }
    if(p != nullptr && p->key == kx) //已存在重复值
        return false;

    p = Buynode(kx);
    
    p->parent = pa;
    
    if(kx < pa->key)
    {
        pa->leftchild = p;
    }
    else
    {
        pa->rightchild = p;
    }
    return true;
}

回溯平衡

对于AVL树来说, 单纯的Insert是不够的, 还需要依靠四个函数 - 左旋/右旋/左右旋转/右左旋转, 来达到对树结构的平衡化;

需要考虑的一个关键点: 回溯的终止条件是什么? 即for循环终止判断语句;

void PassBalance(AVLNode &tree, AVLNode * ptr)
{
    AVLNode * pa = p->parent;
    for(; pa != nullptr; )
    {
        if(pa->leftchild == p) //p在pa的左边
        switch(pa->balance)
        {
            case 0: //本来平衡, 插到左, -1
                pa->balance = -1;     break;
            case 1: //本来右1, 插到左, 0
                pa->balance = 0;      break;
            case -1://本来左1, 插到左, 需要平衡
                LeftBalance(tree, pa);break;
        }
        else //p在pa的右边
        switch(pa->balance)
        {
            case 0: //本来平衡, 插到右, 1
                pa->balance = 1;      break;
            case -1://本来左1, 插到右, 平衡
                pa->balance = 0;      break;
            case 1: //本来右1, 插到右, 需要平衡
                RightBalance(tree, pa);break;
        }
        
        p = pa;
        pa = p->parent;
    }
}

还可以进一步做优化: 循环不一定要一直继续 - 有可能节点在插入之后, 整个树的高度没有发生变化, 此时无需进行全部的回溯;

void PassBalance(AVLNode &tree, AVLNode * ptr)
{
    AVLNode * pa = p->parent;
    bool taller = true;
    for(; pa != nullptr && taller; )
    {
        if(pa->leftchild == p) //p在pa的左边
        switch(pa->balance)
        {
            case 0: //本来平衡, 插到左, -1
                pa->balance = -1;     break;
            case 1: //本来右1, 插到左, 0, 因此树高无变化, 无需回溯
                pa->balance = 0;
                taller = false;       break;
            case -1://本来左1, 插到左, 需要平衡, 进行旋转后, 树高也平衡了, 无需回溯
                LeftBalance(tree, pa);
                taller = false;       break;
        }
        else //p在pa的右边
        switch(pa->balance)
        {
            case 0: //本来平衡, 插到右, 1
                pa->balance = 1;      break;
            case -1://本来左1, 插到右, 平衡, 因此树高无变化, 无需回溯
                pa->balance = 0;
                taller = false;       break;
            case 1: //本来右1, 插到右, 需要平衡, 进行旋转后, 树高也平衡了, 无需回溯
                RightBalance(tree, pa);
                taller = false;       break;
        }
        
        p = pa;
        pa = p->parent;
    }
}

这样一来, 此循环最多进入两次即可退出, 因为, 不管你把pa->balance调为-1或1, 下次循环中的pa->balance肯定不会是上次的值, 而某一case中, 除了第一种情况taller为true, 其他两种均为false;

左平衡

void LeftBalance(AVLTree & tree, AVLNode * ptr)
{
    AVLNode * leftsub = ptr->leftchild;
    AVLNode * rightsub = nullptr;
    switch(leftsub->balance)
    {
        case 0: /* left balance, but maybe a fault */ break;
        case -1:/* 左直线, 需要右单旋转 */
            RotateLeft(tree, ptr);
            ptr->balance = 0;
            leftsub->balance = 0;                     break;
        case 1: /* 左右折线, 需要双旋转 */
            rightsub = leftsub->rightchild;
            switch(rightsub->balance)
            {
                case -1:/* 在根的左孩子的右孩子的左边插入 */
                    leftsub->balance = 0;
                    ptr->balance = 1;                 break;
                case 1: /* 在根的左孩子的右孩子的右边插入 */
                    leftsub->balance = -1;
                    ptr->balance = 0;                 break;
                case 0: /* */
                    leftsub->balance = 0;
                    ptr->balance = 0;                 break;
            }
            /* 先以根的左孩子为根节点, 以其右孩子为轴, 进行左单旋转 */
            RotateLeft(tree, leftsub);
            /* 再以根(ptr)作为根节点, 以其左孩子为轴, 进行右单旋转 */
            RotateRight(tree, ptr);
            rightsub->balance = 0;
            break;//case 1, end
    }
}

Delete

如果被删结点x最多只有一个孩子，那么问题比较简单。如果被删结点x有两个孩子，首先搜索在中序次序下的直接前驱y（同样可以找直接后继）。再把结点y的内容传送给结点x，现在问题转移到删除结点y。
- 把结点y当作被删结点x。
将结点x从树中删去。因为结点x最多有一个孩子，我们可以简单地把x的双亲结点中原来指向x的指针改指到这个孩子结点；如果结点x没有孩子，x双亲结点的相应指针置为NULL。然后将原来以结点x为根的子树的高度减1，
必须沿x通向根的路径反向追踪高度的变化对路径上各个结点的影响。
用一个布尔变量shorter来指明子树的高度是否被缩短。在每个结点上要做的操作取决于shorter的值和结点的balance，有时还要依赖子女的balance。
布尔变量shorter的值初始化为True。然后对于从x的双亲到根的路径上的各个结点p，在shorter保持为True时执行下面的操作。如果shorter变成False，算法终止。
case 1：当前节点p的balance为0。
- 如果它的左子树或右子树被缩短，则它的balance改为1或-1，同时shorter置为false。
case 2：节点p的balance不为0，且较高的子树被缩短，则p的balance改为0，同时shorter置为true。

Cpp_值类型_引用折叠

发表于2022-03-12更新于2025-11-04阅读次数

`static_cast`

int a不能直接用int && e接收。

int main()
{
    int a = 12;
    int && e = a;  // error
    e = 13;
}

int a强转为int&&时，可以用int && e接收，修改e，会连带修改a。

int main()
{
    int a = 12;
    int && e = static_cast<int&&>(a);
    e = 13;     // e = 13; a = 13
}

int a强转为int时，可以用int && e接收，修改e，不会连带修改a。

为什么？
强转为值类型时，相当于拷贝了一份临时对象（另创空间）。

int main()
{
    int a = 12;
    int && e = static_cast<int>(a);
    e = 13;     // e = 13; a = 12
}

移动构造（拷贝右值构造）

参数不能加const，因为语义上，是要把other对象的资源移动过来，是需要改动other的。
经验上，要把移动构造函数声明为noexcept，因为涉及到资源的移动的动作过程中即使出现了异常也无法处理、修复。

class Test
{
public:
    Test(int val) : _val { new int(val) }
    {}
    // 以非右值对象拷贝构造
    Test(Test const & other)
    {
        _val = new int(*other._val);
    }
    // 以右值对象移动构造
    Test(Test && other) noexcept
    {
        _val = other._val;
        other._val = nullptr;
    }
    ~Test()
    {
        if(_val)
        {
            delete _val;
            _val = nullptr;
        }
    }
    void set_value(int v)
    {
        if(_val)
        {
            *_val = v;
        }
    }
private:
    int * _val;
};

测试移动构造：以下代码未能走到移动构造函数的断点——编译器优化了

编译器优化了：Test test{ get_test() }。没走移动构造，而是直接把Test test{5}在main函数中的test上构造了。
这个现象叫做：具名的返回值优化。

Test get_test(void)
{
    Test test{5};
    return test;
}
int main()
{
    Test test{ get_test() };
}

如果不优化的话，会是以下的情况：一共创建了3个对象，有2个是中间无用的临时对象

Test get_test(void)
{
    Test test{ 5 };         // create a new test object
    return test;            // generated a temporary test object
}
int main()
{
    Test test{ get_test() };// create a new object by calling copy-constructor
}

为了能看到移动构造函数的断点：不通过函数返回的临时值，通过自己手动创建一个test，来强转为右值引用，从而移动构造新的test。

int main()
{
    Test test2{ static_cast<Test&&>(test) };
}

赋值重载

以非右值对象赋值

Test & operator=(Test const& other)
{
    if(&other == this) return *this;
    if(_val != nullptr)
    {
        delete _val;
        _val = nullptr;
    }
    if(other._val != nullptr) 
    {
        _val = new int { *other._val };
    }
    return *this;
}

以右值对象赋值

Test & operator=(Test && other)
{
    if(&other == this) return *this;
    if(_val != nullptr)
    {
        delete _val;
        _val = nullptr;
    }
    _val = other._val;
    return *this;
}

`static_cast`三种值类型的行为

没有变量接收时的行为：

int main()
{
    Test test{ 2 };

    static_cast<Test>(test);
    static_cast<Test&>(test);
    static_cast<Test&&>(test);
    
}

通过断点调试，发现，强转为普通值类型<Test>时，而且是在不进行其他操作的情况下，仍会调用一次普通拷贝构造函数。其他两句不会进行拷贝。

接下来研究其他两个语句——在有变量接收时的行为。

强转为普通值类型

以普通值类型接收时，会拷贝，调用的是普通拷贝构造；
不可以左值引用接收普通值类型。
以右值引用接收时，也会拷贝，调用的是普通拷贝构造。

int main()
{
    Test test{ 2 };

    Test    test11 = static_cast<Test>(test);
    Test &  test12 = static_cast<Test>(test);
    Test && test13 = static_cast<Test>(test);
}

强转为左值

以普通值类型接收时，会拷贝，调用的是普通拷贝构造；
以左值引用接收时，不会拷贝，是高效的用法。
不可以右值引用接收左值。

int main()
{
    Test test{ 2 };

    Test    test21 = static_cast<Test&>(test);
    Test &  test22 = static_cast<Test&>(test);
  //Test && test23 = static_cast<Test&>(test);  // error
}

强转为右值

以普通值类型接收时，会拷贝，调用右值构造（如果右值构造较好地处理了资源的移动，则较高效。若没有明确写右值构造，则仍会进行普通拷贝，则降低了效率）；
不可以左值引用接收右值。
以右值引用接收时，不会拷贝，是高效的用法。

int main()
{
    Test test{ 2 };

    Test    test31 = static_cast<Test&&>(test);  // decide on Move Constructor
  //Test &  test32 = static_cast<Test&&>(test);  // error
    Test && test33 = static_cast<Test&&>(test);
}

其中，以“右值引用类型”接收“强转为右值的对象”（或者std::move后的对象），这个行为其实是对“右值对象”的生命期的延展。如果通过右值引用来修改对象，那么对象源值也会修改。这才是右值引用最本原的功能。

int main()
{
    Test test{ 2 };
    // test    : _val : 2

    Test && test33 = static_cast<Test&&>(test);
    test33.set_value(4);
    // test.33 : _val : 4
    // test    : _val : 4
}

总结

Modern Cpp引入了值类型的细分，不是让你装逼的，也不是为了给程序员增加痛苦的，而是为了让各种类型都有它最好的归宿：

左值交给左值引用（不会有任何其他多余的操作，高效转手）
右值交给右值引用（不会有任何其他多余的操作，高效转手）
右值交给普通类型（调用右值构造，如果右值构造较好地处理了资源的移动，则较高效）
对于前两种来说，只要引用类型匹配，则无需程序员费心，便可提高效率。
而对于程序员来说，最要注意的就是第三种情况，即右值构造函数需要程序员来明确写出，指明资源转移的动作，决定了右值交给普通类型的效率。如果没有写右值构造函数，则仍会进行普通拷贝，则降低了效率。

`forwarding_reference`

形式上和右值引用一样，但性质、行为是未定义的。

传入模板的类型，是不确定的，需要接收后另外推断。
传给auto的类型，亦如此，接收后需要推断。

困扰：

template<typename T>
void test(T const & t)
{
    
}

int main()
{
    const int ca = 10;
    int a = 11;
    test(ca);
    test(a);
    test(9);
}

问题：字面常量无法传递给T & t。
于是加了T const & t，可以传递了。

但是，导致，如果传的是const int变量，则T后加const与否对应的行为不一样。
总结起来就是：

T后无const时
1. 传入非常左值，T对应的类型是const int，t对应的类型是const int &
2. 传入常左值，T对应的类型是int，t对应的类型是int &
3. 常性在传入前后始终是对应的，很好。
4. 但是：不能接收右值。
5. 总结：虽然不怎么通用，但是起码没有很乱。
T后有const时
1. 能接收右值了，很好。
2. 但是，无论传入的是常左值、非常左值、右值，最后，T对应的类型都会是int，t对应的类型都会是const int &。
3. 那么就导致：如果传入的是非常左值，由于t被污染成了const int，导致t无法修改。

全新的解决方案

使用T &&这个形式改进T const & 。虽然样子看起来是右值引用，但它不是，因为T是不确定类型，而它又常用在参数转发中，所以起了新名叫”转发引用 (Forwarding Reference)“（也有人叫Universal Reference）。根据接收的值类型的不同，T也会跟着变化。

包容度和T const &一样，既能接收常左值、非常左值，又能接收右值。
最终达到的效果却比T const &更好：

常左值，T对应的类型是const int &，t对应的类型是const int &
左值，T对应的类型是int &，t对应的类型是int &
右值，T对应的类型是int，t对应的类型是int &&

template<typename T>
void test(T && t)
{
    
}

int main()
{
    int a = 11;
    test(a);
    test(9);
}

引用折叠

Reference Collapsed

模板参数中的`&&`

虽然经过传入，变成了对应的引用，在函数中也可以修改t的值（const类型除外），但是其实没啥意义，这个转发引用的意义就是在于让你转发的，不是修改值。

template <typename T>
void test(T && t)
{
    t = 8;
}
int main()
{
    int a = 11;
    test(a);    // 可以把本身改为8。
    test(9);    // 9还是9，不变。   t = 8修改的是副本
}

auto后的`&&`

int main()
{
    int a = 11;
  //int  && ri = a;   // error  右值引用无法接收左值
  //auto &  la = 9;   // error  左值引用无法接收右值
    auto && ra = a;   // ok     ra : int &  
    auto && ra2= 9;   // ok     ra2: int && ra2
}

move

把传入的值类型转换为右值。

template<typename T>
T&& mymove(T && t)
{
    return static_cast<T&&>(t);
}

1 2	T: int & + && -> t: int & T: int + && -> t: int &&

现在的问题是：传入不同值类型的变量后，行为不一致。若是左值，则最终只能强转为int &；若为右值，则最终只能强转为int &&。现在我们想要追求：无论左右值，最终都转为左值。

那么可以考虑用Traits技术，消除左右值的区别、影响，统一。

template<typename T>
class RemoveRefTraits
{
public:
    using TYPE = T;
};

template<typename T>
class RemoveRefTraits<T&>
{
public:
    using TYPE = T;
};

template<typename T>
class RemoveRefTraits<T&&>
{
public:
    using TYPE = T;
};

template <typename T>
using RemRef_t = RemoveRefTraits<T>::TYPE;

template<typename T>
RemRef_t<T>&& mymove(T && t)
{
    return static_cast<RemRef_t<T>&&>(t);
}

完美转发

Perfect Forwarding

内容