190918 data structure - 2

zenibako.lee

8 min readSep 18, 2019

TREE, 2진트리(2진검색트리)

먼저 트리구조에 대해 알아보자.

DOM을 보면 바로 알 수 있다.

DOM은 document의 논리적 구조를 보여준다.

이처럼 ‘계층’을 구분하는 데이터 구조를 사용하고 싶을 때, 트리구조를

사용하게 된다.

<!DOCTYPE html>
  <html>
  <head>
    <title>My Page</title>
  </head>
  <body>
    <h1>Mobile OS</h1>
    <ul>
      <li>Android</li>
      <li>iOS</li>
    </ul>
  </body>
</html>

위 DOM객체를 도식화하면 아래와 같다.

최상위 element인 Document를 ‘root’라고 칭한다.

그리고 root에서 특정 element까지의 화살표(edge) 갯수가 높이(height)이다.

그렇다면
2진트리란 무엇인가?

한 node에서 뻗어나오는 가지(edge)가 최대 2개인 트리를 의미한다.

이런식으로 말이다.

루트노드를 기준으로, 왼쪽의 자식노드는 부모노드보다 작은 value를 갖고, 오른쪽 자식노드들은 부모노드보다 큰 value를 갖는다.

기본적으로 숫자맞추기 UP/DOWN 게임의 최적화 전략과 동일하다.

특정 숫자 UP/DOWN/CORRECT 를

통해 TARGET보다 크면 대상 노드 오른쪽 트리에서 검색,

작으면 왼쪽 트리에서 검색, 과 같은 방식이다.

어떠한 메소드들이 필요할까?

CRUD 라는 것을 가져 올 수 있을 것 같다.

CREATE/READ/UPDATE/DELETE

CREATE(삽입)

삽입을 하기 위해서는, 삽입 할 노드의 위치를 탐색해주어야 한다.

ROOT node부터 비교를 통해, 비어있는 leaf에 도달하면, 그곳이 삽입할 위치가 된다.

2. DELETE(삭제)

삭제역시, value를 기준으로 해당 삭제할 노드의 위치를 탐색(1)

해당 노드를 삭제(2), 노드가 리프(단말노드)가 아닐 경우, 삭제한 노드의 자식에 해당하는 자식노드들 다른 노드에 입양시켜주기(3)이다.

자식노드가 없는 경우- 삭제 후 부모 노드의 link value를 null값으로 초기화.

자식노드가 있는 경우,

자식이 1명일 때와, 2명일 때 방법이 달라진다.

한명일 때는, 본인은 사라지고, 조부모에게 연결시켜주면 된다.

자식이 두 명일 때?

앞의 방법과 동일하게 진행되면, 조부모는 자식을 세명 가질 수 없으므로 불가능하다.

두가지 방법이 있는데, 첫째 자식(피삭제 노드보다 작은 노드중에 제일 큰 노드)혹은 둘째 자식(피삭제 노드보다 큰 노드중 가장 작은노드)로 부모의 위치를 대신하는 것이다.

둘째 자식으로 대체하는 경우를 생각해보자.

삭제할 부모노드에 x표시를 해보았다. 자식이 둘이다.

자식중에 부모보다 큰 오른쪽 자식으로 부모노드를 대체한다.

이때, 둘 째 자식은 중복된 상태이다.

이제 중복된 자식을 다시 방금과 같은 방식으로 자식의 둘째자식(보라색)

을 덮어씌우고, 자식이 없는 원본(보라색)을 삭제하면 완료된다.

Graph structure

비선형 자료구조의 일종.

그래프는 트리와 같이 노드와 엣지로 구성이 되어 있다.

graph의 경우 node를 vertices, edge를 arc라고 부른다.

들어오는 아크 개수를 in-degree, 나가는 아크 개수를 out-degree라고 함.

방향성 유무에 따라 방향그래프,무방향그래프로 나뉨.

무방향/방향 그래프

트리와의 가장 큰 차이점은,

트리의 노드는 in-degree가 한 개 뿐이지만,
그래프의 버텍스는 여러개가 들어올 수 있다.

모든 버텍스가 서로 연결된 경우, ‘완전그래프’라고 한다.

그래프를 표현하는 방식은 1. 2차원배열 2.연결리스트 방식이 있다.

2차원 배열방식은 vertices²의 공간을 차지한다.

이러한 그래프를 2차원배열로 나타내면

vertices의 이름은 보기위해 써놓은 것이고, 연결 상황만 나타내는 크기는 vertices개수(4)² , 16이다.

연결리스트를 사용해서 표현을 해보면

버텍스 + 아크 개수의 합의 개수에 해당하는 메모리를 차지한다.
(! 무방향 아크는 선 하나에 2개로 카운트)

v+2a = 무방향 그래프 연결리스트의 복잡도(o)

따라서,무방향 그래프에서는 v( vertices)²<v+2a(arc) 인 경우에 연결리스트 방식을 사용하는 것이 좋다.

v²<v+2a -> a>1/2(v²-v) 의 범위를 도식화해보면

arc와 vertices의 개수가 빗금친 범위 일 때는, 2차원배열을,

나머지 경우에는 연결리스트를 사용하는 것이 효과적이다.

위에서 예제는 v = 4, 2a = 8, 16<4+16 이므로, 연결리스트가 효과적이 맞다.

방향그래프의 경우에는 v2<v+a 일 때, 연결리스트를, 아니면 2차원배열료 표현하는 것이 좋다.

어떤식으로 동작할지? (psuedo code)

리스트들의 집합인 그래프 객체는 헤더 버텍스의 집합이다.
그래프객체선언, 버텍스배열 선언, 그래프객체에 버텍스를 다 넣어줌.(헤더),
각 리스트는 헤더버텍스에서 출발하여 여러 노드들을 순차적으로 연결한다. (각각 헤더버텍스에 이제 링크로 연결된 버텍스를 이어줌)
충돌 및 수정의 경우, 연결리스트의 메소드와 동일한 방식으로 작동.

Hash tables

what is opening addressing?

해시 테이블은 어떤 특정 값을 받으면 그 값을 해시 함수에 통과시켜 나온 인덱스(index)에 저장하는 자료구조이다.

직접주소테이블이 그 중 하나인데,

입력받은 value를 key로 table에 저장하는 것이다,

결국 10은 10이라는 index에 저장되고, 다음에 100이라는 input이 있으면 100이라는 index로 저장이 된다.

문제는 무엇이냐면, 현재 0~100까지의 인덱스를 전부 사용하면서 데이터 2개만을 저장하면서 100개의 메모리를 잡고 있다.

즉 ‘값은 없지만, 메모리 공간은 할당이 된 상태’이다.

hash함수를 통해 이 문제를 개선하려 하는데,

예를 들어, 5개 까지만의 공간을 미리 선언시에 사이즈로 잡고,

(! 따라서 용량 max시 resize하는 기능이 필요하다)

어떠한 해시함수를 통해 인덱스(hash code)를 최대 4까지만 부여하여 자료를 저장하는 것이다.

이 때, 해시함수는 이미 데이터를 담고있는 인덱스를 의도하지 않을 때에는 부여하면 안된다.

이 방법들은

이렇게 나눠진다.

1 -선형탐사법(linear probing)

선형탐사법은 중복된 index를 받았을 시, 미리 정한 n만큼의 추가된 index로 이동하여 저장을 시도하는 방식이다.

2 -제곱탐사법(quadratic probing)

제곱탐사법은 선형탐사법과 기본적으로 유사하지만, 탐사(이동)하는 폭이 제곱으로 늘어난다.

첫번째 충돌이 나면 n, 이동한 인덱스에도 값이 있으면 (n+1)²이동, 이런식이다.

3 -이중해싱(double hashing probing)

해시함수를 두개를 가져가는 방식인데,

예를들어, 최초위치를 선택하는 해시펑션과, 충돌시 다음 인덱스를 찾는 해시펑션을 최대한 중복이 되지 않게 구성하는 것이다.

이 때 팁은, 해시함수에 사용되는 상수는 ‘소수’를 사용하는 것이다. 소수는 배수계산에서 중복이 최대한 안되는 아름다운 힘을 갖고 있으니까..?

2. 분리연결법(separate chaining)

분리연결법은 각각의 bucket을 linked list로 만들어서,
collision이 발생하면, 해당 bucket의 linkedList에 추가,연결하는 방식이다.
value그 자체가 아니라, value와 다음 node를 가르키는 주소를 포함한 node단위를 넣는 것이다.

key값을 구해, 해시테이블에 삽입, 데이터가 이미 있는경우 링크드 리스트로 노드간 연결.