TRITIUM CLOUD 氚

By Ao Zhang

0%

Posted on Edited on
唯愛門前雙柳樹，枝枝葉葉不相離。 *

Tree is a very important concept in graph theory and commonly used in file systems, Document Object Models and other applications.

Paddy3118, CC BY-SA 4.0 https://creativecommons.org/licenses/by-sa/4.0, via Wikimedia Commons

What is a tree?

In computer science, tree is an abstract model of a hierarchical structure. It has following features: - For every node, there are limited number of children or no children. - The node without a parent is called root. - For every node that is not a root, there is a parent. - Except from the root, every node can seperate to multiple branches without any common node. - There is no cycle in the tree.

Tree Terminologies

  • Node: Each node is a single element in the tree.
  • Root: The node without a parent.
  • Internal node: A node that has at least one child.
  • External node (Leaf node): A node that has no child.
  • Ancestors: Parent, grandparent, grandgrandparent, etc.
  • Descendants: Children, grandchildren, grandchildren, etc.
  • Sibling: Children of the same parent.
  • Height: The height of a node is the longest downward path to a leaf from that node.
  • Depth: The depth of a node is the length of the path from the root to that node.
  • Subtree: Tree consisting of a node and all its descendants.

Traversal of a Tree

There are three types of traversal of a tree: preorder, inorder and postorder.

Here is a simple example of traversals of a tree: user:Nomen4Omen, Public domain, via Wikimedia Commons
Traversal scheme Nodes visited Code
Pre-order

Node visited at position RED 🔴

F, B, A, D, C, E, G, I, H

 
1
2
3
4
5
6
def preorder(root):
    if root is None:
        return
    print(root.data)
    preorder(root.leftChild)
    preorder(root.rightChild)
In-order

Node visited at position GREEN 🟢

A, B, C, D, E, F, G, H, I

 
1
2
3
4
5
6
def inorder(root):
    if root is None:
        return
    inorder(root.leftChild)
    print(root.data)
    inorder(root.rightChild)
Post-order

Node visited at position BLUE 🔵

A, C, E, D, B, H, I, G, F

 
1
2
3
4
5
6
def postorder(root):
    if root is None:
        return
    postorder(root.leftChild)
    postorder(root.rightChild)  
    print(root.data)

Binary Search Tree

A binary search tree is a binary tree in which the value of each node is greater than the values of all the nodes in the left subtree and less than the values of all the nodes in the right subtree. No machine-readable author provided. Dcoetzee assumed (based on copyright claims)., Public domain, via Wikimedia Commons

Binary tree is practical for fast search of an element, addition of a new element and deletion of an element in a sorted list. It is also used in a lot of other applications, on average the time complexity of which is O(log n) for all the operations and the space complexity is O(n) for the tree.

Here is a code exmple of a binarty search tree in C++:

treenode.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#ifndef TREENODE_H
#define TREENODE_H

#include <iostream>
using std::cerr;
using std::cout;
using std::endl;
using std::ostream;

#include <memory>
using std::unique_ptr;

#include <utility>
using std::pair;

template <typename T>
class TreeNode
{
private:
public:
    T data;
    unique_ptr<TreeNode<T>> leftChild;
    unique_ptr<TreeNode<T>> rightChild;
    TreeNode<T> *parent;

    TreeNode<T>(T data) : data(data), leftChild(nullptr), rightChild(nullptr), parent(nullptr) {}

    void setLeftChild(TreeNode<T> *child)
    {
        leftChild.reset(child);
        child->parent = this;
    }

    void setRightChild(TreeNode<T> *child)
    {
        rightChild.reset(child);
        child->parent = this;
    }

    void write(ostream &o) const
    {
        if (leftChild)
        {
            leftChild->write(o);
        }
        o << " " << data << " ";
        if (rightChild)
        {
            rightChild->write(o);
        }
    }

    int maxDepth()
    {
        return MaxDepthFromNode(this);
    }

    int MaxDepthFromNode(TreeNode<T> *node)
    {
        if (node == nullptr)
        {
            return 0;
        }
        else
        {
            int left_depth = MaxDepthFromNode(node->leftChild.get());
            int right_depth = MaxDepthFromNode(node->rightChild.get());

            if (left_depth > right_depth)
            {
                return (left_depth + 1);
            }
            else
            {
                return (right_depth + 1);
            }
        }
    }
};

template <typename T>
class TreeNodeIterator
{
private:
    TreeNode<T> *current;

public:
    TreeNodeIterator(TreeNode<T> *currentIn) : current(currentIn) {}

    T &operator*()
    {
        return current->data;
    }

    bool operator==(const TreeNodeIterator<T> &rhs)
    {
        return current == rhs.current;
    }

    bool operator!=(const TreeNodeIterator<T> &rhs)
    {
        return !(current == rhs.current);
    }

    void operator++()
    {
        if (current->rightChild)
        {
            TreeNode<T> *right_left_child = current->rightChild.get();
            while (right_left_child->leftChild)
            {
                right_left_child = right_left_child->leftChild.get();
            }
            current = right_left_child;
        }
        else
        {
            TreeNode<T> *parent_node = current->parent;
            while (parent_node != nullptr)
            {
                if (parent_node->data < current->data)
                {
                    parent_node = parent_node->parent;
                }
                else
                {
                    break;
                }
            }
            current = parent_node;
        }
    }
};

#endif

treemap.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#ifndef TREEMAP_H
#define TREEMAP_H

#include "tree.h"

template <typename Key, typename Value>
class KeyValuePair
{

public:
    const Key k;
    Value v;
    
    KeyValuePair(Key key) : k(key) {}
    KeyValuePair(Key key, Value val) : k(key), v(val) {}

    bool operator<(const KeyValuePair &rhs)
    {
        if (k < rhs.k)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
};

template <typename Key, typename Value>
ostream &operator<<(ostream &o, const KeyValuePair<Key, Value> &kv)
{
    o << kv.k << "," << kv.v;
    return o;
}

template <typename Key, typename Value>
class TreeMap
{

private:
    BinarySearchTree<KeyValuePair<Key, Value>> tree;

public:
    KeyValuePair<Key, Value> *insert(const Key &k, const Value &v)
    {
        return &(tree.insert(KeyValuePair<Key, Value>(k, v))->data);
    }

    void write(ostream &o) const
    {
        tree.write(o);
    }

    KeyValuePair<Key, Value> *find(Key key)
    {
        KeyValuePair<Key, Value> new_key_value_pair(key);
        if (tree.find(new_key_value_pair))
        {
            return &tree.find(new_key_value_pair)->data;
        }
        else
        {
            return nullptr;
        }
    }
};


#endif

tree.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#ifndef TREE_H
#define TREE_H

#include "treenode.h"

template <typename T>
class BinarySearchTree
{
private:
    unique_ptr<TreeNode<T>> root;

public:
    BinarySearchTree() {}

    void write(ostream &o) const
    {
        root->write(o);
    }

    TreeNode<T> *insert(T data)
    {
        TreeNode<T> *node = insert_node(data);
        if (node->parent && node->parent->parent)
        {
            PerformRotation(node->parent->parent);
        }
        return node;
    }

    TreeNode<T> *insert_node(T data)
    {
        TreeNode<T> *current_node = root.get();
        if (!current_node)
        {
            TreeNode<T> *new_node = new TreeNode<T>(data);
            root.reset(new_node);
            return root.get();
        }
        else
        {
            while (current_node)
            {
                if (current_node->data < data)
                {
                    if (!current_node->rightChild)
                    {
                        TreeNode<T> *new_node = new TreeNode<T>(data);
                        current_node->setRightChild(new_node);
                        new_node->parent = current_node;
                        return new_node;
                    }
                    else
                    {
                        current_node = current_node->rightChild.get();
                    }
                }
                else if (data < current_node->data)
                {
                    if (!current_node->leftChild)
                    {
                        TreeNode<T> *new_node = new TreeNode<T>(data);
                        current_node->setLeftChild(new_node);
                        new_node->parent = current_node;
                        return new_node;
                    }
                    else
                    {
                        current_node = current_node->leftChild.get();
                    }
                }
                else
                {
                    return current_node;
                }
            }
            return current_node;
        }
    }

    TreeNode<T> *find(T data)
    {
        TreeNode<T> *current_node = root.get();
        if (!current_node)
        {
            return nullptr;
        }
        else
        {
            while (current_node)
            {
                if (current_node->data < data)
                {
                    if (!current_node->rightChild)
                    {
                        return nullptr;
                    }
                    else
                    {
                        current_node = current_node->rightChild.get();
                    }
                }
                else if (data < current_node->data)
                {
                    if (!current_node->leftChild)
                    {
                        return nullptr;
                    }
                    else
                    {
                        current_node = current_node->leftChild.get();
                    }
                }
                else
                {
                    return current_node;
                }
            }
            return current_node;
        }
    }

    TreeNodeIterator<T> begin() const
    {
        if (!root)
        {
            return nullptr;
        }
        else
        {
            TreeNode<T> *current_node = root.get();

            while (current_node->leftChild)
            {
                current_node = current_node->leftChild.get();
            }
            return TreeNodeIterator<T>(current_node);
        }
    }

    TreeNodeIterator<T> end() const
    {
        if (!root)
        {
            return nullptr;
        }
        else
        {
            TreeNode<T> *current_node = root.get();

            while (current_node->rightChild)
            {
                current_node = current_node->rightChild.get();
            }
            return TreeNodeIterator<T>(current_node->rightChild.get());
        }
    }
};

#endif

AVL Tree

AVL tree is a self-balancing binary tree. The name AVL comes from the inventors of the algorithm (Adelson-Velsky and Landis). In an AVL tree, the heights of the two child subtrees of any node differ by at most one.

In the worst case, when using a Binary Search Tree, the data is adding in ascending order, the search time is O(n) and the insertion time is O(n). Therefore, to optimize the search time, we can use an AVL tree to balence the tree. AVL trees rebalance themselves after each insertion and deletion, it is done by calculation the balance factor of that node. The balance factor is calculated as follows: 

1
balanceFactor(node) = maxDepth(left node) - maxDepth(right node)

Functions for AVL tree 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
int maxDepth()
{
    TreeNode<T> *node = root.get();
    if (node == nullptr)
    {
        return 0;
    }
    else
    {
        int left_depth = MaxDepthFromNode(node->leftChild.get());
        int right_depth = MaxDepthFromNode(node->rightChild.get());

        if (left_depth > right_depth)
        {
            return (left_depth + 1);
        }
        else
        {
            return (right_depth + 1);
        }
    }
}

int MaxDepthFromNode(TreeNode<T> *node)
{
    if (node == nullptr)
    {
        return 0;
    }
    else
    {
        int left_depth = MaxDepthFromNode(node->leftChild.get());
        int right_depth = MaxDepthFromNode(node->rightChild.get());

        if (left_depth > right_depth)
        {
            return (left_depth + 1);
        }
        else
        {
            return (right_depth + 1);
        }
    }
}

int BalenceFactor(TreeNode<T> *node)
{
    if (node == nullptr)
    {
        return 0;
    }
    return MaxDepthFromNode(node->leftChild.get()) - MaxDepthFromNode(node->rightChild.get());
}

void LeftRotation(TreeNode<T> *node_a)
{
    TreeNode<T> *node_b = node_a->rightChild.release();
    node_a->rightChild.reset(node_b->leftChild.release());

    if (node_a->parent)
    {
        if (node_a->parent->leftChild.get() == node_a)
        {
            node_b->parent = node_a->parent;
            node_a->parent = node_b;
            node_b->leftChild.reset(node_b->parent->leftChild.release());
            node_b->parent->leftChild.reset(node_b);
        }
        else
        {
            node_b->parent = node_a->parent;
            node_a->parent = node_b;
            node_b->leftChild.reset(node_b->parent->rightChild.release());
            node_b->parent->rightChild.reset(node_b);
        }
    }
    else
    {
        TreeNode<T> *node_a = root.release();
        node_b->parent = node_a->parent;
        node_a->parent = node_b;
        node_b->leftChild.reset(node_a);
        root.reset(node_b);
    }
}

void RightRotation(TreeNode<T> *node_c)
{
    TreeNode<T> *node_b = node_c->leftChild.release();
    node_c->leftChild.reset(node_b->rightChild.release());

    if (node_c->parent)
    {
        if (node_c->parent->leftChild.get() == node_c)
        {
            node_b->parent = node_c->parent;
            node_c->parent = node_b;
            node_b->rightChild.reset(node_b->parent->leftChild.release());
            node_b->parent->leftChild.reset(node_b);
        }
        else
        {
            node_b->parent = node_c->parent;
            node_c->parent = node_b;
            node_b->rightChild.reset(node_b->parent->rightChild.release());
            node_b->parent->rightChild.reset(node_b);
        }
    }
    else
    {
        TreeNode<T> *node_c = root.release();
        node_b->parent = node_c->parent;
        node_c->parent = node_b;
        node_b->rightChild.reset(node_c);
        root.reset(node_b);
    }
}

void LeftRightRotation(TreeNode<T> *node_c)
{
    TreeNode<T> *node_a = node_c->leftChild.get();

    LeftRotation(node_a);
    RightRotation(node_c);
}

void RightLeftRotation(TreeNode<T> *node_a)
{
    TreeNode<T> *node_c = node_a->rightChild.get();

    RightRotation(node_c);
    LeftRotation(node_a);
}

void PerformRotation(TreeNode<T> *node)
{
    int balance = BalenceFactor(node);
    if (abs(balance) >= 2)
    {
        if(node->rightChild && node->rightChild.get()->rightChild)
        {
            LeftRotation(node);
        }
        else if(node->leftChild && node->leftChild.get()->leftChild)
        {
            RightRotation(node);
        }
        else if(node->leftChild && node->leftChild.get()->rightChild)
        {
            LeftRightRotation(node);
        }
        else if(node->rightChild && node->rightChild.get()->leftChild)
        {
            RightLeftRotation(node);
        }
    }
}