Balanced binary tree with height as balance condition


  • 0
    V

    Actually, I was trying to implement a segment tree by what I remember (I had roughly heard of segment tree 3 years ago). But after my finish and seeing the solution, I find what I had implemented is a balanced binary search tree with height as balance condition... and I want comments and discussion.
    The tree I used is a binary search tree where each node represents a closed interval [ends[0], ends[1]] that all points in it is at height.
    The tree is also a balanced tree that use height as balance condition, which means a subtree is "balanced" until its root has the biggest height. A unbalanced tree will be rotated to balance, the rotate operation is similar to that of AVL tree.
    The two features of the tree means we can find the interval that the new square will be stuck in one turn of binary search.

    struct segment {
        int ends[2]; //all points in [ends[0], ends[1]] is at height
        int height;
        struct segment *left, *right;
    };
    #define INF 1000000000
    
    struct segment *newSegment(int l, int r, int h) {
        struct segment *s = (struct segment *) malloc(sizeof(struct segment));
        s->ends[0] = l;
        s->ends[1] = r;
        s->height = h;
        s->left = s->right = NULL;
        return s;
    }
    
    // typical recursion searching of binary search tree
    struct segment *findSegment(struct segment *root, int l, int r) {
        if (root->ends[0] > r)
            return findSegment(root->left, l, r);
        if (root->ends[1] < l)
            return findSegment(root->right, l, r);
        return root;
    }
    
    // balance a unbalanced tree in recursion (in a bottom-up way)
    void sortSegment(struct segment **root, int l, int r) {
        struct segment *p = (*root);
        if (p->ends[0] > r) {
            sortSegment(&(p->left), l, r);     // balance left subtree
            if (p->height < p->left->height) { // left son is higher than root, rotate right
                (*root) = p->left;
                p->left = p->left->right;
                (*root)->right = p;
            }
        } else if (p->ends[1] < l) {
            sortSegment(&(p->right), l, r);
            if (p->height < p->right->height) {
                (*root) = p->right;
                p->right = p->right->left;
                (*root)->left = p;
            }
        } 
    }
    
    int insertSegment(struct segment **root, int pos, int len) {
        int l = pos, r = pos + len - 1;
        // find the first segment 'ptr' that the new square stick
        struct segment *ptr = findSegment(*root, l, r);
        int h = ptr->height + len;
        
        // because of symmetry, we just consider left endpoint of the new square
        // three cases: the left endpoint is 'left to / same as / right to' that of 'ptr'
        // and we truncate the 'ptr' to turn 'left to / right to' cases into 'same as'.
    
        // case 0: right to, 'ptr' is split and new segment is inserted
        if (ptr->ends[0] < l) {
            struct segment *s0 = newSegment(ptr->ends[0], l - 1, ptr->height);
            s0->left = ptr->left;
            ptr->left = s0;
        
        // case 1: left to, the left subtree of 'ptr' is truncated 
        } else if (ptr->ends[0] > l) {
            struct segment *s0 = ptr->left;
            while (s0 != NULL) {
                if (s0->ends[0] < l)
                    break;
                // to do: call free()
                s0 = s0->left;
            }
            ptr->left = s0;
            while (s0 != NULL) {
                if (s0->ends[1] >= l)
                    break;
                s0 = s0->right;
            }
            if (s0 != NULL) {
                s0->ends[1] = l - 1;
                s0->right = NULL;
            }
        }
    
        if (ptr->ends[1] > r) {
            struct segment *s1 = newSegment(r + 1, ptr->ends[1], ptr->height);
            s1->right = ptr->right;
            ptr->right = s1;
        } else if (ptr->ends[1] > r) {
            struct segment *s1 = ptr->right;
            while (s1 != NULL) {
                if (s1->ends[1] > r)
                    break;
                // to do: call free()
                s1 = s1->right;
            }
            ptr->right = s1;
            while (s1 != NULL) {
                if (s1->ends[0] <= r)
                    break;
                s1 = s1->left;
            }
            if (s1 != NULL) {
                s1->ends[0] = r + 1;
                s1->left = NULL;
            }
        } 
    
        ptr->ends[0] = l;
        ptr->ends[1] = r;
        ptr->height = h;
    
        // rebalance the tree
        sortSegment(root, l, r);
        return h;
    }
    
    int *fallingSquares(int **positions, int positionsRowSize, int positionsColSize, int *returnSize) {
        
        (*returnSize) = positionsRowSize;
        int *heights = (int *)malloc(sizeof(int) * positionsRowSize);
        struct segment *root = newSegment(0, INF, 0);
        int i, maxh = 0;
        for (i = 0; i < positionsRowSize; i++) {
            int h = insertSegment(&root, positions[i][0], positions[i][1]);
            maxh = (h > maxh) ? h : maxh;
            heights[i] = maxh;
        }
        return heights;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.