当前位置: 首页>>数据结构与算法>> 阅读正文

数据结构之AVL树

Category: 数据结构与算法 View: 27,052 Author: Dong
, ,

  • 评论 (12)
  • 引用通告 (3)
发表评论 发起引用

  • 1楼nhl jerseys 回复

    Post: 2011-05-12 12:39

    90后的,来学习,顶博主一个

    [回复]

  • 2楼hp 回复

    Post: 2011-12-26 11:33

    Node_t Delete(Type x, Tree t) {
    if(t == NULL) return NULL;
    if(t->data == x) {
    if(t->right == NULL) {
    Node_t temp = t;
    t = t->left;
    free(temp);
    } else {
    Node_t head = t->right;
    while(head->left) {
    head = head->left;
    }
    t->data = head->data; //just copy data
    t->right = Delete(t->data, t->right);
    t->height = Max(Height(t->left), Height(t->right)) + 1;

    有个问题,为什么这里可以直接计算t的高度,不用担心t子树的平衡因子么?因为你下面
    else if(t->data right);
    if(t->right) Rotate(x, t->right);
    } else {
    Delete(x, t->left);
    if(t->left) Rotate(x, t->left);
    都有检查t的平衡性。

    [回复]

    Dong 回复:

    @hp, 这段程序是递归的程序,实际上是自上而下处理的已经考虑了,你自己好好想想。

    [回复]

  • 3楼joy 回复

    Post: 2012-03-13 13:10

    Node_t LeftRotate(Node_t a) {
    b = a->right;
    a->right = b->left;
    b->left = a;
    a->height = Max(Height(a->left), Height(a->right));
    b->height = Max(Height(b->left), Height(b->right));
    return b;
    }
    左旋后,a的父节点的孩子指针应该指向b,而这里没有相应的操作
    其他的旋转函数也存在相似的问题

    [回复]

  • 4楼joy 回复

    Post: 2012-03-13 13:16

    sorry,没往后看就写评论了。。。

    [回复]

  • 5楼asdf 回复

    Post: 2012-04-16 09:12

    Node_t Delete(Type x, Tree t) {
    if(t == NULL) return NULL;
    if(t->data == x) {
    if(t->right == NULL) {
    Node_t temp = t;
    t = t->left;
    free(temp);
    } else {
    Node_t head = t->right;
    while(head->left) {
    head = head->left;
    }
    t->data = head->data; //just copy data
    t->right = Delete(t->data, t->right);
    t->height = Max(Height(t->left), Height(t->right)) + 1;
    }
    return t;
    } else if(t->data right);
    if(t->right) Rotate(x, t->right);
    } else {
    Delete(x, t->left);
    if(t->left) Rotate(x, t->left);
    }
    if(t) Rotate(x, t);
    }

    Rotate(x, t);其中,Rotate函数是没有的,应该是LeftRotate或者RightRotate…

    [回复]

  • 6楼azure 回复

    Post: 2012-05-31 05:00

    insert的效率低 经过的路径都要修改指针。做了很多没用的工作。

    [回复]

  • 7楼willfly 回复

    Post: 2012-09-11 03:13

    int Height(Node_t node) {
    return node->height;
    }应该改为
    int Height(Node_t node) {
    if (node == NULL)
    return -1
    else
    return node->height;
    }

    [回复]

  • 8楼willfly 回复

    Post: 2012-09-11 03:14

    四个rotate函数,计算高度应改为a->height = Max(Height(a->left), Height(a->right)) + 1;
    b->height = Max(Height(b->left), Height(b->right)) + 1;

    [回复]

  • 9楼zhuyf87 回复

    Post: 2012-11-12 14:44

    单旋转函数中,计算高度:
    a->height = Max(Height(a->left), Height(a->right));
    是否需要改为Max(…) + 1?

    [回复]

  • 10楼TT 回复

    Post: 2012-12-16 12:54

    Roate(x,y)函数求指导

    [回复]

    keenbin 回复:

    Node_t Rotate(Type x, Node_t t)
    {
    if (t == NULL)
    {
    return NULL;
    }
    else if (x data)
    {
    if (Height(t->left) – Height(t->right) == 2)
    {
    if (x left->data)
    {
    t = LeftRightRotate(t);
    }
    else
    {
    t = RightRotate(t);
    }
    }
    }
    else
    {
    if (Height(t->right) – Height(t->left) == 2)
    {
    if (x > t->right->data)
    {
    t = RightLeftRotate(t);
    }
    else
    {
    t = LeftRotate(t);
    }
    }
    }
    t->height = Max(Height(t->left), Height(t->right)) + 1;
    return t;
    }

    Node_t Delete(Type x, Tree t)
    {
    if (t == NULL)
    return NULL;
    if (t->data == x)
    {
    if (t->right == NULL)
    {
    Node_t temp = t;
    t = t->left;
    free(temp);
    }
    else
    {
    Node_t head = t->right;
    while (head->left)
    {
    head = head->left;
    }
    t->data = head->data; //just copy data
    t->right = Delete(t->data, t->right);
    t->height = Max(Height(t->left), Height(t->right)) + 1;
    }
    }
    else if (t->data right = Delete(x, t->right);
    if (t->right)
    t->right = Rotate(x, t->right);
    }
    else
    {
    t->left = Delete(x, t->left);
    if (t->left)
    t->left = Rotate(x, t->left);
    }
    if (t)
    t = Rotate(x, t);

    return t;
    }

    Node_t createAVL(int data[], int len)
    {
    Node_t root = NULL;
    ;
    for (int i = 0; i left);
    printf(“%d,\t%d,\t%d\n”, root->data, root->height,
    Height(root->left) – Height(root->right));
    traverseAVL1(root->right);
    }
    }

    [回复]

  • 11楼keenbin 回复

    Post: 2013-03-26 00:58

    看了后补全的代码

    /*
    * AVLTree.cpp
    * AVLTree操作
    * Created on: 2013-3-26
    * Author: keenbin
    */

    #include
    #include
    #include
    #include
    #include
    #include
    using namespace std;
    typedef struct Node* Tree;
    typedef struct Node* Node_t;

    typedef int Type;

    struct Node
    {
    Node_t left;
    Node_t right;
    int height;
    Type data;
    };
    int Height(Node_t node)
    {
    if (node)
    return node->height;
    return 0;
    }

    int Max(int n, int m)
    {
    if (n > m)
    return n;
    return m;
    }

    //右旋
    Node_t RightRotate(Node_t a)
    {
    Node_t b = a->left;
    a->left = b->right;
    b->right = a;
    a->height = Max(Height(a->left), Height(a->right));
    b->height = Max(Height(b->left), Height(b->right));
    return b;
    }
    //左旋
    Node_t LeftRotate(Node_t a)
    {
    Node_t b = a->right;
    a->right = b->left;
    b->left = a;
    a->height = Max(Height(a->left), Height(a->right));
    b->height = Max(Height(b->left), Height(b->right));
    return b;
    }
    //左右旋
    Node_t LeftRightRotate(Node_t a)
    {
    a->left = LeftRotate(a->left);
    return RightRotate(a);
    }
    //右左旋
    Node_t RightLeftRotate(Node_t a)
    {
    a->right = RightRotate(a->right);
    return LeftRotate(a);
    }

    Node_t NewNode(Type t)
    {
    Node_t pn = (Node_t) malloc(sizeof(Node));
    if (!pn)
    return NULL;
    pn->left = pn->right = NULL;
    pn->data = t;
    pn->height = 1;
    return pn;
    }
    //插入节点
    Node_t Insert(Type x, Tree t)
    {
    if (t == NULL)
    {
    t = NewNode(x);
    }
    else if (x data)
    {
    t->left = Insert(x, t->left);
    if (Height(t->left) – Height(t->right) == 2)
    {
    if (x left->data)
    {
    t = RightRotate(t);
    }
    else
    {
    t = LeftRightRotate(t);
    }
    }
    }
    else
    {
    t->right = Insert(x, t->right);
    if (Height(t->right) – Height(t->left) == 2)
    {
    if (x > t->right->data)
    {
    t = LeftRotate(t);
    }
    else
    {
    t = RightLeftRotate(t);
    }
    }
    }
    t->height = Max(Height(t->left), Height(t->right)) + 1;
    return t;
    }

    Node_t Rotate(Type x, Node_t t)
    {
    if (t == NULL)
    {
    return NULL;
    }
    else if (x data)
    {
    if (Height(t->left) – Height(t->right) == 2)
    {
    if (x left->data)
    {
    t = LeftRightRotate(t);
    }
    else
    {
    t = RightRotate(t);
    }
    }
    }
    else
    {
    if (Height(t->right) – Height(t->left) == 2)
    {
    if (x > t->right->data)
    {
    t = RightLeftRotate(t);
    }
    else
    {
    t = LeftRotate(t);
    }
    }
    }
    t->height = Max(Height(t->left), Height(t->right)) + 1;
    return t;
    }

    Node_t Delete(Type x, Tree t)
    {
    if (t == NULL)
    return NULL;
    if (t->data == x)
    {
    if (t->right == NULL)
    {
    Node_t temp = t;
    t = t->left;
    free(temp);
    }
    else
    {
    Node_t head = t->right;
    while (head->left)
    {
    head = head->left;
    }
    t->data = head->data; //just copy data
    t->right = Delete(t->data, t->right);
    t->height = Max(Height(t->left), Height(t->right)) + 1;
    }
    }
    else if (t->data right = Delete(x, t->right);
    if (t->right)
    t->right = Rotate(x, t->right);
    }
    else
    {
    t->left = Delete(x, t->left);
    if (t->left)
    t->left = Rotate(x, t->left);
    }
    if (t)
    t = Rotate(x, t);

    return t;
    }

    Node_t createAVL(int data[], int len)
    {
    Node_t root = NULL;
    ;
    for (int i = 0; i left);
    printf(“%d,\t%d,\t%d\n”, root->data, root->height,
    Height(root->left) – Height(root->right));
    traverseAVL1(root->right);
    }
    }

    void traverseAVL2(Tree root) //先序遍历
    {
    if (root != NULL)
    {
    printf(“%d,\t%d,\t%d\n”, root->data, root->height,
    Height(root->left) – Height(root->right));
    traverseAVL2(root->left);
    traverseAVL2(root->right);
    }
    }
    int main()
    {
    int data[] = { 1, 5, 7, 4, 3, 2, 11, 9, 10 };
    Tree root;
    root = createAVL(data, sizeof(data) / sizeof(data[0]));

    traverseAVL1(root);
    printf(“+++++++++++++++++++++++++++++++++++++++\n”);

    root = Delete(5, root);
    traverseAVL1(root);
    printf(“+++++++++++++++++++++++++++++++++++++++\n”);
    root = Delete(9, root);
    traverseAVL1(root);
    }

    [回复]

    keenbin 回复:

    额,格式直接乱掉了,而且还少了很多行。

    [回复]

    asdf 回复:

    你可以用ubantu pastebin

    [回复]

  • 12楼RHD 回复

    Post: 2015-03-14 05:52

    a->height = Max(Height(a->left), Height(a->right));
    b->height = Max(Height(b->left), Height(b->right));
    左旋右旋这里应该要加1吧

    我们书里没概括这个 博主写的蛮有条理的

    [回复]

发表评论