DataStructures-Boom/tree_node.h at master · stavgn/DataStructures-Boom · GitHub

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
#ifndef TREE_NODE_H
#define TREE_NODE_H

#include <cassert>

namespace DS
{
    template <class KEY, class DATA>
    class tree_node
    {
    private:
        /* data */
    public:
        KEY index_array[3];                      //in case of node
        KEY &key = index_array[0];               //in case of leaf
        tree_node<KEY, DATA> *children_array[4]; //in case of node
        DATA *data_ptr;                          //in case of leaf
        int length;
        tree_node<KEY, DATA> *left_ptr;  //in case of leaf
        tree_node<KEY, DATA> *right_ptr; //in case of leaf

        tree_node(const KEY &inserted_key = KEY());
        ~tree_node();
        int insert(tree_node<KEY, DATA> *node); //returns the place in the node of the new node
        tree_node<KEY, DATA> *remove(const KEY &removen_key);
    };

    template <class KEY, class DATA>
    tree_node<KEY, DATA>::tree_node(const KEY &inserted_key)

    {
        children_array[0] = children_array[1] = children_array[2] = children_array[3] = nullptr;
        data_ptr = nullptr;
        left_ptr = nullptr;
        right_ptr = nullptr;
        index_array[0] = inserted_key;
        index_array[1] = KEY();
        index_array[2] = KEY();
        length = (1);
    }
    template <class KEY, class DATA>
    tree_node<KEY, DATA>::~tree_node()
    {
        delete data_ptr;
    }

    template <class KEY, class DATA>
    int tree_node<KEY, DATA>::insert(tree_node *node)
    {
        assert(length < 4);
        int place_in_node = 0;
        for (place_in_node = 0; place_in_node < length; place_in_node++)
        {
            if (node->key < children_array[place_in_node]->key)
            {
                if ((place_in_node > 0) && (node->key >= index_array[place_in_node - 1]))
                {
                    assert(node->children_array[0] == nullptr); //is a leaf
                    index_array[place_in_node - 1] = children_array[place_in_node]->key;
                }
                for (int i = length; i > place_in_node; i--)
                {
                    children_array[i] = children_array[i - 1];
                    if ((i > place_in_node) && ((i - 2) >= 0))
                    {
                        index_array[i - 1] = index_array[i - 2];
                    }
                }
                break;
            }
        }
        children_array[place_in_node] = node;
        if (place_in_node > 0)
        {
            index_array[place_in_node - 1] = node->key;
        }
        else // place_in_node = 0
        {
            index_array[0] = children_array[1]->key;
        }

        length += 1;
        assert(length <= 4);

        return place_in_node;
    }
    template <class KEY, class DATA>
    tree_node<KEY, DATA> *tree_node<KEY, DATA>::remove(const KEY &removen_key)
    {
        assert(length > 1);
        int place_in_node = 0;
        for (place_in_node = 0; (place_in_node < length) && (removen_key != children_array[place_in_node]->key); place_in_node++)
            ; // find the place in the node
        if (place_in_node == length)
        {
            assert(removen_key != children_array[place_in_node]->key);
            return nullptr; //case not found
        }
        tree_node<KEY, DATA> *removen_node = children_array[place_in_node];
        if (removen_node->key != removen_key)
        {
            return nullptr;
        }
        for (int i = place_in_node; i < length - 1; i++)
        {
            children_array[i] = children_array[i + 1];
            if (i < length - 2)
            {
                index_array[i] = index_array[i + 1];
            }
        }

        children_array[length - 1] = nullptr;
        length -= 1;

          return removen_node;
    }

} // namespace DS

#endif