AVL树和伸展树-二叉树-数据结构与算法

迈不过友情╰ 2022-02-18 19:41 194阅读 0赞

1.  **AVL树(高度平衡树)**  
    AVL树是高度平衡的二叉树。它的特点是：树中任何节点的两个子树的高度最大差别为1  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5NDc2NzU2NzY_size_16_color_FFFFFF_t_70]  
    结构体定义:

class AVLTreeNode{
        public:
            T key;                // 关键字(键值)
            int height;         // 高度
            AVLTreeNode *left;    // 左孩子
            AVLTreeNode *right;    // 右孩子
            AVLTreeNode(T value, AVLTreeNode *l, AVLTreeNode *r):
                key(value), height(0),left(l),right(r) {}
    };

增加和删除可能要通过一次或多次树旋转来重新平衡这个树。  
**特点**：  
1．本身是一颗二叉查找树  
2. 带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。  
AVL树，本质上是带了平衡功能的二叉查找树

**AVL树的作用**：  
对于一般的二叉查找树，其期望高度（即一颗平衡树时）为log2n，其各操作的时间复杂度（O(log2n)）同时也由此决定。但是，在某些极端的情况下（如插入的序列是有序时），二叉查找树将会退化成近似链或链。此时，其操作的时间复杂度将退化成线性的，即O(n)。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5NDc2NzU2NzY_size_16_color_FFFFFF_t_70 1]  
由上图可知，同样的结点，由于插入的方式不同导致树的高度也有所不同。特别是在带插入节点个数很多且正序的情况下，会导致二叉树的高度是N,而二叉查找树的高度始终为log2n。高度越小，对树的一些基本操作的时间复杂度就会越小。

**2.伸展树(Splay Tree)**  
伸展树是一种特殊的二叉查找树，它还具备一个特点：当某个结点被访问时，伸展树会通过旋转使该节点成为树根。这样的好处是，下次要访问该节点时，能够迅速的访问该节点。

class SplayTreeNode{
        public:
            T key;                // 关键字(键值)
            SplayTreeNode *left;    // 左孩子
            SplayTreeNode *right;    // 右孩子
            SplayTreeNode():left(NULL),right(NULL) {}
            SplayTreeNode(T value, SplayTreeNode *l, SplayTreeNode *r):
                key(value), left(l),right(r) {}
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5NDc2NzU2NzY_size_16_color_FFFFFF_t_70]: /images/20220218/1994ebbb9f54443d8d520c2a3c8be955.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5NDc2NzU2NzY_size_16_color_FFFFFF_t_70 1]: /images/20220218/385c985d4335407abf50b45da8e16e40.png