Data Structures:


Analyzing an algorithm allows us to predict the resources that it requires:
memory / communication bandwidth / computation time

Big-O : Upper Bound


Linked list: 
Search: Worst case: O(n) 

Binary (Search) Tree:
Search : O(logn)

Tree: a collection of nodes connected by edges
base case: T is empty
recursive definition: if not empty, a Tree consists of:
    a root not r , and zero or more non-empty Sub-trees: T1,T2.....

Root : the only node with no parent

Parent and child : every node except root has only 1 parent
                    a node can have zero or more children

Leaves: nodes with no children

Siblings: nodes with the same parent

Path from node n1 to nk : a sequence of nodes {n1, n2, . . . , nk }
such that ni is the parent of ni+1 for 1 ≤ i ≤ k − 1.

Length of a path
– number of edges on the path

Depth of a node
– length of the unique path from the root to that node

Height of a node
– length of the longest path from that node to a leaf
– all leaves are at height 0

Height of a tree = height of the root = depth of the deepest leaf

Ancestor and descendant: If there is a path from n1 to n2
– n1 is an ancestor of n2
– n2 is a descendant of n1
– if n1 != n2,then: proper ancestor and proper descendant


Binary Tree:
Tree which nodes can have at MOST 2 children

Height of an binary tree with N node is smaller than n

Best case: Well-Balanced Tree: H = O(logN)
Worst case: (N-1)


Implememtation of an binary tree:

template <class T> class BTnode
{
    public:
    BTnode(const T& x, BTnode* L= nullptr, BTnode* R = nullptr):data(x), left(L), right(R){}
    ~BTnode(
        delete left;
        delete right;
    )
    const T& get_data() const { return data; }
    BTnode* get_left() const( return left;)
    BTnode* get_right() const (return right;)
    
    private:
        T data;
        BTnode* left;
        BTnode* right;

}

Traversal:

Inorder:
"left -> right"

void btree_inorder(BTnode<T>* root), void (*action) ((BTnode<T>* r))
{
    if (root){
        btree_inorder(root->get_left(),action)
        action(root);
        btree_inorder(root->get_right(),action)
    }
}

Pre-order:
"root -> left sub-tree -> right sub-tree"

void btree_preorder(BTnode<T>* root), void (*action) ((BTnode<T>* r))
{
    if (root){
        action(root);
        btree_preorder(root->get_left(),action)
        btree_preorder(root->get_right(),action)
    }
}

Post-order:
"left sub-tree -> right sub-tree -> root "


void btree_postorder(BTnode<T>* root), void (*action) ((BTnode<T>* r))
{
    if (root){
        action(root);
        btree_postorder(root->get_left(),action)
        btree_postorder(root->get_right(),action)
    }
} 

Binary Search Tree:

A Binary tree with following properties:

For every node x:

All the keys in its left sub-tree are smaller than the key value in node x.
All the keys in its right sub-tree are larger than the key value in node x.

The same set of values may be stored in different BSTs.

Average depth of a node on a BST is O(log N).
Maximum depth of a node on a BST is O(N).



4.20
Content:
1. Another Alternative BST Implementation
2. BST "Searching"
3. BST "Traversal"
4. find BST "extremum"
5. BST "insertion"
6. BST "deletion"

BST implementation:


template <class T> class BTnode
{
    private:
        T data;
        BTnode* left;
        BTnode* right;
}


Another Alternative Implementation

template <typename T> class BST
{
    private:
        struct BSTnode
        {
            T value;
            BST left; // Child as OBJECT ( previous we're using pointer )
            BST right;
            BSTnode(const T& x): value(x) {}

            BSTnode(const BSTnode&) = default;
            ~BSTnode(){}
        }

        BSTnode* root = nullptr;
    public:
    BST() = default;
    ~BST() {delete root;}
}

when ~BST(){delete root}

"delete" root --> "delete" left --> "delete" left's left --> ...
                                --> "delete" left's right --> ...
              --> "delete" right ... 

We're doing "delete" recursively!


BST(const BST& bst) 
{
    if (bst.is_empty())
     return;
    root = new BSTnode(*bst.root) 
    // What is happened here:
        T.value = (*bst.root).value;
        left = (*bst.root).left // We're calling the copy constructor recursively!
        right = (*bst.root).left // We're calling the copy constructor recursively!
    since We're using "new" , and all BSTnode's data member are Object (Not Pointer), 
                                                                    this is Deep Copy!
}

We implements BST as an Object -> Static Memory allocation



Other member function:

bool is_empty() const { return root == nullptr;}

bool contains(const T& x) const;

BST "Searching":

// Binart Search:

// Base case:
if tree is "empty":
    "not founded"
else if root.value = value:
    "founded!"

// recursive call:
else if larger then: 
    go "right"
else smaller then: 
    go "left"


bool BST<T>::contains(const T& x) const
{
    if (is_empty())
        return false;
    if (root->value == x)
        return true;
    else if(x < root -> value)
        return root->left.contains(x)
    else 
        return root->right.contains(x)
}



void print(int depth = 0) const;

BST "Traverse":

template <typename T>

"inorder" Leftmost -> Rightmost:

void BST<T>:: print(int depth) const
{
    if (is_empty()) return;

    root->right.print(depth+1);

    for (int j = 0 ; j < depth ; j++)
        cout << '\t' ;
    cout << root->value <<endl; 

    root->left.print(depth) + 1;
}





const T& find_max() const;
const T& find_min() const;

find BST "extremum"

since "this" and "this->root->right/left" are both "BST" class:
we can access find_min(); on both of them "move down" the tree Iteratively ( No need recursively);

const T& BST<T>::find_min() const{
    cosnt BSTnode* node = root 
    while(!node->left.is_empty())
        node = node->left.root;
    return node;
}

const T& BST<T>::find_max() const{
    cosnt BSTnode* node = root 
    while(!node->right.is_empty())
        node = node->right.root;
    return node;
}


void insert(constT&);

BST "insertion"

void BST<T> insert(constT& x);
{
    if(is_empty())
        root = new BSTnode(x);
    else if (x < root->value)
        root-> left.insert(x);
    else if (x > root->value)
        root-> right.insert(x);
    else
        ; // optional, actually will not end up at this branch
}


void delete(constT&);

BST "deletion":

Case 1: Delete a Node with no child:

just delete it!


Case 2: Delete a Node with 1 child:

"A -> B -> C "

We delete B and connect A, C --> "A -> C"


Case 3 : Delete a Node with 2 childs:

find Min(leftmost BSTnode) in its right subtree;

swap Min and this

recursively "delete" this

Implementation:

void BST<T>:: remove (const T&x)
{
    if (is_empty())
        return;

    if (x < root-> value)
        root-> left.remove(x);
    else if ( x > root->value)
        root->right.remove(x);

    else if (root->left.root && root->right.root)
    {
        root->value = root->right.find_min().value;
        root->right.remove(root->right.find_min());
    }
    else
    {
        BSTnode* deletingNode = root;

        // Since our destructor delete root recursively (we will alse delete right/left),
        //   We need to set left/right to nullptr in advance
        root = (root->left.is_empty()) ? root->left.root: root->right.root;
    
        deletingNode->left.root = deletingNode->right.root = nullptr;
        delete deletingNode;
    }
}