Binary trees -- traversal, insertion, deletion, and balancing.

这一章比较纠结，可浅可深。既然是伪技术总结，就只提一提要点就好了。

1. Traversal

i) Breadth First: The key is to use a queue to maintain the traversal...two steps as follow.
a) Enqueue root.
b) while (queue != null)
        {
         qPointer = Dequeue;
         visit qPointer;
         Enqueue left and right children of the qPointer.
}

ii) Depth First: Inorder, Preorder and Post order.
L - Left sub tree; R- Right sub-tree; V = visit (access) the node;

Easy in using recursion,
Inorder = LVR.
Preorder = VLR.
Postorder = LRV.

A bit complicated in using non-recursive methods.
a) by maintaining a stack, traversal can be implemented using iterations.
b) using a threaded tree can avoid the stack.
c) Morris's algorithm can avoid both a) and b) to traversal a tree through tree transformation. (complicated...)

In general, recursive methods has better readable code with marginal cost of performance. However, for certain cases, e.g., ultimate performance to be achieve or suffering stack overflow, non-recursive methods or Morris's algorithms has to apply!!

2. Insertion in threaded tree and deletions.

i) insertion.
the key points are using two pointers, prev and p. Consider element el to be inserted. Keep going until these three stop criterion.

a) if (el < p -> el) prev = p and p go left (p = p -> left) until p == nullptr;
b) if (el > p -> el and thread indicator == 0) prev = p and go right until p == nullptr;
c) if (el > p -> el and thread indicator == 1) stop;

How to insert:
a) if (el < prev -> el) insertion is the left child of prev, successor of the child is prev.
b) else if (prev -> successor) means parent of the insertion is not the rightmost node, so, prev -> right = insertion. make parent's successor the insertion's successor.
c) else prev -> right = insertion. (prev is the rightmost node, just insert new node to the right side.)

This is important and very easy to make mistakes when assigning the successor indicator....


ii) deletion.
By merging or copying we could delete a node that has sub-trees on both of its left and right side.

Merging increases the tree depth significantly while copying method has to consider the balancing issue in those problems of many deletion and insertion operations.

3. Balancing
AVL and black-red trees are similar. Specifically, black-red tree is the underlying implementation of (sorted) map and set in STL in C++!!

Data structure 之 Linked List

Key summaries of linked list chapter from Drozdek's Data Structures and Algorithms in C++.

Lists mainly consists of 2 classes, one for node and list for the other. Nodes comprise elements to store and pointers to be linked while List is maintaining the "Head", "Tail" and functions for interface and implementation(e.g., insert, search, etc.).

1. Fundamental lists: singly and doubly linked list.

Nodes of singly linked list has one pointer pointing to the next while doubly linked list contains two pointers. Examples follow by the end of the text.

2. Skip lists and self organising lists.

Skip list is overwhelmingly better in searching with the complexity of lg(n).

self organising lists consist of:

i) move-to-front. (one been searched jumps to the head or tail)

ii) transpose.(one been searched float-up or sink-down by one position)

iii) count    (descent by the frequency been searched)

iv) ordering  (by certain criterion, e.g., alphabetical)

In terms of efficiency (approximately and regardless of the cost on pointers):

i) == iii) > ii)
i) == iii) > iv)

3. "Two one-dimensional arrays of linked lists" to establish compact index which saves storage space.

#1. class declarations for singly and doubly linked lists.

class IntSingleList

{

public:

    IntSingleList() : info(0), next(nullptr) {}

    IntSingleList(int in, IntSingleList* pn = nullptr) : info(in), next(pn) {}

int info = 0;

IntSingleList* next;

};

class IntSLList

{

public:

    IntSLList() : head(nullptr), tail(nullptr){}

    ~IntSLList();

    int isEmpty()

    {

        return head == nullptr;

    }

    void addToHead(int);

    void addToTail(int);

    int deleteFromHead();

    int deleteFromTail();

    void deleteNode(int);

    bool isInList(int) const;

private:

    IntSLLNode* head = nullptr, *tail = nullptr;

};

#2. Example of skip list.

//---------------------------

//skipList.h

const int maxLevel = 4;

template<typename T>

class skipListNode

{

public:

    skipListNode() = default;

    skipListNode(const T& k, skipListNode *nt = nullptr) : key(k), next(nt){}

    T key;

    skipListNode *next = nullptr;

};

template<typename T>

class skipList

{

public:

    skipList() = default;

    bool isEmpty() const;

    void choosePowers();

    int chooseLevel();

    T* skipListSearch(const T&);

    void skipListInsert(const T&);

private:

    typedef skipList<T> *nodePtr;

    nodePtr root[maxLevel] = {nullptr};

    int powers[maxLevel] = {0};

};

//----------------------------------

//skipList.cpp

template<class T>

bool skipList<T>::isEmpty() const

{

    return root[0] == nullptr;

}

template<class T>

void skipList<T>::choosePowers()

{

    powers[maxLevel - 1] = (2 << (maxLevel-1)) - 1; // 2 ^ maxLevel - 1

    for (int i = maxLevel - 2, j = 0; i >= 0; --i, ++j)

        powers[i] = powers[i+1] - (2 << j); // 2 ^ (j+1)

}

template<class T>

int skipList<T>::chooseLevel()

{

    std::default_random_engine e;

    int i, r = e() % powers[maxLevel-1] + 1;

    for (int i = 1; i < maxLevel; ++i)

        if (r < powers[i])

        return i-1;

    return i-1;

}

template<class T>

T* skipList<T>::skipListSearch(const T& key)

{

    if (isEmpty())

        return nullptr;

    nodePtr prev = nullptr, curr = nullptr;

    int lvl = 0;

    for (lvl = maxLevel - 1; lvl >= 0 && !root[lvl]; --lvl);    //find the highest non-null level;

    prev = curr = root[lvl];

    while(true)

    {

        if(key == curr->key)

            return &curr->key;

        else if (key < curr->key)

        {

            if (!lvl)

                return 0;

            else if (curr == root[lvl])

                curr = root[--lvl];

            else curr = *(prev->next + --lvl);

        }

        else

        {

            prev = curr;

            if (*(curr->next + lvl) != 0)

                curr = *(curr->next + lvl);

            else

            {

                for (lvl--; lvl >=0 && *(curr->next + lvl) == 0; --lvl);

                if (lvl >= 0)

                    curr = *(curr->next + lvl);

                else return 0;

            }

        }

    }

}

template<class T>

void skipList<T>::skipListInsert(const T& key)

{

    nodePtr curr[maxLevel], prev[maxLevel], newNode;

    int lvl, i;

    curr[maxLevel-1] = root[maxLevel-1];

    prev[maxLevel-1] = 0;

    for (lvl = maxLevel - 1; lvl >= 0; --lvl)

    {

        while (curr[lvl] && curr[lvl]->key < key)

        {

            prev[lvl] = curr[lvl];

            curr[lvl] = *(curr[lvl]->next + lvl);

        }

        if (curr[lvl] && curr[lvl]->key == key)

            return;

        if (lvl > 0)

            if (!prev[lvl])

        {

            curr[lvl-1] = root[lvl-1];

            prev[lvl-1] = 0;

        }

        else

        {

            curr[lvl-1] = *(prev[lvl]->next + lvl-1);

            prev[lvl-1] = prev[lvl];

        }

    }

    lvl = chooseLevel();

    newNode = new skipListNode<T>;

    newNode->next = new nodePtr[sizeof(nodePtr) * (lvl+1)];

    newNode->key = key;

    for (i = 0; i <= lvl; ++i)

    {

        *(newNode->next + i) = curr[i];

        if (prev[i] == 0)

            root[i] = newNode;

        else *(prev[i]->next + i) = newNode;

    }

}