응애맘마조

이진탐색트리에서 사용했던 노드 추가 및 삭제와 탐색을 ImGui에서 하는 것이 과제였습니다. #include "framework.h" bool GameObject::RenderHierarchy() { ImGui::PushID(this); if (ImGui::TreeNode(name.c_str())) { if (ImGui::IsItemToggledOpen() or ImGui::IsItemClicked()) { GUI->target = this; } if (ImGui::Button("addChild")) { ImGui::OpenPopup("childName"); } if (ImGui::BeginPopup("childName")) { static char childName[32] = "None"; ImGui:..

조사했던 과제처럼 이진탐색트리에 대해서 강의했었습니다. 일단 이진탐색트리는 둘 중에 한 곳으로 내려갑니다. 이진법을 생각하면 0과 1로 2가지만 되어있는 것처럼 이진탐색트리도 둘 중 한 곳만 쓰기 때문에 이진탐색트리라는 이름이 붙었습니다. 이진탐색트리에도 종류가 많지만 완전이진트리에 대해 적어보겠습니다. 먼저 완전이진트리는 좌우 반씩 쪼개서 내려갈 수 있습니다. 가장 위에 있는 노드가 루트 노드이고 거기서부터 내려갈 때마다 탐색을 해야 되는 노드의 수는 절반 이하로 줄어들게 됩니다. 그래서 최대 레벨 도달 수는 최하단에 있는 노드가 됩니다. 그렇게 균형 잡힌 트리의 탐색에 유리한 구조가 자료구조 중의 map과 set입니다. 그럼 map과 set에 대해 알아보겠습니다. 먼저 map은 검색, 삽입, 삭제가 ..

주의 : 해당 게시물에서 작성될 내용은 과제를 해결하기 위해 출처의 내용을 그대로 작성한 부분이 많으며 일절 광고나 수익 창출 목적으로 쓰인 것이 아님을 밝힙니다. 이진탐색트리는 이진 탐색과 연결리스트를 결합한 자료구조입니다. 이진 탐색의 효율과 자료 입력과 삭제가 가능합니다. 구성은 자식 노드가 2개로 구성된 트리로 볼 수 있습니다. 특징으로는 각 노드에 중복되지 않는 키가 있고 루트 노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드로 되어있고 반대로 오른쪽은 해당 노드보다 큰 키를 갖고 있습니다. 또한 좌우 서브트리도 모두 이진 탐색으로 되어있어야 합니다. 연산은 트리의 높이가 h일 때, O(h)의 복잡도를 가지게 됩니다. 탐색 과정은 좌측에 작은 키, 우측에 큰 키로 되어있는 것을 ..