首页 > 代码库 > 伸展树&红黑树&AVL树总结

伸展树&红黑树&AVL树总结

2024-08-21 20:53:36   225人阅读

最近学习了这3种树，感觉其实有很多相同的地方吧，首先是最重要的旋转操作，3种树都有

技术分享 
AvlTree left_left(AvlTree k1)
{
    //if(height(k1->left)-height(k1->right)<2)return k1;
    AvlTree k2 = k1->left;
    k1->left = k2->right;
    k2->right = k1;
   k1->Height = max(height(k1->left),height(k1->right))+1;
    k2->Height = max(height(k2->left),height(k2->right))+1;
    return k2;
}

//右右旋转

AvlTree right_right(AvlTree k1)
{
    //if(height(k1->right)-height(k1->left)<2)return k1;
    AvlTree k2 = k1->right;
    k1->right = k2->left;
    k2->left = k1;
    k1->Height = max(height(k1->left),height(k1->right))+1;
    k2->Height = max(height(k2->left),height(k2->right))+1;
    return k2;
}
View Code

（我的左旋是指自身是左而父亲也是左时的旋转而不是向左旋转，和网上的大部分不同）功能也都差不多一样，AVL树是直接用来保持树的高度平衡性，而在伸展树中，其实旋转操作与把要查找的节点移到头结点并没有太大关系（我的写法中，还有另一种旋转方法则有直接关系），伸展树在一次查询中最坏的情况可能是O(n)，而旋转操作可以保证连续n次旋转复杂度为nlg(n)，也就是说在伸展树中，旋转也是来改变树的深度的，在红黑树中，旋转就要再添加些代码了，因为红黑树中还有父亲节点，所以要添加旋转的时候父亲节点发生的改变，而旋转操作主要是为了满足到叶子节点的黑色节点数相同这一性质，其实也就是在减小树的深度。

技术分享 
template <class T>
red_black_node<T>* red_black_tree<T>::RotateRight(red_black_node<T>* node,red_black_node<T>* root)
{

    red_black_node<T>* tem = node->right;
    node->right = tem->left;
    tem->left = node;
    tem->parent = node->parent;
    node->parent = tem;
    if(node->right!=NULL)
    node->right->parent = node;


    if(tem->parent==NULL)
    {
        root = tem;
    }
    else
    {
        if(tem->parent->key > tem->key)
        {
            tem->parent->left = tem;
            //red_black_tree<T>::Travel_it(root);
        }
        else
        {
            tem->parent->right = tem;
        }

    }
    return root;
}

//左旋函数，并未改变颜色
template <class T>
red_black_node<T>* red_black_tree<T>::RotateLeft(red_black_node<T>* node,red_black_node<T>* root)
{
    red_black_node<T>* tem = node->left;
    node->left = tem->right;
    tem->right = node;
    tem->parent = node->parent;
    node->parent = tem;
    if(node->left!=NULL)
    node->left->parent = node;

    if(tem->parent==NULL)
    {
        root = tem;
    }
    else
    {
        if(tem->key > tem->parent->key)
        {
            tem->parent->right = tem;
        }
        else
        {
            tem->parent->left = tem;
        }
    }
    return root;
}
View Code

另外就是在删除时AVL树和红黑树都是寻找删除节点的右儿子的最左孩子来替代（当然是存在的情况下），然后进行树的重新平衡，AVL树是旋转然后节点高度的更新，红黑树则是旋转，颜色的重绘。相比而言伸展树的删除就方便多了，因为它用到了它在将寻找节点移到根节点时的特殊操作，可以很轻松的实现删除操作。

还有想说的就是关于AVL树与红黑树的性能比较，说句实话我还未没感觉到红黑树比AVL树的操作优化多少，只是红黑树确实在删除和插入时可能会快些。我只明显感觉到红黑树比AVL树复杂太多太多。。。可能是我太菜的缘故吧。。。

伸展树&红黑树&AVL树总结


联系
我们