[Data Structrue (Java)] Tree (4) - Binary Search Tree Map

https://crane206265.tistory.com/89

[Data Structure (Java)] Set

https://crane206265.tistory.com/84

[Data Structure (Java)] Tree (3) - Binary Search Tree

끝일 줄 알았지만, 다시 가져온 BST. 마저 이어서, 다만 이번에는 Map ADT로 구현해봅시다.

---

Recall) Binary Search Tree (BST)

: a binary tree in symmetric order

(no need to be complete)

 

* symmetric order : every node's key is

: larger than all keys in its left subtree

: smaller than all keys in its right subtree

---

BST Map API

API of BSTMap<Key, Value>

methods	explanation
boolean isEmpty()	return if tree is empty
int getSize()	return the # of nodes of the tree
Value get(Key key)	return the value associated with the give key (if it does not exist : return null)
void put(Key key, Value val)	if key exist : replace the associated value to the given value else : add the given entry (key, val)
void delete(Key key)	delete the entry with the given key
void deleteMin()	delete the entry with the smallest key
Key min()	return the smallest key
int height()	return the height of BST
void inorder()	excute and print inorder traversal
void preorder()	excute and print preorder traversal
void postorder()	excute and print postorder traversal

 

* BST :  reference to the root Node

Node class
- Key key
- Value val
- Node left : reference to the left subtree - initiallized as null
- Node right : reference to the right subtree - initiallized as null
- int size : # of nodes in the subtree rooted at itself

Hibbard Deletion : Algorithm to deletion in BST
Goal : delete a node T with key K

- case 0 : node T has 0 children
delete T -> setting parent link to null

- case 1 : node T has 1 children
delete T -> replace parent link to its child

- case 2 : node T has 2 children
find the successor of T : X -> delete X (in T's right subtree) -> replace T to X -> set the left link of X to T.left

* successor of a node X : the node with the smallest value that is larger than value of X
* predecessor of a node X : the node with the largest value that is smaller than value of X

---

BST Map Implementation

BSTMap<Key, Value> implementation : for String keys

import java.lang.Comparable;

public class BSTMap<Key extends Comparable<Key>, Value> {
    //----- constructor & instance variable -----
    private Node root;

    private class Node {
        private Key key;
        private Value val;
        private Node left, right;
        private int size;

        public Node(Key key, Value val, int size) {
            this.key = key;
            this.val = val;
            this.size = size;
        }
    }

    public BSTMap() {

    }


    //----- methods -----
    public boolean isEmpty() {
        return size() == 0;
    }

    public int size() {
        return size(root);
    }

    private int size(Node x) {
        if(x == null) return 0;
        return x.size;
    }

    public Value get(Key key) {
        Node x = root;
        while(x != null) {
            int cmp = key.compareTo(x.key);
            if(cmp == 0) return x.val;
            else if(cmp > 0) x = x.left;
            else if(cmp < 0) x = x.right;
        }
        return null;
    }
    
    public void put(Key key, Value val) {
        root = put(root, key, val);
    }

    private Node put(Node x, Key key, Value val) {
        if(x == null) return new Node(key, val, 1);
        int cmp = key.compareTo(x.key);
        if(cmp == 0) x.val = val;
        else if(cmp > 0) x.left = put(x.left, key, val);
        else if(cmp < 0) x.right = put(x.right, key, val);
        x.size = size(x.left) + size(x.right) + 1;
        return x;
    }

    public void delete(Key key) {
        root = delete(root, key);
    }

    private Node delete(Node x, Key key) {
        if(x == null) return null;
        int cmp = key.compareTo(x.key);
        if(cmp > 0) x.left = delete(x.left, key);
        else if(cmp < 0) x.right = delete(x.right, key);
        else {
            if(x.right == null) return x.left;
            if(x.left == null) return x.right;

            Node t = x;
            x = min(x.right);
            x.right = deleteMin(t.right);
            x.left = t.left;
        }
        x.size = size(x.left) + size(x.right) + 1;
        return x;
    }

    public void deleteMin() {
        root = deleteMin(root);
    }    

    private Node deleteMin(Node x) {
        if(x.left == null) return x.right;
        x.left = deleteMin(x.left);
        x.size = size(x.left) + size(x.right) + 1;
        return x;
    }

    public Key min() {
        return min(root).key;
    }

    private Node min(Node x) {
        if(x.left == null) return x;
        else return min(x.left);
    }

    public int height() {
        return height(root);
    }

    private int height(Node x) {
        if(x == null) return -1;
        else return Math.max(height(x.left), height(x.right)) + 1;
    }

    public void inorder() {
        inorder(root);
    }

    private void inorder(Node x) {
        if(x == null) return;
        inorder(x.left);
        System.out.print(x.key + " ");
        inorder(x.right);
    }

    public void preorder() {
        preorder(root);
    }

    private void preorder(Node x) {
        if(x == null) return;
        System.out.print(x.key + " ");
        preorder(x.left);
        preorder(x.right);
    }

    public void postorder() {
        postorder(root);
    }

    private void postorder(Node x) {
        if(x == null) return;
        postorder(x.left);
        postorder(x.right);
        System.out.print(x.key + " ");
    }
}

 

Running Time Analysis
: depends on the tree shape
    --> tree shape : depends on order of insertion
         - best case : balanced
         - worst case : ascending / descending order -> like linked list

methods get(), put(), delete() : O(h)
* h : height of the BST
- worst case : h = O(n)
- best case : h = O(log n)