[Powered by Google Translate] તમે કેવી રીતે કમ્પ્યૂટર તમારા તમામ પરિવારના સભ્યો પ્રતિનિધિત્વ કરશે?
અમે ફક્ત એક યાદી ઉપયોગ કરી શકે છે,
પરંતુ સ્પષ્ટ વંશવેલો અહીં છે.
>> હવે કહો કે અમે તમારા મહાન-દાદી, એલિસ સાથે શરૂ કરી રહ્યા છીએ.
તેઓ 2 પુત્રો, બોબ છે
અને તમારા દાદા, ચાર્લી.
ચાર્લી 3 બાળકો છે,
તમારા કાકા, દવે, તમારા કાકી, ઈવ અને તમારા પિતા, ફ્રેડ.
તમે ફ્રેડ માત્ર બાળક છે.
>> આ રીતે તમારા કુટુંબના સભ્યો શા માટે આયોજન કરશે
સરળ યાદી પ્રતિનિધિત્વ કરતાં સારી છે?
એક કારણ એ છે કે આ સ્તરવાળું માળખું,
', વૃક્ષ' એક સરળ સૂચિ કરતાં વધુ જાણકારી સમાવે છે એક કહેવાય છે.
અમે દરેકને વચ્ચે કૌટુંબિક સંબંધો ખબર
ફક્ત વૃક્ષ પરીક્ષણ કરીને.
પણ, તે ઝડપ કરી શકો છો
સમય દેખાવ અપ જબરદસ્ત, જો વૃક્ષ માહિતી સૉર્ટ થાય છે.
>> અમે અહીં ફાયદો કે ન લઇ શકે છે પરંતુ અમે આ એક ઉદાહરણ ટૂંક સમયમાં જોશો.
દરેક વ્યક્તિ વૃક્ષ પર એક નોડ દ્વારા રજૂ થાય છે.
ગાંઠો બાળક ગાંઠો હોઈ શકે છે
તેમજ પિતૃ નોડ તરીકે.
આ પારિભાષિક શબ્દો છે,
ત્યારે પણ પરિવારો ઉપરાંત વસ્તુઓ માટે વૃક્ષો મદદથી.
એલિસેઝ નોડ 2 બાળકો અને માતા - પિતા કોઈ હોય છે,
જ્યારે ચાર્લી નોડ 3 બાળકો અને 1 પિતૃ છે.
>> એક પાંદડું નોડ એક છે કે જે કોઈપણ બાળકો નથી છે
વૃક્ષ બહારની ધાર પર.
આ વૃક્ષના સર્વોચ્ચ નોડ, રુટ નોડ,
આ બોલ પર કોઈ પિતૃ છે.
>> એક દ્વિસંગી વૃક્ષ વૃક્ષ એક ચોક્કસ પ્રકાર છે,
જેમાં દરેક નોડ સૌથી વધુ હોય છે, 2 બાળકો.
અહીં સી એક દ્વિસંગી વૃક્ષ એક નોડને સ્ટ્રક્ટ છે
દરેક નોડને તેની સાથે સંકળાયેલ અમુક માહિતી ધરાવે છે
અને અન્ય ગાંઠો માટે 2 પોઇન્ટર.
>> અમારા પરિવાર વૃક્ષ,
સંકળાયેલ માહિતી દરેક વ્યક્તિ નામ હતું.
અહીં તે પૂર્ણાંક છે, જોકે, તે કંઇ હોઇ શકે છે.
જેમ તે તારણ,
દ્વિસંગી વૃક્ષ એક પરિવાર માટે એક સારા પ્રતિનિધિત્વ નહિં હોય,
કારણ કે લોકો વારંવાર 2 કરતા વધારે બાળકો છે.
>> એક દ્વિસંગી શોધ વૃક્ષ
ખાસ, દ્વિસંગી વૃક્ષ આદેશ આપ્યો હતો પ્રકાર છે
કે અમને કિંમતો જોવા ઝડપથી પરવાનગી આપે છે.
તમે સૂચન કર્યું છે
કે જે વૃક્ષ નીચે રુટ દરેક નોડ
બીજા વૃક્ષ મૂળ, એક 'ઉપવૃક્ષ.' તરીકે ઓળખાય છે
અહીં, વૃક્ષની રુટ 6 છે,
અને તેની બાળ, 2, એક ઉપવૃક્ષ મૂળ છે.
>> દ્વિસંગી શોધ વૃક્ષ
નોડ તમામ કિંમતો અધિકાર ઉપવૃક્ષ છે
આ નોડ કિંમત કરતા વધારે હોય છે. અહીં: 6.
વેલ, એક નોડ ડાબી ઉપવૃક્ષ માં કિંમતો
આ નોડ કિંમત કરતાં ઓછી છે.
જો અમે નકલી કિંમતો હેન્ડલ કરવાની જરૂર હોય,
અમે તે ક્યાં તો છૂટક અસમાનતા બદલી શકો છો,
જેનો અર્થ સમાન કિંમતો ક્યાંતો ડાબે અથવા જમણે પડો કરી શકો છો,
સુધી અમે સમગ્ર તેના વિશે સુસંગત હોય છે.
આ વૃક્ષ એ દ્વિસંગી શોધ વૃક્ષ છે
કારણ કે તે આ નિયમો નીચે મુજબ છે.
>> આ રીતે તે જો આપણે સી સ્ટ્ર્ક્ટ્સ માં તમામ ગાંઠો ચાલુ લાગશે.
નોંધ કરો કે જો બાળક ગુમ થયેલ હોય,
પોઇન્ટર નલ છે.
અમે જોવા માટે જો 7 વૃક્ષ છે કેવી રીતે તપાસ કરી શકું?
અમે રુટ શરુ થાય છે.
સાત 6 કરતા વધારે છે, તેથી જો તે વૃક્ષ છે, તે જમણી હોવા જ જોઈએ.
પછી, તે 8 કરતાં ઓછી હોય છે, તેથી તેને છોડી હોવું જ જોઈએ.
અહીં, અમે 7 મળ્યો છે.
હવે, અમે 5 માટે ચકાસણી કરશો.
પાંચ 6 કરતા ઓછી છે, તેથી તે ડાબી હોવા જ જોઈએ.
પાંચ 2 કરતા વધારે હોય છે,
તેથી તે યોગ્ય જ હોવી જોઈએ,
અને તે પણ 4 કરતા વધારે છે, તેથી તેને અધિકાર ફરીથી હોવા જ જોઈએ.
જોકે, કોઇ બાળક અહીં છે.
આ નિર્દેશક નલ છે.
આનો અર્થ એ થાય છે કે જેઓ 5 અમારા વૃક્ષ નથી.
>> અમે નીચેના કોડ સાથે બાઈનરી વૃક્ષ શોધ કરી શકો છો:
દરેક નોડ પર, અમે જોવા માટે જો આપણે મળ્યા છે તપાસ
મૂલ્ય આપણે છીએ.
જો અમે તેને શોધી નથી, અમે નિર્ધારિત કરવા કે તેણે પ્રયત્ન કરીશું
ડાબી કે જમણી અને ઉપર કે ઉપવૃક્ષ તપાસો.
આ લૂપ નીચે વૃક્ષ ચાલુ રહેશે
ત્યાં સુધી ત્યાં ક્યાં તો ડાબે અથવા જમણે પર કોઈ બાળક નોડ છે.
>> યાદ રાખો કે 5 વૃક્ષ માં ન હતી.
અમે તેને કેવી રીતે દાખલ કરી શકું?
આ પ્રક્રિયા માટે શોધવા જેવું જ દેખાય છે.
અમે નીચે 6 થી શરૂ વૃક્ષ પર ફરી વળવું,
2 થી છોડી,
4 થી જમણે,
અને જમણી ફરી, પરંતુ 4 આ બોલ પર કોઈ બાળક છે.
આ 5 માટે નવો સ્થાન હશે,
અને તે કોઈ બાળકો સાથે શરૂ થશે.
>> ઝડપી કેવી રીતે દ્વિસંગી શોધ વૃક્ષ પર કામગીરી છે?
યાદ રાખો કે Bigohnotation પર ઉપલી બાઉન્ડ પૂરી પાડવા માગે છે.
સૌથી ખરાબ કિસ્સામાં,
અમારા વૃક્ષ ખાલી સંલગ્ન યાદી હોઇ શકે છે
કે નિવેશ, નિરાકરણ, અને શોધ જેનો અર્થ થાય છે
આ વૃક્ષ ગાંઠો સંખ્યાના પ્રમાણમાં સમય લાગી શકે છે.
આ ઓ (એન) છે.
>> ઉદાહરણ તરીકે, નીચેના માન્ય દ્વિસંગી શોધ વૃક્ષ છે.
જો કે, અમે 9 શોધવા પ્રયત્ન કરે છે,
અમે દરેક નોડ પસાર હોય છે.
તે કોઈ એક કડી થયેલ યાદી કરતાં વધુ સારી છે.
આદર્શ રીતે, અમે દરેક નોડ માગતા
અમારા દ્વિસંગી શોધ વૃક્ષની 2 બાળકો હોય છે.
આ રીતે, નિવેશ નિરાકરણ, અને શોધ
અંતે સૌથી ખરાબ,, (લોગ એન) ઓ સમય લેશે.
પહેલા ના વૃક્ષ વધુ સંતુલિત હોઇ શકે છે,
આના જેવું જ.
હવે, કોઇ કિંમત શોધી સૌથી વધુ લે છે, 3, પગલાંઓ.
આ વૃક્ષ સંતુલિત છે,
અર્થ એટલે કે ન્યૂનતમ ઊંડાઈ ધરાવે છે
ગાંઠો સંખ્યાને સંબંધિત.
>> સંતુલિત દ્વિસંગી શોધ વૃક્ષ કિંમત જોઈએ છીએ
એક છટણી એરે પર દ્વિસંગી શોધ જેવી જ છે.
હકીકતમાં, જો અમે સામેલ અથવા વસ્તુઓ કાઢી નાખો જરૂર નથી,
તેઓ બરાબર એ જ રીતે વર્તે.
જો કે, એક વૃક્ષ માળખું સારું છે
હેન્ડલિંગ ઉમેરા અને નાશ માટે
>> મારું નામ Bannus વેન ડેર Kloot છે.
આ CS50 છે.