6-ma’ruza. Binar daraxtlar

4. MERGE va SPLIT amallari

Ikkita muvozanatlangan AVL daraxtini birlashtirish algoritmi

Ikkita muvozanatlangan AVL daraxti berilgan bo’lsin. Ularni birlashtirish natijasida yangi muvozanatlangan binary daraxt hosil bo’lishi kerak. Shu amalni bajarishning turlicha samaradorlikka ega bo’lgan algoritmlarini ko’rib chiqamiz.
Birinchi daraxtda n ta va ikkinchisida m ta element berilgan bo’lsin.
Birlashtirish funksiyasi O(n+m) vaqtda bajarilishi kerak.

1. usul. Birinchi daraxt elementlarini ikkinchi daraxtga kiritish.

1ta binar daraxt elemenetlarini birma bir o’qib olib, 2-daraxtga kiritamiz. 2-daraxtdagi elementlar soni n ga teng bo’lsa, unga element kiritish algoritmi
vaqt sarfi log₂n ga teng. M ta elementni kiritish algoritmi samaradorligi Log(n)
+ Log(n+1) … Log(m+n-1) ga teng. Bu ifoda qiymati mlog₂n va mlog₂(m+n-1) oraliqda bo’ladi. Samaradorlikni oshirish uchun elementlarni kichik daraxtga kiritishni nazarda tutamiz.

2. usul. Simmetrik ko`rikdan o`tkazish orqali bilrlashtirish.

1. 
   1-daraxtni simmetrik ko`rikdan o`tkazamiz va elementlarni arr1[] va elementlarni massivga joylaymiz. Bu qadamda O(m) vaqt sarflanadi.
   
2. 
   2-daraxtni simmetrik ko`rikdan o`tkazamiz va elementlarni arr2[] va elementlarni massivga joylaymiz. Bu qadamda O(n) vaqt sarflanadi.
   
3. 
   1 va 2 qadamdagi massivlar saralanganligi sababli ularni birlashtirish O(m+n) vaqt talab etadi.
   
4. 
   Natijaviy saralangan massivdan muvozanatlangan binar daraxt hosil qilamiz va bu amal O(m+n) vaqt talab qiladi.
   

Ushbu usulning samaradorligi birinchi usulga qaraganda yaxshi. Bu metod hattoki O(m+n) vaqt talab etadi agar berilgan binar daraxtlar muvozanatlanmagan bo`lsa ham. Quyida ushbu usulning C++ da dastur kodi keltirilgan

#include #include
/* A binary tree node has data, pointer to left
child
and a pointer to right child */ struct node
{
int data;
struct node* left; struct node* right;
};
// A utility function to merge two sorted arrays into one
int *merge(int arr1[], int arr2[], int m, int n);

// A helper function that stores inorder traversal of a tree in inorder array

void storeInorder(struct node* node, int inorder[], int *index_ptr);
/* A function that constructs Balanced Binary Search Tree from a sorted array
See http://www.geeksforgeeks.org/archives/17138 */
struct node* sortedArrayToBST(int arr[], int start, int end);
/* This function merges two balanced BSTs with roots as root1 and root2.
m and n are the sizes of the trees respectively */
struct node* mergeTrees(struct node *root1, struct node *root2, int m, int n)
{
// Store inorder traversal of first tree in an array arr1[]
int *arr1 = new int[m]; int i = 0;
storeInorder(root1, arr1, &i);

// Store inorder traversal of second tree in another array arr2[]

int *arr2 = new int[n]; int j = 0;
storeInorder(root2, arr2, &j);
// Merge the two sorted array into one int *mergedArr = merge(arr1, arr2, m, n);
// Construct a tree from the merged array and return root of the tree
return sortedArrayToBST (mergedArr, 0, m+n-
1);
}

the
*/
/* Helper function that allocates a new node with given data and NULL left and right pointers.
struct node* newNode(int data)
{

node));
struct node* node = (struct node*)
malloc(sizeof(struct

node->data = data; node->left = NULL; node->right = NULL;


return(node);
}
// A utility function to print inorder traversal of a given binary tree
void printInorder(struct node* node)
{
if (node == NULL) return;
/* first recur on left child */ printInorder(node->left);
printf("%d ", node->data);
/* now recur on right child */ printInorder(node->right);
}
// A utility unction to merge two sorted arrays into one
int *merge(int arr1[], int arr2[], int m, int n)
{
// mergedArr[] is going to contain result

int *mergedArr = new int[m + n]; int i = 0, j = 0, k = 0;

// Traverse through both arrays while (i < m && j < n)

{
// Pick the smaler element and put it in
mergedArr
if (arr1[i] < arr2[j])
{
mergedArr[k] = arr1[i]; i++;
}
else
{
mergedArr[k] = arr2[j]; j++;
} k++;
}
// If there are more elements in first array while (i < m)
{
mergedArr[k] = arr1[i]; i++; k++;
}
// If there are more elements in second array while (j < n)
{
mergedArr[k] = arr2[j]; j++; k++;
}
return mergedArr;
}

// A helper function that stores inorder traversal of a tree rooted with node
void storeInorder(struct node* node, int inorder[], int *index_ptr)
{
if (node == NULL) return;
/* first recur on left child */ storeInorder(node->left, inorder, index_ptr);

entry
inorder[*index_ptr] = node->data; (*index_ptr)++; // increase index for next

/* now recur on right child */ storeInorder(node->right, inorder,

index_ptr);
}
/* A function that constructs Balanced Binary Search Tree from a sorted array
See http://www.geeksforgeeks.org/archives/17138 */
struct node* sortedArrayToBST(int arr[], int start, int end)
{
/* Base Case */ if (start > end)
return NULL;
/* Get the middle element and make it root */ int mid = (start + end)/2;
struct node *root = newNode(arr[mid]);

make it

/* Recursively construct the left subtree and left child of root */

root->left = sortedArrayToBST(arr, start,
mid-1);

/* Recursively construct the right subtree and make it

end);
right child of root */
root->right = sortedArrayToBST(arr, mid+1,

return root;
}
/* Driver program to test above functions*/ int main()
{

BST
/* Create following tree as first balanced
100
/ \
50 300
/ \
20 70
*/
struct node *root1 = newNode(100); root1->left = newNode(50);
root1->right = newNode(300); root1->left->left = newNode(20); root1->left->right = newNode(70);

BST
/* Create following tree as second balanced
80
/ \
40 120

*/
struct node *root2 = newNode(80); root2->left = newNode(40);
root2->right = newNode(120);

struct node *mergedTree = mergeTrees(root1, root2, 5, 3);

printf ("quyida birlashtirilgan binar daraxt elementlarini tartibli ko’ruvdan o’tkazilishi: \n");

printInorder(mergedTree);
getchar(); return 0;
}

Dastur natijasi:

quyida birlashtirilgan binar daraxt elementlarini tartibli ko’ruvdan o’tkazilishi:
20 40 50 70 80 100 120 300

3.