2-3-4 tree

Компьютерийн шинжлэх ухаанд 2-3-4 мод (2-4 мод гэж бас дууддаг) нь өөр өөрийгөө тэнцвэржүүлэгч өгөгдлийн бүтэц. Энэ нь толь бичиг хийх гол хэрэгсэл гэж болно. Модонд эдгээр тоонууд нь нүд бүхэнд хүүхэдтэй( дотоод нүүдэл) хүүхэд нь мөн 2,3,4 зангилаатай ба хүүхэдтэй.

 -А 2 зангилаа нь нэг өгөгдөлийн элемент бас дотоод нүүдлийн 2 хүүхэдтэй.
 -3 дахь зангилаа нь өгөгдөлийн 2 элементтэй ба 3 хүүхэдтэй.
 -4 дахь зангилаа нь 3 хүүхэдтэй бөгөөд дотоод нүүдлийн 4 хүүхэдтэй.

::

2-3-4 моднууд нь 4 зангилаатайг B-Tree гэнэ. B-Tree нь ерөнхийдөө хайх оруулах бас устгаж чадна. 2-3-4 модны өмчүүд нь гадны зангилаатай ба зангилаа бүр нь гүнзгий. 2-3-₮ моднуудын улаан хар моднуудын утга нь тэнцүү. Утга нь өгөгдөлийн бүтэцтэй тэнцүү. Зарим үгүүд нь ижил захиргаанд 2-3-4 тын модуудад оршиж байвал тэнд ядаж энд ядаж нэг элемент байна. Мөн 2-3-4 тын модууд оруулах мөн устгах үйлдэлтэй. Бөгөөд энэ зангилаанууд нь өсдөг.

    Танилцуулга

Улаан хар моднууд нь ихэвчлэн 2-3-4 модыг үүсгэн байгуулдаг. Яагаад гэвэл энэ чадвар нь энгийн. Ер нь 2-3-4 модууд нь үйлдэлийн системийн дах мод программын хэлний хамгийн хэцүү хэрэгсэл яагаад гэвэл онцгой саван дахь их хэмжээний тоо оруулдаг.

    Шинж чанар

Бүх зангилаа (навч эсвэл дотоод) бол 2 зангилаатай, 3 зангилаа, 4 зангилаа нэг хөндийд 2-3 өгөгдөлийн элемент тус бүрт нь байна. -Бүх навчнууд ижил гүнтэй(сүүлийн шат) -Бүх өгөгдөлүүд гол нь дэс дараалалтай.

     Хавсарга 
2-3-4 моднууд үндэснээсээ эхэлдэг

1.Хэрэв одоогийн зангилаа нь 4 зангилаатай

     -Голын буюу 3 зангилаа нь устгагдаж бас хадгалагдана.
     -Салаалсан 3 зангилаа дотор хос 2 зангилаатай (голын холболт хялбар).
     -Хэрэв  энэ зангилаа нь (аль нэг нь гэр бүлгүй бол)
     -3 зангилааны 2 шинэ 2 үндсэн зангилаатай болбол мод өндөр болно. Үндсэн дахь зангилаа дотор өснө.

2.Хүүхдүүдийн зайд оруулж өгсөн нь өгөгдөл болно. 3.Хэрэв хүүхдүүд навч бол хүүхдүүдийн зангилаан дотор өгөгдөлөөн оруулж дуусна.

   Жишээ

- 2-3-4 тын модон дотор 25 гэсэн тоог оруул

- 3 зангилаа( 24,29) нь хос 2 зангилаатай (22) ба (29) тоонд шинэ гэр бүл дэх(10,20,29) руу дээшээ өгсөж байгаагаар буцна.

- үндэсний доош уруудаж байгаа баруун тал хамнийн их тоо байна энэ нь ()(20 –е зайнд 25 оршино)).

- Зангилаа 29 д хүүхэд үлдэхгүйн хэсэг зангилаан дотор 25 гэсэн тоог оруулна.

    Устгах

Энэ оршиж байгаа элемент устгасан бол сэргээн дахин хэрэглэж болно. 2-3-4 мод арилгах 1.Олон элемент устгах Элементэд ямар ч навч байхгүй бол гарч иртэл нь хайна Аль нэгэнд нь элемент оршин байвал залгамжигч нь сунгагдана. Залгамжигч нь хэрэв том түлхүүртэй бол жижиг түлхүүрээ устгана. Аль эсвэл залгамжигч нь жижиг түлхүүртэй бол том түлхүүрээ устгана. Энэ зохицол нь 2 тын зангилаанд навч олдохгүй үед ашиглана. Үүүний дараа зангилаа мөн олдохгүй бол -2 тын элементийн навчны зангилаа багахан хэмжээний зохицол юм. -2ын зангилааны зохицол – хүлээгдэж буй үндэсний зангилаа – навч устгах 1.Хэрэв ах дүүс нь хатуу байвал (1 түлхүүртэй) гүйцэтгэл нь ах дүүсийн хамт 2.Захим ах дүүст хаалттай байдаг. 3.Parent key n 3 зангилаанд шилжинэ. 4.Хүүхэд болох ах дүүст зангилаа нэмэгдэнэ. 5.Хэрэв parent 2 зангилаатай бас ах дүүс нь 3 зангилаатай, элементийн зангилаа нь бага модны 4 зангилаа нь болно. (энэ дүрэмэнд үндэсний гэр бүлд 2 зангилаа, зангилаанаас хойш өөрчлөгдөхгүй. Яагаад бонино мод гэсэн гэвэл бүх үйлдэлийг нэгэтгэн оруулж ирж байгаа юм. ) 6.Хэрэв parent key 3 зангилаатай эсвэл 4 зангилаатай ах дүүс нь 3 зангилаатай бол бүх үйлдэл нь нэгдэн зохицоно

  -Ах дүүсийн хүүхдийг зангилаанд хувиргаж болно.
  -Энэ байгааг ер нь устгах нь асуудалтай яагаад гэвэл навчны зангилаа нь илүү даатгагдсан байдаг болхоор хэцүү.