AVL树


AVL

  • 平衡二叉搜索树

性质

  • 完美继承二叉搜索树的性质
  • |H(left) - H(right)| <= 1

优点

  • 由于对每个节点的左右子树的树高做了限制,所以整棵树不会退化为一个链表
  • 继承了二叉搜索树的优点
  • 高度平衡的二叉搜索树,查找效率非常高O(log1.68 h) ~ O(log 2 h)

缺点

  • 为了维持高度的平衡,每次插入、删除都要进行树高的调整,比较复杂、耗时。
  • 对于频繁的插入删除操作,使用AVL树代价高

操作

  • LL、LR、RL、RR型条件的不平衡
  • LL与RR型只用进行一次调整
  • 其余需要进行两次调整

结构定义

//结构定义
typedef struct Node {
    int value, h;
    struct Node *left, *right;
}Node;

更新树高

//更新树高
void update_h(Node *root) {
    if (root == NIL) return ;
    root->h = max(root->left->h, root->right->h) + 1;
    return ;
}

左旋

//左旋
Node *left_rotate(Node *root) {
    //printf("\n left rotate : %d\n", root->value);
    Node *p = root->right;
    root->right = p->left;
    p->left = root;
    update_h(root);
    update_h(p);
    return p;
}

右旋

//右旋
Node *right_rotate(Node *root) {
    //printf("\n right rotate : %d\n", root->value);
    Node *p = root->left;
    root->left = p->right;
    p->right = root;

    update_h(root);
    update_h(p);
    return p;
}

完整代码

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


#define max(a, b) (\
    (a) > (b) ? (a) : (b)\
)



//结构定义
typedef struct Node {
    int value, h;
    struct Node *left, *right;
}Node;

Node __NIL;
#define NIL (&__NIL)
__attribute__((constructor))
void init_NIL() {
    NIL->h = 0;
    NIL->value = -1;
    NIL->left = NIL->right = NIL;
}


//结构操作
Node *getNewNode(int target) {
    Node *p = (Node *)malloc(sizeof(Node));
    p->h = 1;
    p->left = p->right = NIL;
    p->value = target;
    return p;
}

void clear(Node *root) {
    if (root == NIL) return ;
    clear(root->left);
    clear(root->right);
    free(root);
    return ;
}

int search(Node *root, int target) {
    if (root == NIL) return 0;
    if (root->value == target) return 1;
    if (root->value > target) {
        return search(root->left, target);
    }
    return search(root->right, target);
}


//更新树高
void update_h(Node *root) {
    if (root == NIL) return ;
    root->h = max(root->left->h, root->right->h) + 1;
    return ;
}

//左旋
Node *left_rotate(Node *root) {
    printf("\n left rotate : %d\n", root->value);
    Node *p = root->right;
    root->right = p->left;
    p->left = root;

    update_h(root);
    update_h(p);
    return p;
}

//右旋
Node *right_rotate(Node *root) {
    printf("\n right rotate : %d\n", root->value);
    Node *p = root->left;
    root->left = p->right;
    p->right = root;

    update_h(root);
    update_h(p);
    return p;
}
const char *maintain_str[] = {"", "LL", "LR", "RL", "RR"};

Node *maintain(Node *root) {
    //判断是否失衡
    if (abs(root->left->h - root->right->h) <= 1) return root;
    
    int maintain_type = 0;
    // 失衡
    if (root->left->h > root->right->h) { //֤左子树高,失衡条件L
        if (root->left->right->h > root->left->left->h) { //LR
            // LR 和 RL 都要旋转两次 
            root->left = left_rotate(root->left); 
            maintain_type = 2;
        } else {
            maintain_type = 1;            
        }
        root = right_rotate(root); 
        
    } else { //右子树高,失衡条件 R 
        
        if (root->right->left->h > root->right->right->h) { 
            root->right = right_rotate(root->right); 
            maintain_type = 3;
        } else {    
            maintain_type = 4;            
        }
        root = left_rotate(root); 
        
    }
    printf("AVL maintain_type : %s\n", maintain_str[maintain_type]);
    return root;
} 

Node *insert(Node *root, int target) {
    if (root == NIL) return getNewNode(target);
    if (root->value == target) return root;
    if (root->value > target) {
        root->left = insert(root->left, target);
    } else {
        root->right = insert(root->right, target);
    }
    update_h(root);
    
    
    
    return maintain(root);
}


Node *get_pre(Node *root) {
    Node *p = root;
    while (p->right != NIL) {
        p = p->right;
    }
    return p;
}

Node *erase(Node *root, int target) {
    if (root == NIL) return NIL;
    if (root->value > target) {
        root->left = erase(root->left, target);
    } else if (root->value < target) {
        root->right = erase(root->right, target);
    } else {
        if (root->left == NIL || root->right == NIL) {
            Node *tmp = (root->left != NIL ? root->left : root->right);
            free(root);
            return tmp;
        } else {
            Node *pre = get_pre(root->left);
            root->value = pre->value;
            root->left = erase(root->left, pre->value); 
        }
    }
    update_h(root);  
     
    return maintain(root);
}

void in_order(Node *root) {
    if (root == NIL) return ;
    in_order(root->left);
    printf("%d ", root->value);
    in_order(root->right);
    return ;
}

void outputTree(Node *root) {
    if (root == NIL) return ;
    printf("(%d(%d) | %d, %d)\n", root->value, root->h, root->left->value, root->right->value);
    outputTree(root->left);
    outputTree(root->right);
    return ;
}


int main() {
    srand(time(NULL));
    Node *root = NIL;
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        int val = rand() % 100;
        printf("\ninsert %d to tree: \n", val);
        root = insert(root, val);
        outputTree(root);
    }
    
    
    while (scanf("%d", &n) != EOF) {
        root = erase(root, n);
        //in_order(root);
        outputTree(root);
    }
    
    clear(root);
    
    return 0;
}

剑指 Offer 26. 树的子结构

输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构, 即 A中有出现和B相同的结构和节点值。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

// bool flag = false;

// bool func1(struct TreeNode *A, struct TreeNode *B) {
//     if (B == NULL) return true;
//     if (A == NULL) return false;
//     if (A->val != B->val) return false;
//     return flag = (func1(A->left, B->left) && func1(A->right, B->right));
// }

// void func(struct TreeNode *A, struct TreeNode *B) {
//     if (A == NULL) return ;
//     if (flag) return ;
//     if (A->val == B->val) {
//         func1(A, B);
//     }
//     func(A->left, B);
//     func(A->right, B);
//     return ;
// }

bool is_match(struct TreeNode *A, struct TreeNode *B) {
    if (B == NULL) return true;
    if (A == NULL) return false;
    if (A->val != B->val) return false;
    return is_match(A->left, B->left) & is_match(A->right, B->right);
}

bool isSubStructure(struct TreeNode* A, struct TreeNode* B) {
    if (B == NULL || A == NULL) return false;
    if (is_match(A, B)) return true;
    return isSubStructure(A->left, B) || isSubStructure(A->right, B);
}

108. 将有序数组转换为二叉搜索树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

// struct TreeNode *func(int *nums, int left, int right) {
    
//     if (left >= right) {
//         return NULL;
//     }
//     int ind = (left + right) >> 1;
//     struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
//     root->val = nums[ind];
//     root->left = func(nums, left, ind);
//     root->right = func(nums, ind + 1, right);
//     return root;
// }

// struct TreeNode* sortedArrayToBST(int* nums, int numsSize){
//     return numsSize == 0 ? NULL : func(nums, 0, numsSize);
// }
#define max(a, b) ((a) > (b) ? (a) : (b))

int getHeight(struct TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    int l = getHeight(root->left);
    int r = getHeight(root->right);
    return max(l, r) + 1;
}

struct TreeNode *left_rotate(struct TreeNode *root) {
    struct TreeNode *p = root->right;
    root->right = p->left;
    p->left = root;

    return p;
}

struct TreeNode *right_rotate(struct TreeNode *root) {
    struct TreeNode *p = root->left;
    root->left = p->right;
    p->right = root;       
    return p;
}


struct TreeNode *maintain(struct TreeNode *root) {
    if (abs(getHeight(root->left) - getHeight(root->right)) <= 1) return root;
    if (getHeight(root->left) > getHeight(root->right)) {
        if (root->left && root->right && getHeight(root->left->right) > getHeight(root->left->left)) {
            root->left = left_rotate(root->left);
        }
        root = right_rotate(root);
    } else {
        if (root->left && root->right && getHeight(root->right->left) > getHeight(root->right->right)) {
            root->right = right_rotate(root->right);
        }
        root = left_rotate(root);
    }
    return root;
}
struct TreeNode *getNewNode(int target) {
    struct TreeNode *p = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    p->val = target;
    p->left = p->right = NULL;
    return p;
}
struct TreeNode *insert(struct TreeNode *root, int target) {
    if (root == NULL) return getNewNode(target);
    
    if (root->val > target) {
        root->left = insert(root->left, target);
    } else {
        root->right = insert(root->right, target);
    }
    return maintain(root);
}

struct TreeNode* sortedArrayToBST(int* nums, int numsSize){
    struct TreeNode *root = NULL;
    for (int i = 0; i < numsSize; ++i) {
        root = insert(root, nums[i]);
    }
    return root;
}

112. 路径总和

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
void hash_insert(struct TreeNode *A, int *num, int sum) {
    if (A->left == NULL && A->right == NULL) {
        if (sum > 1000 || sum < -1000) return ;
        if (sum < 0) num[1000 - sum] = 1;
        else num[sum] = 1;
        return ;
    } 
    if (A->left) hash_insert(A->left, num, sum + A->left->val);
    if (A->right) hash_insert(A->right, num, sum + A->right->val);
    return ;
}

//哈希

bool hasPathSum(struct TreeNode* root, int targetSum) {
    if (root == NULL) return false;
    int num[2001] = {0};
    //memset(num, 0, sizeof(num));
    hash_insert(root, num, root->val);
    if (targetSum >= 0) return num[targetSum];
    return num[1000 - targetSum];
}
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    bool hasPathSum(TreeNode* root, int targetSum) {
        if (root == nullptr) return false;
        if (root->left == nullptr && root->right == nullptr) {
            return root->val == targetSum;
        }
        return hasPathSum(root->left, targetSum - root->val) | hasPathSum(root->right, targetSum - root->val);;
    }
};

103. 二叉树的锯齿形层序遍历

  • BFS
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

#define N (1024)
int** zigzagLevelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    *returnSize = 0;
    if (root == NULL) return NULL;

    int **ans = (int **)malloc(sizeof(int *) * N );
    
    *returnColumnSizes = (int *)malloc(sizeof(int) * N );

    struct TreeNode *queue[N], *p = NULL;
    int l = 0, r = 0;
    queue[r++] = root;
    //循环队列,反向搜索
    int flag = 0;//flag = 0从左往右,1从右往左
    while (l != r) {
        //printf("flag = %d, l = %d, r = %d\n", flag, l, r);
        int n = r - l;
        (*returnColumnSizes)[*returnSize] = n;
        int *s = (int *)malloc(sizeof(int) * n);
        int rr = r - 1;
        l = r;
        if (flag == 0) { //从左往右
            for (int i = 0; i < n; ++i) {
                p = queue[rr];
                rr = (--rr) % N;

                s[i] = p->val;
                if (p->left != NULL) {
                    queue[r] = p->left;
                    r = (++r) % N;
                }
                if (p->right != NULL) {
                    queue[r] = p->right;
                    r = (++r) % N;                    
                }


            }
            flag = 1;
        } else { //从右往左
            for (int i = 0; i < n; ++i) {
                p = queue[rr];
                rr = (--rr) % N;

                s[i] = p->val;

                if (p->right != NULL) {
                    queue[r] = p->right;
                    r = (++r) % N;                    
                }
                if (p->left != NULL) {
                    queue[r] = p->left;
                    r = (++r) % N;
                }

            }
            
            flag = 0;
        }
        ans[*returnSize] = s;
        ++(*returnSize);

    }
    return ans;
}

文章作者: Axieyun
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Axieyun !
评论
评论
  目录