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


Download 1.05 Mb.
bet8/23
Sana06.04.2023
Hajmi1.05 Mb.
#1334689
1   ...   4   5   6   7   8   9   10   11   ...   23
Bog'liq
1 mavzu Algoritmlarning xossalari Algoritmning asosiy xossalari

}
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.


Download 1.05 Mb.

Do'stlaringiz bilan baham:
1   ...   4   5   6   7   8   9   10   11   ...   23




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling