Implementing an AVL tree using a List

Question

So I have implemented an Binary search tree using a parameterized List i.e.

List<Node> tree = new List<>();

The tree works fine. The node itself doesn't know anything about its parent or children. This is because I calculate the locations based on the index e.g.

                         If i is the index of some None N then:
                                N's left child is in tree[i*2] 
                                N's right child is in tree[(i*2)+1]

This binary tree works fine. But now I want to put AVL tree features to it. Im am stuck at this point because I do not know how to make the rotations on a List. On rotation, how do i move the children of the new root? Fact is they have to shift indexes don't they? Also doing this on an List gives me the problem that displaying the tree will require looping through the List everytime i add a node. THis wont happen in O(logn) anymore destroying the whole point of an AVL tree.

I am doing this in C#. I just want to know how to make this AVL tree efficiently using a List or any array based data structure thats indexable and not a Linked list. This is important.Some code to illustrate would be greatly appreciated.

Answer 1

Representing a tree in an array/list the way you are doing is common for the heap data structure, but it does not work for virtually any other kind of tree. In particular, you cannot do this (efficiently) for AVL trees because each rotation would require too much copying.

Answer 2

I had a need for this for an embedded application where we did not have malloc available. Having not any done any kind of data structure algorithm implementation before I was trying if it could be done. While writing code I realized I would have to move a lot of things around. I searched for a remedy and got to this post.

Thanks to Chris's reply, I am not going to spend any more time on it. I will find some other way to implement what I need.

Answer 3

I believe I found an answer, the Trick is to move subtrees up and down the list so that you don't overwrite valid nodes while rotating.

void shiftUp(int indx, int towards) {
    if (indx >= size || nodes[indx].key == NULL) {
        return;
    }
    nodes[towards] = nodes[indx];
    nodes[indx].key = NULL;
    shiftUp(lChild(indx), lChild(towards));
    shiftUp(rChild(indx), rChild(towards));
}

void shiftDown(int indx, int towards) {
    if (indx >= size || nodes[indx].key == NULL) {
        return;
    }

    // increase size so we can finish shifting down
    while (towards >= size) { // while in the case we don't make it big enough
        enlarge();
    }

    shiftDown(lChild(indx), lChild(towards));
    shiftDown(rChild(indx), rChild(towards));
    nodes[towards] = nodes[indx];
    nodes[indx].key = NULL;
}

As you can see this is done by exploring recursively each subtree until the NULL (defined in this as -1) nodes then copying each element one by one up or down.

with this we can define the 4 types of rotations named according this Wikipedia Tree_Rebalancing.gif

void rotateRight(int rootIndx) {
    int pivotIndx = lChild(rootIndx);

    // shift the roots right subtree down to the right
    shiftDown(rChild(rootIndx), rChild(rChild(rootIndx)));
    nodes[rChild(rootIndx)] = nodes[rootIndx]; // move root too

    // move the pivots right child to the roots right child's left child
    shiftDown(rChild(pivotIndx), lChild(rChild(rootIndx)));

    // move the pivot up to the root
    shiftUp(pivotIndx, rootIndx);

    // adjust balances of nodes in their new positions
    nodes[rootIndx].balance--; // old pivot
    nodes[rChild(rootIndx)].balance = (short)(-nodes[rootIndx].balance); // old root
}

void rotateLeft(int rootIndx) {
    int pivotIndx = rChild(rootIndx);

    // Shift the roots left subtree down to the left
    shiftDown(lChild(rootIndx), lChild(lChild(rootIndx)));
    nodes[lChild(rootIndx)] = nodes[rootIndx]; // move root too

    // move the pivots left child to the roots left child's right child
    shiftDown(lChild(pivotIndx), rChild(lChild(rootIndx)));

    // move the pivot up to the root
    shiftUp(pivotIndx, rootIndx);

    // adjust balances of nodes in their new positions
    nodes[rootIndx].balance++; // old pivot
    nodes[lChild(rootIndx)].balance = (short)(-nodes[rootIndx].balance); // old root
}


// Where rootIndx is the highest point in the rotating tree
// not the root of the first Left rotation
void rotateLeftRight(int rootIndx) {
    int newRootIndx = rChild(lChild(rootIndx));

    // shift the root's right subtree down to the right
    shiftDown(rChild(rootIndx), rChild(rChild(rootIndx)));
    nodes[rChild(rootIndx)] = nodes[rootIndx];

    // move the new roots right child to the roots right child's left child
    shiftUp(rChild(newRootIndx), lChild(rChild(rootIndx)));

    // move the new root node into the root node
    nodes[rootIndx] = nodes[newRootIndx];
    nodes[newRootIndx].key = NULL;

    // shift up to where the new root was, it's left child
    shiftUp(lChild(newRootIndx), newRootIndx);

    // adjust balances of nodes in their new positions
    if (nodes[rootIndx].balance == -1) { // new root
        nodes[rChild(rootIndx)].balance = 0; // old root
        nodes[lChild(rootIndx)].balance = 1; // left from old root
    } else if (nodes[rootIndx].balance == 0) {
        nodes[rChild(rootIndx)].balance = 0;
        nodes[lChild(rootIndx)].balance = 0;
    } else {
        nodes[rChild(rootIndx)].balance = -1;
        nodes[lChild(rootIndx)].balance = 0;
    }

    nodes[rootIndx].balance = 0;
}

// Where rootIndx is the highest point in the rotating tree
// not the root of the first Left rotation
void rotateRightLeft(int rootIndx) {
    int newRootIndx = lChild(rChild(rootIndx));

    // shift the root's left subtree down to the left
    shiftDown(lChild(rootIndx), lChild(lChild(rootIndx)));
    nodes[lChild(rootIndx)] = nodes[rootIndx];

    // move the new roots left child to the roots left child's right child
    shiftUp(lChild(newRootIndx), rChild(lChild(rootIndx)));

    // move the new root node into the root node
    nodes[rootIndx] = nodes[newRootIndx];
    nodes[newRootIndx].key = NULL;

    // shift up to where the new root was it's right child
    shiftUp(rChild(newRootIndx), newRootIndx);

    // adjust balances of nodes in their new positions
    if (nodes[rootIndx].balance == 1) { // new root
        nodes[lChild(rootIndx)].balance = 0; // old root
        nodes[rChild(rootIndx)].balance = -1; // right from old root
    } else if (nodes[rootIndx].balance == 0) {
        nodes[lChild(rootIndx)].balance = 0;
        nodes[rChild(rootIndx)].balance = 0;
    } else {
        nodes[lChild(rootIndx)].balance = 1;
        nodes[rChild(rootIndx)].balance = 0;
    }

    nodes[rootIndx].balance = 0;
}

Note that in cases where shifting would overwrite nodes we just copy the single node

As for efficiency storing the balance in each node would be a must as getting the differences of heights at each node would be quite costly

int getHeight(int indx) {
    if (indx >= size || nodes[indx].key == NULL) {
        return 0;
    } else {
        return max(getHeight(lChild(indx)) + 1, getHeight(rChild(indx)) + 1);
    }
}

Though doing this requires us to update the balance at affected nodes when modifying the list, though this can be somewhat efficiently by only updating strictly necessary cases. for deletion this adjustment is

// requires non null node index and a balance factor baised off whitch child of it's parent it is or 0
private void deleteNode(int i, short balance) {
    int lChildIndx = lChild(i);
    int rChildIndx = rChild(i);

    count--;
    if (nodes[lChildIndx].key == NULL) {
        if (nodes[rChildIndx].key == NULL) {

            // root or leaf
            nodes[i].key = NULL;
            if (i != 0) {
                deleteBalance(parent(i), balance);
            }
        } else {
            shiftUp(rChildIndx, i);
            deleteBalance(i, 0);
        }
    } else if (nodes[rChildIndx].key == NULL) {
        shiftUp(lChildIndx, i);
        deleteBalance(i, 0);
    } else {
        int successorIndx = rChildIndx;

        // replace node with smallest child in the right subtree
        if (nodes[lChild(successorIndx)].key == NULL) {
            nodes[successorIndx].balance = nodes[i].balance;
            shiftUp(successorIndx, i);
            deleteBalance(successorIndx, 1);
        } else {
            int tempLeft;
            while ((tempLeft = lChild(successorIndx)) != NULL) {
                successorIndx = tempLeft;
            }
            nodes[successorIndx].balance = nodes[i].balance;
            nodes[i] = nodes[successorIndx];
            shiftUp(rChild(successorIndx), successorIndx);
            deleteBalance(parent(successorIndx), -1);
        }
    }
}

similarly for insertion this is

void insertBalance(int pviotIndx, short balance) {
    while (pviotIndx != NULL) {
        balance = (nodes[pviotIndx].balance += balance);

        if (balance == 0) {
            return;
        } else if (balance == 2) {
            if (nodes[lChild(pviotIndx)].balance == 1) {
                rotateRight(pviotIndx);
            } else {
                rotateLeftRight(pviotIndx);
            }
            return;
        } else if (balance == -2) {
            if (nodes[rChild(pviotIndx)].balance == -1) {
                rotateLeft(pviotIndx);
            } else {
                rotateRightLeft(pviotIndx);
            }
            return;
        }

        int p = parent(pviotIndx);

        if (p != NULL) {
            balance = lChild(p) == pviotIndx ? (short)1 : (short)-1;
        }

        pviotIndx = p;
    }
}

As you can see this just uses plain arrays of "node"s as i translated it from c code given gitHub array-avl-tree and optimizations and balancing from (a link i'll post in a comment) but would work quite similar in a List

Finally I have minimal knowledge of AVL trees, or optimal implementations so i don't claim that this is bug free or the most efficient but have passed my preliminary tests at least for my purposes