ICS46 - Binary Search Tree

Binary Search Tree: Recursive Insert_Node

static TreeNode insert(KeyType key, ValueType value, TreeNode t);

Node * BSTree::insert_node(Node * t, string key){
    if(t == nullptr){
        return new Node(key);}

    if (key <  t->key){
        t->left = insert_node(t->left, key);
    }
    else if (key > t->key){
        t->right = insert_node(t->right, key);
    }
    return t;
}

• We will add to the tree depending on the value of the node is greater than or less than the parent node

  • Uses recursion

  • Inserts checks if nullptr

Binary Search Tree: Inserting in a Sorted order

O(N) (Would become a linked list)

Binary Search Tree: Inserting in a random order

O(Log n)

Binary Search Tree: Iterative Find_Node

Node * BSTree::find_node(Node * t, string key)

Node * BSTree::find_node(Node * t, string key){
    if(t == nullptr){
        return nullptr;}

    Node * current = t;
    while(current != nullptr){
        if(current->key == key){
            return current;
        }
        if(key < current->key){
            current = current->left;}
        else if(key > current->key){
            current = current->right;}
    }
    return nullptr;
}

Binary Search Tree: Find() in a Sorted order

O(N)

Binary Search Tree: Find() in a Random order

O(Log n)

Binary Search Tree: Recursive Remove_Node

Node * BSTree::delete_node(Node * t, string key)

Node * BSTree::delete_node(Node * t, string key){
    if(t == nullptr){return t;} 

    if (key < t->key)
        t->left = delete_node(t->left, key);
    else if (key > t->key){
        t->right = delete_node(t->right, key);
    }
    // key == t->key

    else {
        // Case 1: Node has one or no child
        if (t->left == nullptr || t->right == nullptr) {
            Node * child = t->left ? t->left : t->right;
            // NO CHILD CASE
            if (child == nullptr) {
                child = t;
                t = nullptr;
            } else { // ONE CHILD CASE
                *t = *child; // COPY DATA FROM CHILD
            }
            delete child;
        }
           // Case 2: Node has two children
        else {
	    // find min of right-subtree
            Node * succ = left_most(t->right);
	    // swap the succ and the one you are deleting 
            swap(t->key, succ->key);
            // Deltete node 
            t->right = delete_node(t->right, key);
        }
    }
    return t;
}

3 Cases:

• We are removing a leaf node → Remove a single node

• We are removing a node w/ a single child → Replace with child node

• We are removing a node w/ two children → swap with minimum of the right subtree and delete

Binary Search Tree: Remove() in a Random order

O(Log n)

Binary Search Tree: Remove() in a Sorted order

O(1)

Pre-Order Traversal

void BST::pre_order_print(ostream & out, Node * t){
    if(t == nullptr){
        return;
    }
    out << t-> key << " ";
    pre_order_print(out, t->left);
    pre_order_print(out, t->right);
}

Root → Left → Right

In-Order Traversal

void BST::in_order_print(ostream & out, Node * t){
    if(t == nullptr){
        return;
    }
    in_order_print(out, t->left);
    out << t-> key << " ";
    in_order_print(out, t->right);
}

Left → Root → Right

Post Order Traversal

void BST::post_order_print(ostream & out, Node * t){
    if(t == nullptr){
        return;
    }
    post_order_print(out, t->left);
    post_order_print(out, t->right);
    out << t-> key << " ";
}

Left → Right → Root

AVL Tree: Insert()

Node * AVLTree::insert_node(Node * t, string key)

Node * AVLTree::insert_node(Node * t, string key){
    if(t == nullptr){
        return new Node(key);}
    if (key <  t->key){
        t->left = insert_node(t->left, key);
    }
    else if (key > t->key){
        t->right = insert_node(t->right, key);
    }
    set_height(t);
    return rebalance(t);
}

• Same as BST, we just need to call rebalance

When do we use recursion for bst?

AVL Trree: Inserting in a Sorted order

O(Log N)

AVL Trree: Inserting in a Random order

O(Log N)

AVL Tree: Rebalance()

Node * AVLTree::rebalance(Node * t){
    set_height(t);
    int balance = get_balance(t);
    if (balance > 1) {
        if (get_balance(t->left) < 0){
            t->left = left_rotate(t->left);
        }
        return right_rotate(t);
    } else if (balance < -1) {
        if (get_balance(t->right ) > 0){
            t->right = right_rotate(t->right);
        }
        return left_rotate(t);
    }
    return t;
}

• We check the value of get_balance to see if our graph is skewed to the left or right

  • Then we perform a left or right rotate accordingly

Left Rotate

Node * AVLTree::left_rotate(Node * x){
    Node * y = x->right;
    Node * T2 = y->left;
    y->left = x;
    x->right = T2;
    set_height(x);
    set_height(y);
    return y;  
}

Right Rotate

Node * AVLTree::right_rotate(Node * y){
    Node * x = y->left;
    Node * T2 = x->right;
    x->right = y;
    y->left = T2;
    set_height(y);
    set_height(x);
    return x;     

}