Module 5 - BST Operations

The best case, O(1), of searching in a BST, regardless of the size of the tree, would be if the data we searched for is at the root node.

AVG: O(log n)

worst: O(n)

ADD

1. data 를 찾을시 search 는 성공하지만 add 는 추가하지 않는다(이미 있으니까)

2. node 가 null, 즉 비어있으면 search는 실패하지만 add 는 그곳에 데이터를 추가한다

위에부터 차근차근 내리면 된다

## child 가 null 인걸 확인하고 add 하는것이지 null node 까지 직접 가지는 않는다

• curr = null 로 base case 확인, 데이터가 없을수 있으니까 
• data 가 현재 curr 보다 작으면 왼쪽 크면 오른쪽으로 가고 recursion 
• 마지막에 return curr 로 처음으로 돌아감

public void add(T data) {
    if (data == null) {
        throw new IllegalArgumentException("Cannot add null data.");
    }
    root = addHelper(data, root);
}
 */
private BSTNode<T> addHelper(T data, BSTNode<T> node) {
    if (node == null) {
        size++;
        return new BSTNode(data);
    } else if (data.compareTo(node.getData()) < 0) {
        node.setLeft(addHelper(data, node.getLeft()));
    } else if (data.compareTo(node.getData()) > 0) {
        node.setRight(addHelper(data, node.getRight()));
    }
    return node;
}

Remove

data 발견 = 제거, 발견 X =exception

child 가 업는 node 제거는 간단, 하지만 child 가 있으면 힘듬

제거되는 node 의 parent 와 child 를 연결한다

자, 그렇다면 root 를 remove 해야할땐 어떻게 해야할까? 

두가지 경우가 있는데 predecessor, successor

predecessor = root 보다 가장 가까운 작은수를 root 로 만든다 

successor = root 보다 가장 가까운 큰수를 root 로 만든다

base case 두가지

1. cur == null 즉 데이터가 없을때

2. data 를 찾았을때. 

그게 아니면 left right 로 recursion 을 돌린다.

data 를 찾았을시

child 가 없다면 return null

왼쪽이나 오른쪽에 child 가 있다면 return 하고

왼쪽 오른쪽 전부 child 가 있담면  predesessor successor 중에 메소드를 이용해서 successor, predesessor 을 찾은후 parent 와 연결시킨다 

public T remove(T data) {
        if (data == null) {
            throw new IllegalArgumentException("Cannot remove null data.");
        }
        // create dummy node reference to return data that was removed
        BSTNode<T> removeRef = new BSTNode(null);
        root = removeHelper(data, root, removeRef);
        size--;
        return removeRef.getData();
    }
    
private BSTNode<T> removeHelper(T data, BSTNode<T> node,
                                BSTNode<T> removeRef) {
    if (node == null) {
        throw new NoSuchElementException(data + " was not "
                + " found in the BST.");
    }
    //recurse until you reach the node
    if (data.compareTo(node.getData()) < 0) {
        node.setLeft(removeHelper(data, node.getLeft(), removeRef));
    } else if (data.compareTo(node.getData()) > 0) {
        node.setRight(removeHelper(data, node.getRight(), removeRef));
    } else {
        //if data is the same as node's data, delete this node
        //case 1 and 2: no child or one child
        if (removeRef.getData() == null) {
            //ensures dummy node's data is only changed once
            removeRef.setData(node.getData());
        }
        if (node.getLeft() == null) {
            return node.getRight();
        } else if (node.getRight() == null) {
            return node.getLeft();
        }
        //case 3: two children
        // get successor, swap data, delete old successor node
        node.setData(successor(node.getRight()));
        node.setRight(removeHelper(node.getData(), node.getRight(),
                removeRef));
    }
    return node;
}

private T successor(BSTNode<T> node) {
    T data = node.getData();
    while (node.getLeft() != null) {
        data = node.getLeft().getData();
        node = node.getLeft();
    }
    return data;
}

private BSTNode<T> predecessorHelper(BSTNode<T> node, BSTNode<T> child) {
    if (node.getRight() == null) {
        child.setData(node.getData());
        return node.getLeft();
    }
    node.setRight(predecessorHelper(node.getRight(), child));
    return node;
}

public boolean contains(int data) {
    return containsHelper(data, root);
}

private boolean containsHelper(int data, Node node) {
	if (node == null) {
		return false;
	} else if (data < node.data) {
		containsHelper(data, node.left);
	} else if (data > node.data) {
		containsHelper(data, node.right);
	} else {
		return true;
	}
}