시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
이 기사에서 우리는 이진 트리에 삽입. 우리는 이미 BFS 이전 기사에서 이진 트리에 데이터를 삽입하는 데 동일한 개념을 사용합니다. 개념은 레벨 순서로 트리를 순회하고 왼쪽 또는 오른쪽 또는 두 노드가 모두 NULL 인 노드를 발견하면 NULL 노드의 위치에 데이터를 삽입합니다 (기본 설정은 왼쪽에서 먼저). 자세한 내용은 아래 예를 참조하십시오.
위의 이진 트리에 data (10)가있는 노드를 삽입하려고합니다. BFS를 사용할 때 자식 NULL을 남긴 node (5)를 찾습니다. 그래서 우리는 10의 왼쪽 자식으로 data (5) 노드를 추가합니다.
이진 트리에 삽입하기위한 C ++ 코드
/*C++ Implementation of Insertion in Binary Tree*/
#include<bits/stdc++.h>
using namespace std;
/*Structure of Node of BT which contain pointer to left child and right child and a data for node.*/
struct Node{
int data;
struct Node* left;// for left child;
struct Node* right;// for right child;
Node(int value)// create a node using new_Node;
{
data=value;
left=NULL;
right=NULL;
}
};
/*Function which print bfs of the given tree*/
void level_order(Node* root)
{
if(root==NULL)
{
return;
}
queue<Node*> q;
q.push(root);
while(!q.empty())
{
Node* temp=q.front();
cout<<temp->data<<" ";
q.pop();
if(temp->left!=NULL)
{
q.push(temp->left);
}
if(temp->right!=NULL)
{
q.push(temp->right);
}
}
cout<<endl;
}
void add(Node* root,int value)
{
queue<Node*> q;
q.push(root);
while(!q.empty())
{
Node* temp=q.front();
q.pop();
if(temp->left==NULL)
{
temp->left=new Node(value);
goto label;
}
if(temp->right==NULL)
{
temp->right=new Node(value);
goto label;
}
if(temp->left!=NULL)
{
q.push(temp->left);
}
if(temp->right!=NULL)
{
q.push(temp->right);
}
}
label:;
}
int main()
{
/*construct tree*/
Node* root= new Node(9);
root->left= new Node(1);
root->right= new Node(8);
root->left->left= new Node(5);
root->left->right= new Node(4);
root->right->left= new Node(6);
root->right->right= new Node(7);
root->left->left->right= new Node(2);
root->left->right->right= new Node(3);
int value;
cin>>value;//input the data of node which we want to insert;
cout<<"Level order traversal before Insertion of node: ";
level_order(root);
/*add the node*/
add(root, value);
cout<<"Level order traversal after Insertion of node: ";
level_order(root);
return 0;
}
Output: Level order traversal before Insertion of node: 9 1 8 5 4 6 7 2 3 Level order traversal after Insertion of node: 9 1 8 5 4 6 7 10 2 3
이진 트리 삽입의 시간 복잡성
의 위에) 여기서 N은 주어진 이진 트리의 노드 수입니다. 최악의 시간 복잡성은 모든 노드에 정확히 하나의 자식이있을 때 발생합니다. 여기서 우리는 선형 시간으로 방문합니다. 선형 시간 복잡도는 N 순서임을 의미합니다.
공간 복잡성
O (1) 주어진 바이너리 트리에 노드를 추가 할 공간을 만들지 않기 때문입니다.
