0401 이진탐색트리Binary Search Tree
2021. 4. 1. 18:24ㆍC#/자료구조
왼쪽 노드의 값이 루트 노드의 값보다 작고, (root>node)=left
오른쪽 노드의 값이 루트 노드의 값보다 큰 값을 갖는 트리 (root<node)=right
모든 노드의 키가 unique 하다는 정의를 포함시키는 것이 일반적
중복을 허용하는 트리의 경우 왼쪽 서브트리는 루트보다 작거나 같고,
오른쪽 서브트리는 루트보다 크거나 같다
public class BSTNode
{
public int data;
public BSTNode left;
public BSTNode right;
public BSTNode(int data)
{
this.data = data;
}
}public class BinarySearchTree
{
private BSTNode root;
public BinarySearchTree()
{
}
public void Add(int data)
{
if (root == null)
{
this.root = new BSTNode(data);
return;
}
//비교
var node = this.root;
while (node != null)
{
//추가 하려는 값과 노드의 값을 비교
var result = data.CompareTo(node.data);
if (result == 0)
{
//같다
throw new ApplicationException("duplicate");
}
else if (result < 0)
{
//작다
if (node.left == null)
{
node.left = new BSTNode(data);
break;
}
else
{
node = node.left;
}
}
else
{
//크다
if (node.right == null)
{
node.right = new BSTNode(data);
break;
}
else
{
node = node.right;
}
}
}
}
}public class App
{
public App()
{
BinarySearchTree tree = new BinarySearchTree();
tree.Add(10);
}
}
public class BinarySearchTree
{
private BSTNode root;
public BinarySearchTree()
{
}
public void Add(int data)
{
if (root == null)
{
this.root = new BSTNode(data);
return;
}
//비교
var node = this.root;
while (node != null)
{
//추가 하려는 값과 노드의 값을 비교
var result = data.CompareTo(node.data);
if (result == 0)
{
//같다
throw new ApplicationException("duplicate");
}
else if (result < 0)
{
//작다
if (node.left == null)
{
node.left = new BSTNode(data);
break;
}
else
{
node = node.left;
}
}
else
{
//크다
if (node.right == null)
{
node.right = new BSTNode(data);
break;
}
else
{
node = node.right;
}
}
}
}
public bool Search(int data)
{
var node = this.root;
while (node != null)
{
//넣은 값과 노드 값을 비교
var result=data.CompareTo(node.data);
if (result == 0)
{
//넣은 값과 노드 값이 같으면 true
return true;
}
else if (result > 0)
{
//넣은 값>노드면 오른쪽
node = node.right;
}
else if (result < 0)
{
//넣은 값<노드면 왼쪽
node = node.left;
}
}
//다 돌았는데도 없으면
return false;
}
} public class App
{
public App()
{
BinarySearchTree tree = new BinarySearchTree();
tree.Add(10);
var result=tree.Search(10);
Console.WriteLine(result);
}
}
재귀함수로 구현한 search 메서드
public class BinarySearchTree
{
private BSTNode root;
public BinarySearchTree()
{
}
public void Add(int data)
{
if (root == null)
{
this.root = new BSTNode(data);
return;
}
//비교
var node = this.root;
while (node != null)
{
//추가 하려는 값과 노드의 값을 비교
var result = data.CompareTo(node.data);
if (result == 0)
{
//같다
throw new ApplicationException("duplicate");
}
else if (result < 0)
{
//작다
if (node.left == null)
{
node.left = new BSTNode(data);
break;
}
else
{
node = node.left;
}
}
else
{
//크다
if (node.right == null)
{
node.right = new BSTNode(data);
break;
}
else
{
node = node.right;
}
}
}
}
//재귀함수
public bool SearchRecursive(int data)
{
return SearchRecursive(this.root, data);
}
public bool SearchRecursive(BSTNode node, int data)
{
var result=data.CompareTo(node.data);
if (result == 0)
{
return true;
}
return SearchRecursive(node.left, data) || SearchRecursive(node.right, data);
}public class App
{
public App()
{
BinarySearchTree tree = new BinarySearchTree();
tree.Add(10);
//var result=tree.Search(10);
var result = tree.SearchRecursive(10);
Console.WriteLine(result);
}
}
자식 노드가 1개면
부모 노드에서 삭제할 노드 자리에 왼쪽/오른쪽 자식 노드를 대입한다.
자식 노드가 2개면
왼쪽 서브트리 중 가장 큰 수/오른쪽 서브트리 중 가장 작은 수를
삭제할 노드 자리에 옮긴다.
오른쪽 서브트리의 가장 작은 값= minNode
public class BinarySearchTree
{
private BSTNode root;
public BinarySearchTree()
{
}
public bool Remove(int data)
{
var node = this.root;
BSTNode prev = null;
while (node != null)
{
var result = data.CompareTo(node.data);
if (result == 0)
{
break;
}
else if (result < 0)
{
prev = node;
node = node.left;
}
else
{
prev = node;
node = node.right;
}
}
if (node == null) return false;
//노드를 찾음 (삭제 진행)
//1.왼쪽 노드 or 오른쪽 노드가 없는 경우
if (node.left == null && node.right == null)
{
//부모에서 떼어내기
if (prev.left == node)
{
prev.left = null;
}
else
{
prev.right = null;
}
//찾으려고 하는 노드를 null로 만듦.
node = null;
}
//2.노드의 왼쪽/오른쪽이 있으면
else if (node.left != null || node.right != null)
{
//왼쪽/오른쪽 둘 하나만 있는 경우
var child = node.left != null ? node.left : node.right;
if (prev.left == node)
{
prev.left = child;
}
else
{
prev.right = child;
}
}
else
{
//왼쪽 오른쪽 둘 다 있는 경우
//검색된 노드 저장
var pre = node;
//검색된 노드의 오른쪽 노드 저장
var min = node.right;
while (min.left != null)
{
pre = min;
min = min.left;
}
node.data = min.data;
if (pre.left == min)
{
pre.left = min.right;
}
else
{
pre.right = min.right;
}
}
return true;
}
public class App
{
public App()
{
BinarySearchTree tree = new BinarySearchTree();
tree.Add(30);
tree.Add(25);
tree.Add(35);
tree.Add(21);
tree.Add(27);
tree.Add(28);
//var result=tree.Search(10);
//var result = tree.SearchRecursive(10);
var result = tree.Remove(25);
Console.WriteLine(result);
}
}'C# > 자료구조' 카테고리의 다른 글
| 0402 그래프 (0) | 2021.04.02 |
|---|---|
| 0402 이진 탐색 트리 재귀 함수로 중위순회 (0) | 2021.04.02 |
| 0401 연결리스트를 사용해 이진트리 만들고 Postorder Traversal (Iterative) 복습 (0) | 2021.04.01 |
| 0401 연결리스트로 이진트리 만들고 중위순회 하기 (Iterative방식) 복습 (0) | 2021.04.01 |
| 0401 연결리스트로 구현한 이진트리 InorderTraversal (Iterative) 복습 (0) | 2021.04.01 |