Algoritmlarning xossalari Algoritmning asosiy xossalari. Algoritmning 5-ta asosiy xossasi bor: Diskretlilik Cheklilik

}
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

Ikkilik daraxtga qo'shilish vaqtining murakkabligi
O (N) bu erda N - berilgan ikkilik daraxtdagi tugunlar soni. Vaqtning eng yomon holati, har bir tugunda bittadan bolaga ega bo'lganda yuz beradi. Bu erda biz chiziqli vaqtda tashrif buyuramiz. Vaqtning chiziqli murakkabligi bu N tartibida ekanligini anglatadi.
Ikkilik daraxt turlari
Davom etishdan oldin, avval BT nima ekanligini bilamizmi? Ikkilik daraxt - bu bir turi ma'lumotlar tuzilishi bu tabiatan ierarxikdir. BT har bir tugun chap tugunlari, o'ng ko'rsatkichi va tugunning og'irligi sifatida ma'lumotlar bilan ifodalanadi. Har bir tugun eng ko'pi 2 bolani o'z ichiga olishi mumkin, ular ota tugunning chap va o'ng farzandiga tegishli.


Nima uchun ikkilik daraxtlar kerak? | Nima uchun biz ikkilik daraxtlardan foydalanamiz?

• 
  BT yordamida biz tezda qidirish, kiritish va o'chirishni amalga oshiramiz (ba'zi bir ustuvor tartibda berilgan ... BST kabi).
  
• 
  BT yordamida biz eng yaqin narsani ham topishimiz mumkin.
  
• 
  Ma'lumotlarni ierarxik tarzda saqlang (masalan, kompyuterdagi fayl tizimi).
  
• 
  Har qanday harakatni amalga oshirish uchun kam vaqt talab qiladigan ko'rsatgich yordamida BTni amalga oshiring.
  
• 
  Lug'atlarni prefiks izlash bilan amalga oshiring.
  
• 
  Ushbu ma'lumotlar to'plamining sobit matnida tezkor qidiruv.
  

Ikkilik daraxtlarning xususiyatlari

1. 
   Har qanday darajadagi maksimal tugun soni: 2 ^ L bu erda L - bir qator darajalar (0 <= L <= H).
   
2. 
   BT balandlikdagi H tugunlarining minimal va maksimal soni: Minimal- H + 1 va maksimal- 2 ^ (H + 1) - 1 bu erda 0 darajasi 0 ga teng.
   
3. 
   N tugunlarga ega bo'lgan ma'lum bir BTning minimal balandligi: log2 (N + 1) -1 bu erda 0 darajasi 0 ga teng.
   
4. 
   Barg tugunlarining umumiy soni: 2 bolali tugunlarning umumiy soni + 1.
   
5. 
   L bargli tugunlarga ega bo'lgan BT darajalarining minimal soni: (log2 L) +1.