DS4

Problem A

向空AVL树插入 3,1,4,6,9,2,5,7

在插入9前，与BST相同
图示：

按BST插入方法插入9
图示：

此时，0003节点左右子树高度差超过1，执行旋转树操作。
图示：

后续插入同BST
图示：

Problem B

单旋转代码：

PTNode rightRotate(PTNode y) {
    PTNode x = y->LChild;
    PTNode xr = x->RChild;

    x->RChild = y;
    y->LChild = xr;

    x->height = height(x);
    y->height = height(y);

    return x;
}

PTNode leftRotate(PTNode y) {
    PTNode x = y->RChild;
    PTNode xl = x->LChild;

    x->LChild = y;
    y->RChild = xl;

    x->height = height(x);
    y->height = height(y);

    return x;
}

双旋转基本操作与单旋转相同，具体实现代码为：

//LL
if (bf > 1 && data < node->LChild->data) {
    return rightRotate(node);
}
//RR
if (bf < -1 && data > node->RChild->data) {
    return leftRotate(node);
}
//LR
if (bf > 1 && data > node->LChild->data) {
    node->LChild = leftRotate(node->LChild);
    return rightRotate(node);
}
//RL
if (bf < -1 && data < node->RChild->data) {
    node->RChild = rightRotate(node->RChild);
    return leftRotate(node);
}

A/B整体实现代码

#include <stdio.h>
#include <stdlib.h>

typedef struct Node *PTNode;
typedef struct Node {
    int data;
    PTNode LChild;
    PTNode RChild;
    int height;
} Node;

int max(int a, int b) {
    return a > b ? a : b;
}

int height(Node *root) { //可能有问题️
    if (root == NULL) {
        return 0;
    }
    return 1 + max(height(root->LChild), height(root->RChild));
}

PTNode newNode(int data) {
    PTNode newNode = (PTNode) malloc(sizeof(Node));
    newNode->data = data;
    newNode->LChild = newNode->RChild = NULL;
    newNode->height = 0;
    return newNode;
}

int getBalanceFactor(PTNode root) {
    if (root == NULL) {
        return 0;
    }
    return height(root->LChild) - height(root->RChild);
}

PTNode rightRotate(PTNode y) {
    PTNode x = y->LChild;
    PTNode xr = x->RChild;

    x->RChild = y;
    y->LChild = xr;

    x->height = height(x);
    y->height = height(y);

    return x;
}

PTNode leftRotate(PTNode y) {
    PTNode x = y->RChild;
    PTNode xl = x->LChild;

    x->LChild = y;
    y->RChild = xl;

    x->height = height(x);
    y->height = height(y);

    return x;
}

PTNode insert(PTNode node, int data) {
    if (node == NULL) {
        return newNode(data);
    }
    if (data < node->data) {
        node->LChild = insert(node->LChild, data);
    }
    else if (data > node->data) {
        node->RChild = insert(node->RChild, data);
    }
    else {
        return node; //值已经存在
    }

    node->height = height(node);

    int bf = getBalanceFactor(node);

    //LL
    if (bf > 1 && data < node->LChild->data) {
        return rightRotate(node);
    }

    //RR
    if (bf < -1 && data > node->RChild->data) {
        return leftRotate(node);
    }

    //LR
    if (bf > 1 && data > node->LChild->data) {
        node->LChild = leftRotate(node->LChild);
        return rightRotate(node);
    }

    //RL
    if (bf < -1 && data < node->RChild->data) {
        node->RChild = rightRotate(node->RChild);
        return leftRotate(node);
    }

    return node;
}

void inOrder(PTNode root) {
    if (root != NULL) {
        inOrder(root->LChild);
        printf("%d,", root->data);
        inOrder(root->RChild);
    }
}

void preOrder(PTNode root) {
    if (root != NULL) {
        printf("%d,", root->data);
        preOrder(root->LChild);
        preOrder(root->RChild);
    }
}

int main() {
    int n;
    scanf("%d,", &n);
    PTNode root = newNode(n);
    while (scanf("%d,", &n) == 1) {
        root = insert(root, n);
    }
    preOrder(root);
    return 0;
}