[Binary Search Tree]

Binary Search Tree

 

부모 노드를 기준으로, 왼쪽 자식들은 부모 노드보다 값이 작으며, 오른쪽 자식 노드들은 부모 노드보다 값이 크다!

 

기본적인 Node java 코드

package binaryTree;

public class Node {
	private int key;
	private String data;
	private Node left;
	private Node right;
	private Node parent;
	public Node(int k, String d) {
        key = k;
        data = d;
        left = null;
        right = null;
	}
	public String getData() {return data;}
	public int getKey() {return key;}
	public Node getLeftChild() {return left;}
	public Node getRightChild() {return right;}
	public Node getParent() {return parent;}
	public void setLeftChild(Node n) {left = n;}
	public void setRightChild(Node n) {right = n;}
	public void setParent(Node n) {parent = n;}
}

BinarySearchTree를 구현하기위해 필요한 것

삽입 과정을 알아야 함

insertNode

st-lab.tistory.com

insert 과정 2가지

1. 사용자가 Comparator을 사용하여 정렬 방법을 BinarySearchTree 생성단계에서 넘겨받은 경우 (comparator가 null이 아닌 경우)

2. 클래스 내에 정렬 방식을 Comparable로 구현했거나 기본 정렬 방식을 따르는 경우 (comparator가 null인 경우)