Define Node properties

[andrealorenzon]

General type: struct (could be class, but everything is public (to Tree) in a node, so it can safely be a struct)

Necessary attributes: K key (must be comparable, with >, =, and <) T value
shared_ptr<Node> left
shared_ptr<Node> right

Optional but useful:
short int balance to keep track of tree balancing shared_ptr<Node> root to understand to which tree the node belongs to weak_ptr<Node> parent pro: breadcrumbing, backtracking, easier navigation , cons: more memory used. IMPORTANT!! Must be weak to avoid circular reference!!!

[andrealorenzon]

What must a node do?

constructor(s) and destructor:

1. empty constructor ( new Node() )
2. constructor with initialization( new Node(value) )

Methods:

1. get and set value: will the node do that, or the tree? I'll let it to the node.
2. delete: it should delete only the node, while preserving child nodes. they should be re-inserted.
3. compute balance: how does a node compute its balance value? when should it do that automatically?

[andrealorenzon]

Layout:

    /**
     * @brief binary search Tree node struct
     */
template <typename K, typename T>
struct Node {
    K key;         // key
    T value;       // value
    short int balance // balance of the node
    shared_ptr<Node> left;  // pointer to left node
    shared_ptr<Node> right;  // pointer to right node
    shared_ptr<Node> parent;  // temporary, maybe we'll remove it later

      /**
       * @brief Constructor of a binary search tree node
       */
    Node():    //not sure about this
        key(), value(), left(NULL), right(NULL) {};
    Node(const K k, const T v): {
         this->key = k;
         this->value = v;
         this->left = NULL;
         this->right = NULL;
         this->parent.reset();
        };
    };
};  // end struct Node

[francescocicala]

What must a node do?

constructor(s) and destructor:

1. empty constructor ( `new Node()` )

2. constructor with initialization( `new Node(value)` )

Methods:

1. get and set value: will the node do that, or the tree? I'll let it to the node.

2. delete: it should delete only the node, while preserving child nodes. they should be re-inserted.

Agree

3. compute balance: how does a node compute its balance value? when should it do that automatically?

By definition, balance_factor := height(right_subtree) - height(left_subtree) If we want each node to store its balance factor, each time a node is inserted or removed the tree has to update all the balance factors. But, since those values are needed only when rebalancing the tree, we could also consider to compute them just when they are needed.