شجرة (بنية بيانات)

  لمعانٍ أخرى، طالع شجرة (توضيح).
شجرة

تعديل - تعديل مصدري - تعديل ويكي بياناتحول القالب

شجرة بسيطة غير مرتبة، العقدة رقم 7 لديها ابنين 2 و6 وأب واحد 2. العقدة الجذر ليس لديها أب.

في علم الحاسوب, الشجرة هي هيكل بيانات واسع الاستخدام يحاكي شكل شجرة هرمية مع مجموعة من الرؤوس المرتبطة.

في علم رياضيات، هي شجرة متصلة متجهة: رسم بياني متصل عديم الحلقات حيث لكل رأس يوجد صفر أو أكثر من الرؤوس الأبناء وأب واحد على الأكثر. أيضا، لأبناء رأس ما يوجد ترتيبا محددا.

مصطلحات

الرأس هو بنية تمتلك قيمة، شرط، أو تمثل هيكل بيانات منفصل (الذي يمكن أن يكون شجرة بحد ذاته). لكل رأس يوجد صفر أو أكثر من الرؤوس الأبناء، التي تكون تحته في الشجرة (بالإجماع، الشجر يرسم لأسفل). الرأس الذي يمتلك ابنا يسمى رأس أب لذلك الرأس, (أو سلفه، أو سابقه). للرأس يوجد على الأكثر أب واحد.

رأس داخلي أو رأس باطني هو أي رأس من الشجرة بحيث يمتلك رؤوس أبناء. وبالمثل, رأس خارجي (أيضا يطلع عليه ورقة أو رأس طرفي) هو أي رأس بحيث لا يمتلك أية رؤوس أبناء.

يطلق على الرأس الأعلى في شجرة الجذر. كونه الرأس الأعلى، الجذر لا يمتلك آباء. هو الرأس الذي عادة ما تبدأ منه العمليات (بالرغم من أن بعض الخوارزميات تبدأ من الأوراق). يمكن الوصول لكل الرؤوس الأخرى منه (الجذر) باتباع الحواف أو الروابط. (بالتعريف الرسمي، كل مسار كهذا هو فريد). في الرسوم البيانية، يرسم عادة في الأعلى. في بعض الأشجار مثل الأكوام، للجذر هناك خصائص مميزة. كل رأس في الشجرة يعد جذرا للشجرة الفرعية المبتدئة به.

شجرة حرة هي الشجرة التي ليس لها جذر.

ارتفاع رأس هو طول أطول مسار سفلي لورقة من ذلك الرأس. ارتفاع الجذر هو ارتفاع الشجرة. عمق رأس هو أطول مسار للجذر. هناك حاجة لهذه الخاصية في معالجة العديد من الأشجار المتزنة، شجرة AVL على وجه الخصوص. بالإجماع، القيمة 1- تعطى لشجرة فرعية بدون رؤوس، حيث يعطى الصفر شجرة فرعية برأس واحد.

شجرة فرعية لشجرة ج هي شجرة تتكون من رأس في الشجرة ج وكل أحفاده في ج. (هذا تعريف مختلف عن التعريف الرسمي للشجرة الفرعية في نظرية المخططات[1]). شجرة فرعية التي تبدأ من الجذر هي الشجرة الكاملة؛ الشجرة الفرعية التي تبدأ من أي رأس اخر تسمى شجرة فرعية حقيقية (مشابها لمصطلح المجموعة الجزئية الحقيقية).

تمثيل

هناك العديد من الطرق لتمثيل الأشجار. التمثيلات العامة تمثل الرؤوس كسجلات مخصصة بشكل حيوي لعائلة ما مع مؤشرات لابنائهم، آبائهم، أو كلاهما، أو كعناصر في مصفوفة مع علاقات بين بعضهم البعض محددة حسب موقعهم في المصفوفة (مثل الكومة الثنائية).

الشجر والرسوم البيانية

هيكل بيانات الشجرة يمكن أن يعمم ليمثل رسوما بيانية متصلة عن طريق إزالة التقييدات بأنه للرأس (أب) واحد على الأكثر، وبأن الحلقات غير مسموحة. والزوايا تبقى معتبرة تجريديا أزواج من الرؤوس، مع ذلك، والمصطلحات أب وابن عادة ما يتم استبدالهم بمصطلحات أخرى (على سبيل المثال، مصدر وهدف)، وتوجد العديد من أساليب التنفيد، مثل قائمة الجوار.

العلاقة مع الشجر في نظرية المخططات

في نظرية المخططات، الشجرة هي رسم بياني متصل عديم الحلقات؛ إلا إذا نص غير ذلك، الشجر والرسوم البيانية غير متصلة.

طرق الاجتياز

المرور خلال عناصر الشجرة، عن طريق العلاقات بين الآباء والأبناء، يسمى اجتياز الشجرة. عادة، بالإمكان تنفيذ عملية ما عندما يصل المؤشر إلى رأس معين. اجتياز الذي يتم به المرور على كل أب قبل أبنائه يسمى اجتياز بترتيب خلفي؛ اجتياز الذي يتم به المرور على كل أب قبل أبنائه يسمى اجتياز بترتيب أمامي؛ اجتياز الذي يتم به المرور على الشجرة الفرعية اليسرى ثم الرأس نفسه يسمى اجيازا مرتبا. (الحالة الأخيرة، تشير إلى شجرتين فرعيتين بالضبط، شجرة فرعية يمني وشجرة فرعية يسرى، يفترض بالتحديد شجرة ثنائية.)

عمليات شائعة

  • تعداد كافة العناصر
  • تعداد جزء من شجرة
  • البحث عن عنصر
  • إضافة عنصر جديد في موقع معين على الشجرة
  • حذف عنصر
  • إزالة مقطع كامل من شجرة (تسمى التقليم)
  • إضافة قسم كامل لشجرة (تسمى التطعيم)
  • العثور على الجذر لأي رأس

استعمالات شائعة

انظر أيضًا

Other trees

المراجع

  1. ^ Eric W. Weisstein "Subtree." From MathWorld—A Wolfram Web Resource. http://mathworld.wolfram.com/Subtree.html نسخة محفوظة 2020-04-26 على موقع واي باك مشين.
  2. ^ Miltiadou, Milto; Campbell, Neill D. F.; Cosker, Darren; Grant, Michael G. (Jan 2021). "A Comparative Study about Data Structures Used for Efficient Management of Voxelised Full-Waveform Airborne LiDAR Data during 3D Polygonal Model Creation". Remote Sensing (بالإنجليزية). 13 (4): 559. Bibcode:2021RemS...13..559M. DOI:10.3390/rs13040559.

Read other articles:

Santa Ysabel, California

Unincorporated community in California, United States Unincorporated community in California, United StatesSanta YsabelUnincorporated communitySanta Ysabel AsistenciaSanta YsabelLocation within the state of CaliforniaShow map of San Diego County, CaliforniaSanta YsabelSanta Ysabel (southern California)Show map of southern CaliforniaSanta YsabelSanta Ysabel (California)Show map of CaliforniaSanta YsabelSanta Ysabel (the United States)Show map of the United StatesCoordinates: 33°6′33″N 11...

 

趙家驤

追晉陸軍二級上將趙家驤將軍个人资料出生1910年 大清河南省衛輝府汲縣逝世1958年8月23日(1958歲—08—23)（47—48歲） † 中華民國福建省金門縣国籍 中華民國政党 中國國民黨获奖 青天白日勳章（追贈）军事背景效忠 中華民國服役 國民革命軍 中華民國陸軍服役时间1924年－1958年军衔 二級上將 （追晉）部队四十七師指挥東北剿匪總司令部參謀長陸軍�...

 

Tilton School

School in Tilton, New Hampshire, United StatesTilton SchoolAddress30 School StreetTilton, New HampshireUnited StatesCoordinates43°26′40″N 71°35′23″W / 43.44444°N 71.58972°W / 43.44444; -71.58972InformationTypePrivate, coeducational, secondary boarding and day schoolMottoQuanti Est Sapere - How Valuable is WisdomEstablished1845; 179 years ago (1845)Head of SchoolDerek KreinGrades9–12 and Post GradGenderCoeducationalEnrollment150CampusSmal...

Lisa Arrindell

American actress Lisa ArrindellArrindell at Evidence Dance Company's Winter Gala at the Hudson Theater in 2008BornMarch 24, 1969 (age 54)The Bronx, New York, U.S.EducationThe Juilliard SchoolOccupationActressYears active1991–presentSpouse Basil Anderson ​ ​(m. 1993; div. 2015)​Children2 Lisa Arrindell (born March 24, 1969), also credited as Lisa Arrindell Anderson, is an American actress. Beginning her career in the early 1990s, Arrindell...

 

Sự chia cắt Tiệp Khắc

Sự chia cắt Tiệp Khắc / sự phân rã Tiệp Khắc (tiếng Séc: Rozdělení Československa, tiếng Slovak: Rozdelenie Česko-Slovenska) có hiệu lực vào ngày 1 tháng 1 năm 1993, và là sự phân tách tự quyết của nước cộng hòa liên bang Tiệp Khắc thành các nước độc lập Cộng hòa Séc và Slovakia. Cả hai quốc gia này giống các quốc gia cũ Cộng hòa Xã hội Chủ nghĩa Séc và Cộng hòa Xã hội Chủ nghĩa Slovakia...

 

Adam Arkin

American actor and director Adam ArkinArkin in 1999Born (1956-08-19) August 19, 1956 (age 67)New York City, U.S.OccupationsActordirectorYears active1969–presentSpouses Linda Arkin Phyllis Lyons ​(m. 1999⁠–⁠2013)​ Michelle Dunker ​(m. 2017)​ Children2ParentAlan Arkin (father)RelativesMatthew Arkin (brother)David I. Arkin (paternal grandfather) Adam Arkin (born August 19, 1956)[1] is an American ac...

2019 UCLA Bruins football team

2019 UCLA Bruins football team 2019 UCLA Bruins footballConferencePac-12 ConferenceDivisionSouth DivisionRecord4–8 (4–5 Pac-12)Head coachChip Kelly (2nd season)Offensive coordinatorJustin Frye (1st season)Offensive schemeSpread optionDefensive coordinatorJerry Azzinaro (2nd season)Base defense4–2–5Home stadiumRose BowlUniformSeasons← 20182020 → 2019 Pac-12 Conference football standings vte Conf Overall Team   W   L   &...

 

عزلة بني شعب (تعز)

عزلة بني شعب  - عزلة -  تقسيم إداري البلد  اليمن[1] المحافظة محافظة تعز المديرية مديرية شرعب السلام خصائص جغرافية إحداثيات 13°46′34″N 43°51′55″E / 13.77621°N 43.86518°E / 13.77621; 43.86518   الارتفاع 1397 متر  السكان التعداد السكاني 2004 السكان 3٬489   • الذكور 1٬649 &...

 

Amateur Trapshooting Association

Amateur Trapshooting AssociationJurisdiction InternationalAbbreviationATAFounded1900 (1900) 1940s postcard of headquarters in Ohio The Amateur Trapshooting Association (ATA)[1] serves as the governing body for the sport of American style of trapshooting. The ATA was founded in 1900 and as the American Trapshooting Association.[2] Its first president was John Philip Sousa.[3][4] See also List of shooting sports organizations References ^ The official site o...

James Farley

American businessman and politician (1888–1976) For other people named James Farley, see James Farley (disambiguation). James Farley50th United States Postmaster GeneralIn officeMarch 4, 1933 – September 10, 1940PresidentFranklin D. RooseveltPreceded byWalter Folger BrownSucceeded byFrank C. WalkerChair of the Democratic National CommitteeIn officeJuly 2, 1932 – August 17, 1940Preceded byJohn J. RaskobSucceeded byEdward J. FlynnChair of the New York Democratic PartyIn ...

 

Vinaixa

Municipality in Catalonia, SpainVinaixaMunicipalityFireworks outside the church of St. John the Baptist Coat of armsVinaixaLocation in Province of LleidaShow map of Province of LleidaVinaixaLocation in CataloniaShow map of CataloniaVinaixaLocation in SpainShow map of SpainCoordinates: 41°25′49″N 0°58′34″E / 41.43028°N 0.97611°E / 41.43028; 0.97611Country SpainCommunity CataloniaProvinceLleidaComarcaLes GarriguesGovernment • MayorJosep ...

 

Hugó Sónyi

Hungarian military officer The native form of this personal name is Sónyi Hugó. This article uses Western name order when mentioning individuals. General Hugó Sónyi ca 1940 Hugó Sónyi Vienna 1902 Hugó Sónyi (Wölkersdorf 2 March, 1883 - 7 June, 1958 Ratingen) was a Hungarian military officer who served as the Commander-in-Chief of the Hungarian Army. He was a member of the Upper House of the Hungarian Parliament, and the Captain General of the Hungarian Order of Vitéz Biography H...

Parachute (magazine)

Contemporary art magazine ParachutePARACHUTE 1, fall 1975 (contemporary art magazine), cover: Vladimir Tatlin, Monument to the 3rd International, draft drawing, 1919; graphic design: Roland Poulin. Chantal Pontbriand editor and publisherEditorChantal PontbriandCategoriesArtsFrequencyQuarterlyCirculation5,0000PublisherArtdataFounderChantal PontbriandFounded1974First issueOctober 1975 (1975-October)Final issueNumberApril 2009125CountryCanadaBased inMontreal, QuébecLanguageEnglish, Fr...

 

吉村道明

吉村 道明プロフィールリングネーム 吉村 道明本名 吉村 道明ニックネーム 火の玉小僧突貫小僧闘将身長 183cm体重 108kg誕生日 1926年9月19日死亡日 (2003-02-15) 2003年2月15日（76歳没）出身地 日本・岐阜県岐阜市スポーツ歴 相撲デビュー 1954年4月引退 1973年3月3日テンプレートを表示 吉村 道明（よしむら みちあき、1926年〈大正15年〉9月19日 - 2003年〈平成15年〉2月15日）は、日�...

 

Nathaniel Hawthorne

American author (1804–1864) Nathaniel HawthorneHawthorne in the 1860sBornNathaniel Hathorne(1804-07-04)July 4, 1804Salem, Massachusetts, U.S.DiedMay 19, 1864(1864-05-19) (aged 59)Plymouth, New Hampshire, U.S.Alma materBowdoin CollegeSpouse Sophia Peabody ​(m. 1842)​Children3, including Julian and RoseSignature Nathaniel Hawthorne (born Nathaniel Hathorne; July 4, 1804 – May 19, 1864) was an American novelist and short story writer. His works often fo...

Khởi động tình dục

Mục từ này liên quan đến chủ đề giáo dục giới tính và tình dục. Thông tin ở đây có thể không phù hợp với một số đối tượng độc giả hoặc khi truy cập ở những nơi công cộng. Wikipedia không chịu trách nhiệm về những nội dung có thể không phù hợp cho một số người xem, xem chi tiết tại Wikipedia:Phủ nhận về nội dung. Tranh in Francion 15 của Martin van Maële mô tả một cặp tình nhân �...

 

フジキセキ

この記事では「旧馬齢表記」と「新馬齢表記」が混在しています。 詳しくは馬齢#日本における馬齢表記を参照してください。 フジキセキ 画像をアップロード品種 サラブレッド[1]性別 牡[1]毛色 青鹿毛[1]生誕 1992年4月15日[1]死没 2015年12月28日（23歳没）父 サンデーサイレンス[1]母 ミルレーサー[1]母の父 Le Fabuleux[1]生国 日本（北�...

 

Wheel of Fortune (American game show)

American television game show For the unrelated American game show of the same name that debuted in 1952, see Wheel of Fortune (1952 game show). For other uses, see Wheel of Fortune (disambiguation). Wheel of FortuneAlso known asWheelGenreGame showCreated byMerv GriffinDirected byJeff GoldsteinDick CarsonMark CorwinBob CisnerosRobert EnnisAlex Van WagnerPresented byChuck WooleryPat SajakRolf BenirschkeBob GoenSusan StaffordVanna WhiteMaggie SajakRyan SeacrestAnnouncerCharlie O'DonnellJack Cla...

象の白い脚

象の白い脚 死体発見現場となるメコン川河畔（ビエンチャン市内）作者 松本清張国 日本言語 日本語ジャンル 長編小説発表形態 雑誌連載初出情報初出 『別册文藝春秋』 1969年8月号 - 1970年8月号初出時の題名 『象と蟻』出版元 文藝春秋刊本情報刊行 『象の白い脚』出版元 文藝春秋出版年月日 1974年6月25日装画 竹内宏一 ウィキポータル 文学 ポータル 書物テンプレート...

 

無形文化遺産

2 ゲレデ（英語版）の口承遺産 無形文化遺産のロゴ 無形文化遺産（むけいぶんかいさん、intangible cultural heritage）は、民俗文化財、フォークロア、口承伝統などの無形文化財を保護対象とした、国際連合教育科学文化機関（ユネスコ）の事業の一つ。2006年に発効した無形文化遺産の保護に関する条約（以下、無形文化遺産条約）に基づく。無形文化遺産に対して、ユネ�...