Tree & BST

우창민·2023년 10월 18일

자료구조

목록 보기

3/4

Tree(비선형자료구조)

Tree란 무엇인가?

계층적인 자료를 나타내는데 자주 사용되는 자료 구조
부모노드가 0개 이상의 자식 노드를 가질 수 있음
한 노드에서 출발하여 다시 자기 자신의 노드로 돌아오는 순환구조를 가질수 없음.

Tree 사용처?

계층적 관계를 표현하는데 용이하다.
최대/최소 힙
우선 순위 큐

Heap

많은 자료 중 우선순위가 가장 높은 요소를 빠르게 가져오기 위해 사용

Heap이란?

완전 이진 트리의 일종으로
부모노드가 항상 자식노드보다 우선수위가 높은 속성을 만족하는 트리구조

위의 두 상태가 만족되면 Heap상태를 만족한다! 라고 말함. ->우선순위에 따라 정렬이 되어있다.

힙에서는 중복된 값을 허용한다.

힙의 삽입/삭제

힙에 새로운 데이터가 들어왔을 때 일어나는 순서
1. 힙의 가장 마지막 단에 데이터를 추가
2. 해당 데이터가 올라갈 수 있을때 까지 올림 -> 부모보다 우선순위가 낮을때 까지.
힙에 데이터를 제거했을 때 일어나는 순서
1. 우선순위가 높은 노드를 빼고난 후 가장 마지막 데이터와 교체
2. 트리 형태 유지 이후 자식들과의 비교를 통해 우선순위 설정.

힙의 구현

완전 이진트리를 사용해 배열에 저장하는 방식을 사용할 수 있다. 인덱스의 개념은 아니지만 간단한 산수 연산으로 자식의 위치로 바로갈 수 있다.

구현

-> PriorityQueue

internal class PriorityQueue<TElement, TPriority>{
	private struct Node{
    	public TElement Elemnet;
        public TPriority Priority;    
    }
    private List<Node> nodes;
    private IComparer<TPriority> comparer;
    
    public PriorityQueue(){
    	this.nodes = new List<Node>();
        this.comparer = Comparer<TPriority>.Default;
    }
    public int Count{get {return nodes.Count;}}
    public IComparer<TPriority> Comparer{get {return comparer;}}
    
    public void Enqueue(TElemnet element, TPriority priority){
    	Node newNode = new Node(){Element = element, Priority = priority};
        PushHeap(newNode);
    }
    private void PushHeap(Node newNode){
    	nodes.Add(newNode);
        int newNodeIndex = nodes.Count -1;
        
}

BinarySearchTree(BST)

이진탐색 트리?

이진속성과 탐색 속성을 적용한 트리.
이진탐색을 통해 탐색 영역을 절반으로 줄여가며 탐색 가능
이진 : 부모노드는 최대 2개의 자식노드를 가질 수 있음
탐색 : 자식의 노드보다 작은 값들은 왼쪽, 큰 값들은 오른쪽에 위치

Big-O

접근 : O(logN)
탐색 : O(logN)
삽입 : O(logN)
삭제 : O(logN)

이진 탐색의 주의점?

이진 탐색 트리의 노드들이 한쪽 자식으로만 추가되는 불균형 발생 가능
이 경우 탐색영역이 절반으로 줄여지지 않기 때문에 시간복잡도 증가
이러한 현상을 막기 위해 자가균형기능을 추가한 트리의 사용이 일반적이다.
-> 해결방법으로 Red-Black Tree / AVL Tree 등을 통해 불균형 상황을 파악함.
이중 AVL트리의 경우 회전을 이용하여 불균형 상황을 해결하는데 root에서 leaf까지의 depth를 왼쪽 오른쪽으로 각각 비교하여서 depth가 작은쪽으로 회전을 시킴.

트리 순회

트리는 비선형 자료구조로 반복자의 순서에 대해 정의하는데 규칙을 정해야함.

전위 순회 : 노드, 왼쪽, 오른쪽
중위 순회 : 왼쪽, 노드, 오른쪽 <- 이진탐색트리에서 사용시 오름차순으로 데이터정렬
후위 순회 : 왼쪽, 오른쪽, 노드

구현?

internal class BinarySearchTree where T : IComparable{
private Node root;
public BinarySearchTree(){
this.root = null;
}
public bool Add(T item)
{
Node newNode = new Node(item, null, null, null);

		if (root == null)
		{
			root = newNode;
			return true;
		}

		Node current = root;
		while (current != null)
		{
			if (item.CompareTo(current.Item) < 0)
			{
				if (current.Left != null)
				{
					current = current.Left;
				}
				else
				{
					current.Left = newNode;
					newNode.Parent = current;
					break;
				}
			}
			else if (item.CompareTo(current.Item) > 0)
			{
				if (current.Right != null)
				{
					current = current.Right;
				}
				else
				{
					current.Right = newNode;
					newNode.Parent = current;
					break;
				}
			}
			else
			{
				return false;
			}
		}
		return true;
	}

	public bool Remove(T item)
	{
		Node findNode = FindNode(item);
		if (findNode == null)
		{
			return false;
		}
		else
		{
			EraseNode(findNode);
			return true;
		}
	}

	public void Clear()
	{
		root = null;
	}

	public bool TryGetValue(T item, out T outValue)
	{
		Node findNode = FindNode(item);
		if (findNode == null)
		{
			outValue = default(T);
			return false;
		}
		else
		{
			outValue = findNode.Item;
			return true;
		}
	}

	private Node FindNode(T item)
	{
		if (root == null)
			return null;

		Node current = root;
		while (current != null)
		{
			if (item.CompareTo(current.Item) < 0)
			{
				current = current.Left;
			}
			else if (item.CompareTo(current.Item) > 0)
			{
				current = current.Right;
			}
			else
			{
				return current;
			}
		}

		return null;
	}

	private void EraseNode(Node node)
	{
		if (node.HasNoChild)
		{
			if (node.IsLeftChild)
				node.Parent.Left = null;
			else if (node.IsRightChild)
				node.Parent.Right = null;
			else
				root = null;
		}
		else if (node.HasLeftChild ^ node.HasRightChild)
		{
			Node parent = node.Parent;
			Node child = node.HasLeftChild ? node.Left : node.Right;

			if (node.IsLeftChild)
			{
				parent.Left = child;
				child.Parent = parent;
			}
			else if (node.IsRightChild)
			{
				parent.Right = child;
				child.Parent = parent;
			}
			else
			{
				root = child;
				child.Parent = null;
			}
		}
		else
		{
			Node nextNode = node.Right;
			while (nextNode.Left != null)
			{
				nextNode = nextNode.Left;
			}
			node.Item = nextNode.Item;
			EraseNode(nextNode);
		}
	}

	private class Node
	{
		private T item;
		private Node parent;
		private Node left;
		private Node right;

		public Node(T item, Node parent, Node left, Node right)
		{
			this.item = item;
			this.parent = parent;
			this.left = left;
			this.right = right;
		}

		public T Item { get { return item; } set { item = value; } }
		public Node Parent { get { return parent; } set { parent = value; } }
		public Node Left { get { return left; } set { left = value; } }
		public Node Right { get { return right; } set { right = value; } }

		public bool IsRootNode { get { return parent == null; } }
		public bool IsLeftChild { get { return parent != null && parent.left == this; } }
		public bool IsRightChild { get { return parent != null && parent.right == this; } }

        public bool HasLeftChild { get { return left != null; } }
        public bool HasRightChild { get { return right != null; } }
        public bool HasNoChild { get { return !HasLeftChild && !HasRightChild; } }
		public bool HasBothChild { get { return HasLeftChild && HasRightChild; } }
	}
}

}