Trees Programming, Data Structures and Algorithms English Malayalam

TreesYouTube↗ IA↗(long shot)
People & Blogs 1.1K views 3 likes 0 dislikes 30 Jan 2018

Programming, Data Structures and Algorithms 451 subscribers N/A YouTube↗

In the last class we looked at the list ADT.

ADT എന്ന ജനറിക് ലിസ്റ്റിനെക്കുറിച്ച് (generic list) നമ്മൾ സംസാരിച്ചു,

And we talked about a generic list ADT, there we said insert any element anywhere. And then we have talked about two other flavors of the list ADT, one is the stack LIFO Last

അവിടെ ഏത് ഘടകവും എവിടെയും ചേർക്കാമെന്ന് നമ്മൾ പറഞ്ഞു ADT ലിസ്റ്റിലെ (list) മറ്റ് രണ്ട് തരങ്ങളെക്കുറിച്ച് നമ്മൾ സംസാരിച്ചു, ഒന്ന് സ്റ്റാക്ക്

LIFO ലാസ്റ്റ് ഇൻ ഫസ്റ്റ് ഔട്ട് (Last in First Out), മറ്റൊന്ന്

In First Out and the other is the FIFO which is the First In First Out or the queue ADT.

FIFO, ഇത് ഫസ്റ്റ് ഇൻ ഫസ്റ്റ് ഔട്ട് (First In First Out) അല്ലെങ്കിൽ ക്യൂ (queue) ADT. ഇനങ്ങളുടെ

Now, the generic list ADT what it consists of a sequence of items.

ഒരു ശ്രേണിയാണ് ജനറിക് ലിസ്റ്റ് (generic list) ADT. ഇതിന് ഒരു കൂട്ടം ഘടകങ്ങളുണ്ടായിരുന്നു,

So, it had a set of elements and if you want you could have completely an unordered set of items as in the generic list or in the last in first out of the stack ADT, we had

നിങ്ങൾക്ക് ജനറിക് ലിസ്റ്റിലേതുപോലെ (generic list) ക്രമരഹിതമായ ഒരു കൂട്ടം ഇനങ്ങൾ ലഭിക്കും. ലാസ്റ്റ് ഇൻ ഫസ്റ്റ് ഔട്ട് (Last in First Out) ADT ആയ

സ്റ്റാക്കിൽ (stack) മുകളിൽ നിന്ന് മാത്രമേ

a particular flavor where you said you can only insert at the top and delete from the

ഇൻസേർട്ട് (insert) ചെയ്യാനും ഡിലീറ്റ് (delete) ചെയ്യാനും സാധിക്കൂ.

top. And in the first in first out this is the queue ADT, we inserted at the end and we deleted

ഫസ്റ്റ് ഇൻ ഫസ്റ്റ് ഔട്ട് (First In First Out) ആയ ക്യൂ (queue) ADT യിൽ അവസാനം ഇൻസേർട്ട് (insert) ചെയ്യുകയും

from the first. So, it is like you know when you look at generic ADT, it is like a vanilla ice cream when you

ആദ്യം ഡിലീറ്റ് (delete) ചെയ്യുകയും ചെയ്തു. ജനറിക് എ‌ഡി‌ടിയെ (generic ADT) നോക്കുമ്പോൾ

know, whereas the stack ADT is like chocolate and if you like chocolate, then it is like

അത് ഒരു വാനില ഐസ്‌ക്രീം (vanilla icecream) പോലെയാണ്, അതേസമയം സ്റ്റാക്ക് എ‌ഡി‌ടി (stack ADT) ചോക്ലേറ്റ്

chocolate ADT which is does something very special and on the list ADT.

(choclate) പോലെയാണ്, നിങ്ങൾ‌ക്ക് ചോക്ലേറ്റ് (choclate) ഇഷ്ടമാണെങ്കിൽ‌, അത് ചോക്ലേറ്റ് എ‌ഡി‌ടി

And a first in first out is perhaps like butter scotch which just something else special.

(choclate ADT) പോലെയാണ്, അത് വളരെ സവിശേഷമായ എന്തെങ്കിലും

So, it depending upon what you like, I do know these are some of the most favoured flavors in ice creams.

ചെയ്യുന്നു. ഫസ്റ്റ് ഇൻ ഫസ്റ്റ് ഔട്ട് (First In First Out) ബട്ടർസ്കോച്ച്

So, it is something like that, so either a stack or a queue still qualifies as a generic list now, there is one problem with the stack or a queue and the problem is the following.

(butter scotch) പോലെയാണ്, അത് മറ്റെന്തെങ്കിലും പ്രത്യേകതയാണ്. ഇത് നിങ്ങൾ ഇഷ്ടപ്പെടുന്നതിനെ ആശ്രയിച്ച്, ഐസ്ക്രീമുകളിൽ (ice cream) ഏറ്റവും പ്രിയങ്കരമായ ചില ഫ്ലേവറുകളാണിവയെന്ന്

What we see is that whether directly or indirectly there is some kind of ordering in the list.

(flavour) എനിക്കറിയാം. അത് അത്തരത്തിലുള്ള ഒന്നാണ്, ഒരു സ്റ്റാക്ക് (stack) അല്ലെങ്കിൽ ക്യൂ (queue) ഒരു ജനറിക് ലിസ്റ്റാണ്

The items either pushed on to the stack and popped from the stack in one end or they are,

(generic list), സ്റ്റാക്കിലോ (stack) ക്യൂവിലോ (queue) ഒരു പ്രശ്നമുണ്ട്, പ്രശ്നം ഇനിപ്പറയുന്നവയാണ്.

you know pushed at one end, removed from the other end as in the queue ADT.

നേരിട്ടോ അല്ലാതെയോ പട്ടികയിൽ‌ ഏതെങ്കിലും തരത്തിലുള്ള ഓർ‌ഡറിംഗ് (ordering) ഉണ്ട്.

Now, today what I want to talk about is, let us say I want to represent the family tree. Suppose I want to represent my family tree, let us say a is the parent has a,b,c,d,e,

ഇനങ്ങൾ ഒന്നുകിൽ സ്റ്റാക്കിലേക്ക് (stack) നീക്കി ഒരു അറ്റത്ത് സ്റ്റാക്കിൽ (stack) നിന്ന് പോപ്പ് (pop) ചെയ്യുന്നു അല്ലെങ്കിൽ ക്യൂവിൽ (queue) അവ ഒരു അറ്റത്ത് പുഷ് (push)

ചെയ്ത് മറ്റേ അറ്റത്ത് നിന്ന് നീക്കംചെയ്യുന്നു.

are set of children let me say that p are the parents, it does not matter whether mother

ഇപ്പോൾ, ഇന്ന് ഞാൻ സംസാരിക്കാൻ ആഗ്രഹിക്കുന്നത് ഫാമിലി ട്രീയെക്കുറിച്ചാണ് (family tree). എന്റെ ഫാമിലി ട്രീ (family tree) പ്രതിനിധീകരിക്കാൻ

or father. And let us see you have four children and these are your siblings, now this let us clearly

ഞാൻ ആഗ്രഹിക്കുന്നുവെന്ന് കരുതുക, p ആണ് പാരന്റ് (parent). എന്നിവയാണ് ചിൽഡ്രൻ (children). അമ്മയോ അച്ഛനോ എന്നത് പ്രശ്നമല്ല.

the old generation and this generation now for example, generally has generation 1 above

നിങ്ങൾക്ക് നാല് കുട്ടികളുണ്ടെന്നും ഇവർ നിങ്ങളുടെ സഹോദരങ്ങളാണെന്നും നമുക്ക് നോക്കാം, പഴയ തലമുറയെയും ഈ തലമുറയെയും ഇപ്പോൾ

you guys has had perhaps only 2 children f and so on.

വ്യക്തമായി കാണട്ടെ, നിങ്ങൾക്ക് മുകളിലുള്ള തലമുറ 1 ഉണ്ട്, നിങ്ങൾക്ക് ഒരുപക്ഷേ 2 കുട്ടികൾ

And suppose you want to find out, you know who is the grand parent of whom and so on,

മാത്രമേ ഉണ്ടായിരുന്നുള്ളൂ. നിങ്ങൾക്ക് കണ്ടെത്താനാഗ്രഹിക്കുന്നത്, ആരുടെ മുത്തച്ഛൻ ആരാണെന്നും മറ്റും ആണ്. നിങ്ങൾക്ക് സഞ്ചരിക്കണമെങ്കിൽ ഒരു ലിസ്റ്റ് (list)

then if you want to traverse you have to represented all of this using a list, then the problem would have been, this would have been number 1 in your list 2, 3, 4, 5, 6, 7, 8, 9.

ഉപയോഗിച്ച് ഇതെല്ലാം പ്രതിനിധീകരിക്കേണ്ടതുണ്ട്, അപ്പോൾ പ്രശ്നം ഉണ്ടാകുമായിരുന്നു, ഇത് നമ്പറാകുമായിരുന്നു (number). നിങ്ങളുടെ പട്ടികയിലെ 1, 2, 3, 4, 5, 6, 7, 8, 9.

5 ന് ശേഷം 6 വന്നുവെന്ന് കരുതുക, നിങ്ങൾ അവയെ

Assuming that 6 came after 5, you put them in this particular list and to access an element

ഈ പ്രത്യേക പട്ടികയിൽ ഉൾപ്പെടുത്തുകയും 10 ഇൽ ഉള്ള ഒരു ഘടകം ആക്സസ് അല്ലെങ്കിൽ

at 10, let us say or to access the element the 11th element for that matter, you do have

പതിനൊന്നാമത്തെ ഘടകം ആക്സസ് (access) ചെയ്യാൻ, നിങ്ങൾ പട്ടികയുടെ അവസാനത്തിലേക്ക് പോകണം. ഇതുപോലുള്ള ഒന്ന് പ്രതിനിധീകരിക്കാൻ

ഏതുതരം ലിസ്റ്റ് (list) ഉപയോഗിക്കും,

to go to the end of the list.

ഞാൻ ഒരു ജനറിക് ലിസ്റ്റ് (generic list) ഉപയോഗിക്കും.

So, this would have, but at the same time the reason I am talking about this is when

കാരണം, നിങ്ങൾ സഹോദരങ്ങളെ നോക്കുമ്പോൾ ഒരു

I am using a list to represent something like this, then what kind of a list will I use,

സഹോദരന് മറ്റൊരാളേക്കാൾ മുൻഗണയൊന്നുമില്ല. പക്ഷേ, പ്രാതിനിധ്യത്തിൽ ആദ്യം നിങ്ങൾ ഒരാളെ ആയിരിക്കും ലിസ്റ്റിൽ (list) ഇടുക, ഡിലീറ്റ്

I will use a generic list. Because, there is nothing like when you look at siblings for example, there is nothing

(delete) ചെയ്യാൻ, ഉദാഹരണത്തിന് ആരെങ്കിലും കുടുംബത്തിൽ

like a priority of one sibling over the other.

മരിക്കുന്നു, അത് പട്ടികയിലെ ഏത് ഘട്ടത്തിലും

But, just the representation by itself it is, first you put them in and so on and so forth.

സംഭവിക്കാം, മാത്രമല്ല എല്ലാ പ്രവർത്തനങ്ങളും വളരെ ചെലവേറിയതായിത്തീരും, കാരണം നിങ്ങൾ മുഴുവൻ

But, you know deletion for example, someone dies in the family, it can happen at any point

ലിസ്റ്റും (list) സഞ്ചരിക്കേണ്ടതുണ്ട്. ഇത്തരത്തിലുള്ള ഘടനകളെ മികച്ച രീതിയിൽ

in the list and all most all operations will become very expensive, because you have to

പ്രതിനിധീകരിക്കാമോ എന്നതാണ് ആശയം. ഏറ്റവും ജനപ്രിയമായ ഒരു പ്രാതിനിധ്യം, ഇതിൽ നിന്ന് ഞങ്ങൾക്ക്

traverse mostly the entire list. So, the idea is can we represent these kind of structures in a better way.

എന്താണ് വേണ്ടത്, j എന്ന നോഡ് (node) ആക്സസ് (access) ചെയ്യാൻ കുറച്ച് വിവരങ്ങൾ വേണം. ആരാണ് j എന്ന നോഡിന്റെ (node) പാരന്റ് (parent) എന്നാണ്

So, one of the most popular representations, what do we want from this, if I want to access

കണ്ടെത്തേണ്ടത് ((Refer Time: 05:20)). ഇത് എത്ര എളുപ്പമാണ് അല്ലെങ്കിൽ എത്ര ബുദ്ധിമുട്ടാണ് എന്നത് നമ്മൾ ഉപയോഗിക്കാൻ പോകുന്ന പ്രാതിനിധ്യത്തെ ആശ്രയിച്ചിരിക്കുന്നു.

the node corresponding to j, then I would like some information.

ഒരു ട്രീ ഡാറ്റാ സ്ട്രക്ചർ (tree data structure)

What would like I to say I want to look at, then I would like j to say who is his or her

ഇത്തരത്തിലുള്ള ഡാറ്റയെ വളരെ നന്നായി കൈകാര്യം ചെയ്യുന്നു, ഒരു ജനറൽ ട്രീ (general tree) എന്താണെന്നു നോക്കാം.

parent, who is this one’s parent, who is this is parent if I want to find a of j.

ഞാൻ ഇതിനകം പറഞ്ഞതുപോലെ, ഈ പ്രത്യേക ട്രീയിലൂടെ

So, how easy or how difficult is this depends upon the kind of representation that we are

(tree) സഞ്ചരിക്കാൻ കഴിയുക എന്നതാണ് പ്രധാന ലക്ഷ്യം, ചില മാനദണ്ഡങ്ങളെ അടിസ്ഥാനമാക്കി ഒരു പ്രത്യേക ഘടകം ട്രീയിൽ (tree) ഉണ്ടോ

going to use.

എന്ന് നോക്കുക.

So, a tree data structure kind of suites this kind of data very well, so what we are going

ഇവയെല്ലാം ഒരു ജനറൽ ട്രീയിൽ (general tree) ചെയ്‌തതിനുശേഷം ഞങ്ങൾ മടങ്ങിവരും, പക്ഷേ ഇത് പൊതുവെ

to talk about is we are going to talk about a general tree something like this.

ഒരു ട്രീ (tree) ആണ്, ഇപ്പോൾ ട്രീയുടെ (tree) പ്രാതിനിധ്യം

And then as I already said, the major objective is to be able to traverse this particular

നിരവധി മാർഗങ്ങളിലൂടെ ചെയ്യാനാകും. നിങ്ങൾക്ക് ഒരു അറേ (array) പ്രാതിനിധ്യം ഉപയോഗിക്കാം അല്ലെങ്കിൽ ഏതെങ്കിലും ജനറൽ

tree, see if a particular element is present in the tree based on certain criteria that can be satisfied and so on.

ട്രീ (general tree) എന്ന് വിളിക്കുന്നതിനെ ലെഫ്റ്റ് ചൈൽഡ് റൈറ്റ് സിബ്‌ളിംഗ് (left child

We will come back after we do all these to general a tree, but this is in general a tree,

right child) പ്രാതിനിധ്യം എന്ന് വിളിക്കുന്നു. ഇതിന്റെ അർത്ഥം p, a, b, c, d ആണ് ഇതിനുള്ള

now representation of the tree can be done in a number of ways.

പ്രാതിനിധ്യം. ഈ ട്രീ (tree) എടുത്ത് ഈ ഫോർമാറ്റിലേക്ക് (format) പരിവർത്തനം ചെയ്യുന്നത് ശ്രദ്ധിക്കുക, ഞാൻ

You can use an array representation or you can use what is called any general tree is represented by what is called the left most child, right sibling representation. What this means is p, a, b, c, d is the representation for this and this is represented like this

ഒരു അറേയെ (array) പ്രതിനിധീകരിക്കുന്നുവെങ്കിൽ എന്തുചെയ്യും, 0 ഇത് p ആണ്, ഈ നോഡ് (node) p ന് തുല്യമാണെന്ന് പറയാം. ഇപ്പോൾ, ഞാൻ ഇവിടെ ചില വിവരങ്ങൾ 0 യിൽ സൂക്ഷിക്കുന്നു, തുടർന്ന് ഇൻഡെക്സുകൾ

and you have i which is represented like this, it has two children f and this one has the left most child j, I will explain in a minute what this representation is all about.

(index) 1 മുതൽ 2 വരെ പോകുന്നു, a, 1 b, 1 c, 1 d, 1 എന്നിങ്ങനെ പറയും, e, 2 f, 2 j, 3, ഞാൻ ഇവിടെ എന്താണ് പ്രതിനിധീകരിക്കുന്നതെന്ന് ഒരു മിനിറ്റിനുള്ളിൽ ഞാൻ നിങ്ങളോട് പറയും, h, 3 i, 6 j, 7.

ഞാൻ ഇവിടെ സംഭരിക്കുന്നതെന്താണ്, ഒരു അറേ (array) നടപ്പാക്കലാണ്,

So, what is done is notice that we take this particular tree over here and converted it

ഇത് ഒരു ലിങ്ക് ലിസ്റ്റ് (linked list) നടപ്പാക്കലാണ് . എന്താണ് ലിങ്ക് ലിസ്റ്റ്,

into to this format what would I do if I was representing an array, I would say here 0 this is p, let us say this node corresponds to p. Now, I keeps some information 0 over here, then the indices go from 1 to 2, I would say

ഇത് ഒരു റിക്കേർസീവ് ഡാറ്റാ സ്ട്രക്ച്ചർ (recursive data structure) ആണ്. ഈ ട്രീയുടെ (tree) പ്രശ്നം എന്താണ്, ഞങ്ങൾ ഈ ട്രീയെ (tree) പ്രതിനിധീകരിക്കാൻ ആഗ്രഹിക്കുന്നു, തുടർന്ന് ഒരു ലിങ്ക്

a comma 1, b comma 1, c comma 1, d comma 1 and I would say e comma 2, f comma 2, j comma

ലിസ്റ്റ് (linked list) ഉപയോഗിച്ച് ഓരോ നോഡിലും (node) എനിക്ക് പറയാൻ കഴിയണം, ഞാൻ അത് പ്രതിനിധീകരിക്കുന്നുവെങ്കിൽ

3, I will tell you in a minute what I am representing over here, h comma 3 and i comma 6 and j comma

പോയിന്ററുകളുടെ (pointer) എണ്ണം അനുസരിച്ച് നോഡിന് (node) പരമാവധി പോയിന്ററുകളുടെ (pointer) എണ്ണം n ഉണ്ടെന്ന്. എനിക്ക് ഘടകങ്ങളുടെ ഒരു ലിസ്റ്റ് (list)

ഉണ്ടായിരിക്കാം, അതാണ് ഞങ്ങൾ ഇവിടെ ചെയ്യുന്നത്.

What I am storing here, if I am this is an array implementation and this is a link list implementation. What are the link list now, it is a recursive data structure, what is the problem with this tree, we want to represent this tree, then using a link list then at every node I must

ഞങ്ങൾ ഇവിടെ പറയുന്നത് p ഒരു റൂട്ട് നോഡാണെന്നും (root node) അതിൽ a, b, c, d എന്നീ ചിൽഡ്രൺ (children) ഉണ്ട്. ഏറ്റവും ഇടത്തേ ചൈൽഡ് (child) ആണ് a. എന്നിട്ട് ഞങ്ങളുടെ പ്രാതിനിധ്യം കൂടുതൽ

സൗകര്യപ്രദമാക്കാൻ, ഇത് റൂട്ട് നോഡാണെങ്കിൽ

be able to say, if I was representing it by the number of pointers I must say that node

(root node) അതിനുള്ളിൽ ഇടത് ചൈൽഡിലേക്ക്

has some max number of pointers n.

(child) ഒരു പോയിന്റർ (pointer) ഉണ്ട്, വലത് സഹോദരൻ

To avoid that you know, I could have a list of elements on the other hand that is exactly what we are doing over here.

മറ്റെല്ലാ നോഡുകളിലേക്കും (node) പോയിന്റ് (point) ചെയ്യുന്നു. അതുപോലെ തന്നെ ഏറ്റവും ഇടത്തേ ചൈൽഡിലേക്കും (child) ഒരു പോയിന്റർ (pointer) ഉണ്ടായിരിക്കും,

See, you looked at it over here after that we are doing, we are saying here p is a root

അതിനാൽ ട്രീ (tree) ഇതുപോലെയാണ്, മുന്നോട്ട് പോയിന്റ്

node and it has children a, b, c, d.

(point) ചെയ്യുന്ന പോയിന്ററുകൾ (pointer) ഉണ്ടായിരിക്കും.

Let us say a is the left most child or the oldest child, then to make our representation

മറുവശത്ത്, അറേ (array) നടപ്പാക്കലിൽ, ഞങ്ങൾ എന്തിനാണ് ചെയ്യുന്നത്, കാരണം അടിസ്ഥാന പ്രശ്‌നങ്ങളിലൊന്ന്

more convenient, if this is the root node within that it has a pointer to the left most child which whose right sibling point to all the other nodes.

പാരന്റ് (parent) വിവരങ്ങൾ വേണം എന്നതാണ്. അല്ലെങ്കിൽ പാരന്റിൽ (parent) നിന്ന് ചൈൽഡിലേക്ക് (child) പോകാൻ ആഗ്രഹിക്കുന്നു, ഈ രണ്ട് വിവരങ്ങളിൽ

And similarly it will also have a pointer to it is left most child, so the tree is like

ഒന്ന് ആവശ്യമാണ്. മറുവശത്ത് അറേ (array) നടപ്പാക്കൽ ഞങ്ങൾ

this, the pointers that are pointing forward. On the other hand in the array implementation, why are we doing is, because as I say one of the fundamental problems says we want parent information or from the parent I would like

പാരന്റിനെ (parent) പ്രത്യേകമായി സംഭരിക്കുന്നു. നോഡിന്റെ (node) ഇൻഡക്സ് (index) 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11

to go to the child, one of these two information is required. See if we look at this, the array implementation on the other hand what do we do, we say that I store the parent in this particular, let me call it the index of the node is 1, 2,

എന്നിവ ഞാൻ ഒരു അറേയിൽ (array) സൂക്ഷിച്ചുവെന്ന് കരുതുക. പിന്നെ, നമ്മൾ ചെയ്യുന്നത് നോഡിന്റെ (node) പാരന്റിലേക്ക് (parent) ഒരു പോയിന്റർ (pointer) സംഭരിക്കുക എന്നതാണ്,

3, 4, 5, 6, 7, 8, 9, 10 and 11 suppose I have storing it in an array.

ഇപ്പോൾ ഞാൻ ഇൻഡക്സ് (index) 0 ഇട്ടു, ഇൻഡക്സ്

Then, what we do is we store a pointer to the nodes parent and now I have put the index

(index) 0 എന്നാൽ എന്താണ്, ഈ പ്രത്യേക നോഡ് (node) റൂട്ട് നോഡാണ് (root node).

0, index 0 means what, this particular node is the root node.

അടുത്തതായി ഞാൻ ചെയ്യുന്നത് a എന്ന ഘടകമാണ്, ഇപ്പോൾ

Next what I do is the element a, now element a is stored here and who is it is parent, it is parent is p whose index is 1.

ഘടകം a ഇവിടെ സംഭരിച്ചിരിക്കുന്നു, അതിന്റെ പാരന്റാണ് (parent) p. p ന്റെ ഇൻഡക്സ് (index) 1 ആണ്. അതുപോലെ,

Similarly, the node b is stored in index 3 and it is parent a is a node 1 and I keep

നോഡ് (node) b ഇൻഡക്സ് (index) 3 ൽ സംഭരിച്ചിരിക്കുന്നു,

that index. Now, for c what happens a, b, c, d is like that, when I come to e what do I do, I keep

അതിന്റെ പാരന്റ് (parent) a ഒരു നോഡാണ് (node) 1 എന്ന ഇൻഡക്സ് (index) സൂക്ഷിക്കുന്നു. ഇപ്പോൾ, c ക്ക് എന്ത് സംഭവിക്കുന്നു, b,

the index of it is parent which is 2, because a is the parent of e therefore, I store e

c, d അങ്ങനെയാണ്, ഞാൻ e യിലേക്ക് വരുമ്പോൾ അതിന്റെ പാരന്റിന്റെ (parent) ഇൻഡക്സ് (index) 2 ആണ്.

and 2 over here. Similarly, for f what do I do, I store f and 2 over here, because for f the parent is again a. So, you repeat like this and you can get use the array representation for any general tree.

കാരണം e യുടെ (parent) a ആയതിനാൽ ഞാൻ e യും 2 ഉം ഇവിടെ സംഭരിക്കുന്നു. അതുപോലെ, f ഉം 2 ഉം ഇവിടെ സംഭരിക്കുന്നു, കാരണം f ന്റെ പാരന്റ് (parent) a ആണ്. നിങ്ങൾ ഇതുപോലെ

In the link list representation, this representation is basically this is array representation

ആവർത്തിക്കുകയും ഏത് പൊതു വീക്ഷണത്തിനും നിങ്ങൾക്ക് അറേ (array) പ്രാതിനിധ്യം ഉപയോഗിക്കാനും

where we use pointers to the parent in every node.

കഴിയും. ഓരോ നോഡിലും (node) പാരന്റിലേക്ക് (parent) പോയിന്ററുകൾ (pointer) ഉപയോഗിക്കുന്നു. മറുവശത്ത്, ലിങ്ക്ഡ് ലിസ്റ്റ് (linked list) പ്രാതിനിധ്യത്തിൽ

ഓരോ നോഡിനും (node) ഏറ്റവും ഇടത്തേ ചൈൽഡിലേക്കും

On the other hand, in the link list representation what does every node have, every node has

(child) വലത് സിബ്‌ളിംഗിലേക്കും (sibling) ഒരു പോയിന്റർ

a pointer to it is left most child and the right sibling.

ഉണ്ട്. p എന്നത് പാരന്റ് (parent) ആണ്, അത് ഈ ട്രീയുടെ (tree) റൂട്ട് (root) ആണ്, അതിന് ഏറ്റവും ഇടത്തേ

So, notice that p is the parent, it is the root of this particular tree therefore, it has only pointer to it is left most child, it is right sibling has pointer to null, because the root has no siblings.

ചൈൽഡിലേക്ക് (child) മാത്രമേ പോയിന്റർ (pointer) ഉള്ളൂ, വലത്തേ സിബ്‌ളിംഗ് (sibling) പോയിന്റർ (pointer) നൾ (null) ആണ്. കാരണം റൂട്ടിന് (root) സഹോദരങ്ങളില്ല.

And here what is that is happening here, a is the left most child and it is pointing

ഇവിടെ എന്താണ് സംഭവിക്കുന്നത്, a ഏറ്റവും ഇടത്തേ

to it is right sibling this is right sibling, this is it is left most child, left most child,

ചൈൽഡ് (child) ആണ്. അത് പോയിന്റ് (point) ചെയ്യുന്നത് വലത്തേ സിബ്‌ളിംഗിലേക്കാണ് (sibling).

left most child, right sibling pointer, left most child, right sibling, right sibling,

ഓരോ നോഡിലും (node) നമുക്ക് ഏറ്റവും ഇടത്തേ ചൈൽഡിലേക്കും (child0) വലത് സിബ്‌ളിംഗിലേക്കും (sibling) രണ്ട് പോയിന്ററുകൾ

left most child, left most child, right sibling, left most child, right sibling, right sibling,

(pointer) മാത്രമേയുള്ളൂ. അടിസ്ഥാനപരമായി ഓരോ നോഡിലും (node) രണ്ട് പോയിന്ററുകൾ (pointer) ഉണ്ട്, നിങ്ങൾക്ക്

left most child, left most child, right sibling. So, what I have done now in all the arrows now I have put the which corresponds to the

ഒരു ജനറൽ ട്രീ (general tree) പ്രതിനിധീകരിക്കാൻ കഴിയും. ഏതെങ്കിലും ഏകപക്ഷീയമായ ട്രീ (tree) കാണണമെങ്കിൽ ഇത് ഉപയോഗപ്രദമാണ്.

തൽക്കാലം ഞങ്ങൾ ഇത് മാറ്റിവയ്ക്കുകയും

pointer, which corresponds to that of the left most child and right sibling, RS to the

കുറച്ച് സമയത്തിന് ശേഷം ഇതിനെക്കുറിച്ച് സംസാരിക്കുകയും ചെയ്യും. പക്ഷേ, ഇത് ഒരു ട്രീയുടെ (tree) അത്തരം ഒരു പ്രാതിനിധ്യമാണെന്ന്

left most child and right sibling.

ഓർമ്മിക്കുക. ലെഫ്റ് മോസ്റ്റ് (leftmost) അഥവാ ഏറ്റവും

So, we make these pointers like this. Now, that means what is nice about the structure, in every node we are having only two pointers

ഇടത്തേ ചൈൽഡിന്റെ (child) അർത്ഥമെന്താണ്, അത് മുതിർന്ന സഹോദരനും വലത് മൂത്ത കുട്ടിയുമാണ്. കുറച്ച് സമയത്തിന് ശേഷം ഞങ്ങൾ ഈ ട്രീയിലേക്ക്

the left most child and a right sibling.

(tree) മടങ്ങും, അവിടെ നമുക്ക് ഇതിന്റെ

But, so basically you have two pointers in every node, but you are able to represent any general tree.

അറേ പ്രാതിനിധ്യം ഉണ്ട്. ചില പ്രത്യേക ട്രീകൾ (tree) നോക്കാം.

Now, this tree is useful if you want to look at any arbitrary tree.

നമ്മൾ ബൈനറി ട്രീ (binary tree) നോക്കും.

For the time being we will kindly postpone this and we will talk about this is a little

എന്താണ് ബൈനറി ട്രീ (binary tree). ഇവിടെ ഒരു ഉദാഹരണം ഉണ്ട്, ഇവിടെ നമുക്ക്

later. But, remember that this is one such representation of a tree. What is the meaning of the left most child, left most child is older sibling and a right oldest child, in the right sibling corresponds to it is next sibling at that particular level.

റൂട്ട് (root) ഉണ്ട്, കൂടാതെ രണ്ട് പോയിന്ററുകൾ (pointer) ഒന്ന് ഇടത് ചൈൽഡിനും വലതുവശത്തും ഉണ്ട്, ഇവിടെ ഒരു ശ്രേണിയും ഇല്ല, അതാണ് അടിസ്ഥാന

We will come back to this tree a little later where we have either array representation

വ്യത്യാസം. ഇതിന് സമാനമാണ് നിങ്ങൾക്ക് ഒരു നോഡ് (node) ഉള്ളിടത്ത്

of this. What we are look at is we look at some special trees today.

രണ്ട് കുട്ടികളും വലത് സഹോദരനും രണ്ട് പോയിന്ററുകൾ (pointer) ഉണ്ട്.

In particular we will look at the binary tree. What is the binary tree now?

ബൈനറി ട്രീ (binary tree) നോഡും (node) ജനറൽ ട്രീ (general tree) നോഡും (node) തമ്മിലുള്ള വ്യത്യാസം ഇടത് ചൈൽഡിനും

Here is an example, where we have the root and it also has two pointers one to the left

(child) വലത് ചൈൽഡിനും (child) ഒരു ശ്രേണിയും ഇല്ല എന്നതാണ്. ഇപ്പോൾ, ഒരു ബൈനറി ട്രീയെ (binary tree) എങ്ങനെ

child and the right side, there is no hierarchy here, that is the fundamental difference.

നിർവചിക്കും, ഇത് ഇതുപോലെ നിർവചിച്ചിരിക്കുന്നു,

It is similar to this where you have a node has two pointers left most child and right

ഇത് ശൂന്യമായ അല്ലെങ്കിൽ ഒരു റൂട്ട് (root), ഇടത്,

sibling. The difference between the binary tree node and the general tree node is that the left

വലത് ഉപ ട്രീകൾ (tree) എന്ന് വിളിക്കുന്ന

child and right child there is no hierarchy.

രണ്ട് ഡിസ്‌ജോയിന്റ് ബൈനറി ട്രീകൾ (disjoint

What you mean by that here a points to b, two had been nodded at the same level whereas,

binary tree) അടങ്ങിയ ഒരു സെറ്റ് (set) നോഡുകളാണ്

the left most child points to a node at the one level lower.

(node). ഇതാണ് ബൈനറി ട്രീ (binary tree), ഇത് ശൂന്യമായിരിക്കാം,

So, basically what we are talking about here is one level higher, here in the other hand

കൂടാതെ ഇടത്, വലത് ഉപ വൃക്ഷങ്ങളും വീണ്ടും ബൈനറി ട്രീകളാണ് (binary tree).

you are saying left more child and right child, left child and right child are at the same

ഉദാഹരണത്തിലേക്ക് മടങ്ങുക, നിങ്ങൾ ഈ നോഡിൽ (node) നിന്ന് ആരംഭിച്ചെങ്കിൽ,

level. Now, what is the use of such trees, we will see in a minute. Now, how do we define a binary tree, it defined like this, what is it.

ഇത് ഒരു ട്രീ (tree) ആണ്, ഇതിന് ഒരു നോഡ് (node) മാത്രമേയുള്ളൂ. പക്ഷേ, അടിസ്ഥാനപരമായി എല്ലാ തലത്തിലും ഒരേ ഘടന ഓരോ നോഡിൽ (node) നിന്നും വീണ്ടും

It is a finite set of nodes that is either empty or consists of a root and two disjoint

പിന്തുടരുന്നു, ലെഫ്റ് മോസ്റ്റ് ചൈൽഡ് (leftmost child), റൈറ്റ് സിബ്‌ളിംഗ് (right sibling).

binary trees called the left and right sub trees.

അതുപോലെ, ഇവിടെയുള്ള ബൈനറി ട്രീയിലും (binary tree) ഓരോ നോഡിനും (node) ഓപ്ഷണലായി (optional)

What is it telling me that, this is the binary tree, it can also be empty and it has left

രണ്ട് സബ് ട്രീകളുണ്ടാവാം, (sub tree) അല്ലെങ്കിൽ അതിന് ഒരു സബ് ട്രീയും (sub tree) ആവശ്യമില്ല.

and right sub trees which are again binary trees.

അതിന് റൂട്ട് (root) ഇല്ലെങ്കിൽ, ഒഴിഞ്ഞ

Again going back to the example, if you started from this node, this is the tree still and

ട്രീ (tree) പോലും ഒരു ബൈനറി ട്രീ (binary tree)

this is also a tree, this is also tree it has only one node.

ആണ്. ഇത് ഒരു സ്ക്യുഡ് ബൈനറി ട്രീ (skewed binary

But, basically what we are saying is at every level the same structure follows again from

tree) ആണ്, ചിത്രം ഇവിടെ സ്ലൈഡിൽ (slide) നൽകിയിരിക്കുന്നു, സ്ക്യുഡ് (skewed) എന്നാൽ അത് ഇടതുവശത്തേക്ക്

every node, left most child right sibling, it is what we said. Similarly, in the binary tree here also every node can have optionally two sub trees, it

വളച്ചൊടിക്കുന്നു, തുടർന്ന് ഞാൻ ഒരു ഫുൾ ബൈനറി ട്രീ (ful binary tree) എന്ന് വിളിക്കുന്ന മറ്റ് ബൈനറി ട്രീ (binary tree) വരച്ചിട്ടുണ്ട്, നോഡുകൾ (node) ഇതുപോലെ നിറഞ്ഞിരിക്കുന്നു.

can also have binary sub trees or it need not have any sub tree at all.

കംപ്ലീറ്റ് ബൈനറി ട്രീ (complete binary tree) എന്ന്

If it does not have the root, even an empty tree is a binary tree.

വിളിക്കുന്ന മറ്റൊരു വകഭേദവും, ഞങ്ങൾ ഇതിലേക്ക് മടങ്ങും. ഈ ട്രീ (tree) പൂരിപ്പിക്കുമ്പോൾ‌, ആദ്യ ലെവലിൽ‌ (level)

So, this is a skewed binary tree, the picture is given here in the slide, skewed means,

ഞാൻ‌ നോഡുകൾ‌ (node) പൂരിപ്പിച്ചതായി ശ്രദ്ധിക്കുക, രണ്ടാമത്തെ ലെവലിൽ‌ (level) നോഡുകൾ (node), മൂന്നാം ലെവലിൽ‌ (level) നോഡുകൾ‌ (node) പൂരിപ്പിക്കുമ്പോൾ‌, ഞാൻ‌ ഇടത്തുനിന്നും വലത്തേക്ക്‌ പോകുന്നു.

it is skewed to the left and then I have drawn other binary tree which is called a full binary

ഇതാണ് കംപ്ലീറ്റ് ബൈനറി ട്രീ (complete binary tree). ഇത് ഒരു കംപ്ലീറ്റ് ബൈനറി ട്രീ (complete binary

tree, the nodes are full like this.

tree) അല്ല, ഇത് ഒരു മിറർ ഇമേജായിരിക്കുമ്പോൾ

Then, you also have another variant of it called the complete binary tree, we will come

(mirror image) ഇത് ഒരു കംപ്ലീറ്റ് ബൈനറി ട്രീ (complete binary

back to this. What we mean by this is when you fill this tree for example, notice that I filled the

tree) ആണ്. പ്രിയോറിറ്റി ക്യൂകൾ‌ (priority queue) എന്ന്

nodes with the first level, nodes with the second level, nodes with the third level when

വിളിക്കുന്നവ നിർമ്മിക്കുന്നതിന് അത്തരം ബൈനറി ട്രീകൾ‌ക്ക്

I am filling them, I am go from left to right. This is the complete binary tree.

(binary tree) ധാരാളം ആപ്ലിക്കേഷനുകൾ‌ (application) ഉണ്ട്. ആദ്യം നമുക്ക് നോക്കാം, എന്തുകൊണ്ടാണ് ഒരു

While this one is not, this is not a complete binary tree, while it is a mirror image this

ബൈനറി ട്രീ (binary tree) വേണ്ടത്, ഇതിൽ എന്തെങ്കിലും ഉപയോഗമുണ്ടോ, ഒരു ബൈനറി ട്രീയിൽ (binary tree) നിങ്ങൾ ചെയ്യുന്ന പ്രവർത്തനങ്ങൾ എന്തൊക്കെയാണ്. എന്താണ് ബൈനറി ട്രീ (binary tree) ? ബൈനറി ട്രീ

is a complete binary tree.

(binary tree) ഒരു ഡാറ്റാ (abstract data) തരം കൂടിയാണ്,

Such binary trees have a lot of applications in building what are called priority queues

സ്റ്റാക്കുകൾ (stack), ക്യൂകൾ (queue), ലിസ്റ്റ്

we will talk about that a little later.

(list) എന്നിവ കണ്ടതുപോലെ

First let us see, why do we want a binary tree in the first place and is there any use of this and what are the operations that you will perform on a binary tree. So, you need something, so what is this that we do, these are the...

പ്രാതിനിധ്യമുള്ള ബൈനറി ട്രീ എ‌ഡി‌ടിയും (binary tree ADT) അബ്‌സ്ട്രാക്ട് ഡാറ്റാ (abstract data) തരവുമുണ്ട്, ഒരു റൂട്ട് നോഡും (root node) ലെഫ്റ് ചൈൽഡും (left child) റൈറ്റ് ചൈൽഡും (right child) ഉണ്ടെന്ന്

So, now what is the binary tree now?

പ്രതിനിധീകരിക്കുന്നു.

The binary tree is also an abstract data type, like we saw the stacks, queues and list or list, queues and stack So, we have the binary tree ADT and abstract data type that we have a representation, the

അടിസ്ഥാനപരമായി ഒരു ആവർത്തന ഡാറ്റാ (data) ഘടന, തുടർന്ന് നടപ്പിലാക്കാൻ കഴിയുന്ന ഓപ്പറേഷനുകൾ (operation) ഉണ്ട്, നിങ്ങൾ നടത്തിയ പ്രവർത്തനങ്ങൾ എന്തൊക്കെയാണ്, ഒരു ADT ഒരു ഗണിതശാസ്ത്ര

മോഡൽ (model) പോലെയാണ്, മാത്രമല്ല അതിൽ വിവിധ

representation says there is a root node and the left child and a right child that is the

പ്രവർത്തനങ്ങൾ നടത്തുകയും ചെയ്യുന്നു. നിങ്ങൾ ഒരു ബൈനറി ട്രീ (binary tree) സൃഷ്ടിക്കാൻ

representation binary tree node. So, essentially a recursive data structure and then we have operations which can be performed

ആഗ്രഹിക്കുന്നു, ആദ്യം ഒരു ശൂന്യമായ ബൈനറി ട്രീ (binary tree) സൃഷ്ടിക്കുക അല്ലെങ്കിൽ ഒരു പ്രത്യേക നോഡ് (node) ഉപയോഗിച്ച് ഒരു ബൈനറി ട്രീ (binary tree) സൃഷ്ടിക്കുക.

and what are the operations that you performed, because an ADT is like a mathematical model

കാരണം, നിങ്ങൾ എവിടെ നിന്നെങ്കിലും ആരംഭിക്കണം,

and it perform various operations on it. So, what you want to do, you want to create a binary tree, first create an empty binary

അതിനുശേഷം ലെഫ്റ്റ് ചൈൽഡിനെയോ (left child) റൈറ്റ് ചൈൽഡിനെയോ (right child) റൈറ്റ് സബ് ട്രീയെയോ

tree or create a binary tree with a particular node. Because, you have to start from somewhere, then you want to find left child, right child or right sub tree, then you want to find a parent of a given node and right child, left

(right sub tree) കണ്ടെത്തണം, തുടർന്ന് നൽകിയ നോഡിന്റെ (node) റൈറ്റ് ചൈൽഡിനെയും (right child) ലെഫ്റ്റ് ചൈൽഡിനെയും (left child) പാരന്റിനെയും (parent) കണ്ടെത്താൻ നിങ്ങൾ ആഗ്രഹിക്കുന്നു.

എല്ലായ്പ്പോഴും ആവശ്യമുള്ള ശൂന്യമായ

child are we talked about. And of course, we need to create empty tree always that should required, parent and not

ട്രീ (tree) സൃഷ്ടിക്കേണ്ടതുണ്ട്, പാരന്റ് (parent) എല്ലായ്പ്പോഴും അല്ല, ചിലപ്പോൾ ട്രീയുടെ (tree) റൂട്ട് (root) ചോദിക്കുന്നു. അതിനാൽ, ശൂന്യമായ ട്രീ (tree) സൃഷ്ടിക്കുകയും ചിലപ്പോൾ റൂട്ട് (root) ചെയ്യുന്നതും

നല്ലതല്ല, പക്ഷേ മറ്റ് ചില പുസ്തകങ്ങൾ

always, sometimes they ask for the root of the tree.

ഇതിനെക്കുറിച്ച് സംസാരിച്ചതിനാൽ

So, creation of empty tree and sometimes get root, this is not good to

ഞാൻ ഇത് പറയുന്നു. റൂട്ട് (root) നേടുക ബൈനറി ട്രീകളുടെ (binary tree) നടപ്പാക്കൽ എന്താണെന്ന് നിങ്ങളോട് പറയുന്നു.

have, but since some other books talked about it, I kept this particular operation, because get root if you have it tells you what the implementation of the binary trees.

ഇപ്പോൾ ഞങ്ങൾ ചെയ്യുന്നത്, ഒരു ആപ്ലിക്കേഷൻ (application) എടുക്കും, ബൈനറി ട്രീകളുടെ (binary tree) ധാരാളം ആപ്ലിക്കേഷനുകൾ (application) ഉണ്ട്, നിങ്ങൾക്ക്

So, now what we will do is, we will take one application, there is a lots of applications

സെറ്റുകളെ (set) പ്രതിനിധീകരിക്കാൻ കഴിയും, ഹഫ്മാൻ കോഡിംഗ്

of binary trees, you can represent sets, you can do Huffman coding, you can represents

(Huffman coding) ചെയ്യാൻ കഴിയും, ഹീപ്പുകളും (heap) ഡിക്ഷണറിയും

heaps and dictionaries.

(dictionary) പ്രതിനിധീകരിക്കാൻ കഴിയും.