Drzewiec (informatyka)

Drzewiec – forma binarnego drzewa poszukiwań pozwalająca na wyszukiwanie binarne wśród kluczy. Po każdej sekwencji wstawień i usunięć kluczy kształt drzewa wyraża się zmienną losową z jednakowym prawdopodobieństwem dystrybucji, jak przy drzewach losowych; w szczególności, z dużym prawdopodobieństwem, jego wysokość jest proporcjonalna do logarytmu ilości kluczy tak, że każde wyszukiwanie, wstawianie lub usuwanie trwa przez czas logarytmiczny.

Drzewiec został po raz pierwszy przedstawiony przez Cecilię Aragon i Raimunda Seidela w 1989 roku^[1]^[2]. Nazwa ta jest zbitką wyrazów „drzewo” i „kopiec”.

Opis

Drzewiec z alfabetycznymi kluczami i liczbowym porządkiem kopcowym

Jest to drzewo, w którym każdy klucz posiada losowo wybrany priorytet. Strukturę drzewa zadaje wymóg utrzymania porządku kopcowego (według priorytetów kluczy). Na każdej ścieżce, od korzenia do liścia, kolejno przeglądane priorytety muszą maleć. W ten sposób korzeń drzewca jest wierzchołkiem o najwyższym priorytetem (co przekłada się na fakt, że każdy wierzchołek jest wierzchołkiem o największym priorytecie w drzewie zawieszonym w tym wierzchołku).

Operacje

Drzewce obsługują następujące podstawowe operacje:

Do wyszukiwania wartości klucza stosujemy standardowy binarny algorytm wyszukiwania w drzewie binarnych wyszukiwań, ignorując priorytety.
Aby wstawić nowy klucz x do drzewca, generujemy losowy priorytet g dla x. Wyszukujemy x w drzewcu i tworzymy nowy wierzchołek jako liść w miejscu, które wskaże binarne przeszukiwanie. Następnie, o ile x nie jest korzeniem i ma większy priorytet niż jego rodzic h (a więc zaburzona jest własność kopca), wykonujemy rotacje pomiędzy x i h.
Aby usunąć węzeł x z drzewca:
- Jeśli x jest liściem drzewa, usuwamy go.
- Jeśli x ma jedno dziecko (z), usuwamy x z drzewa, a z czynimy dzieckiem dotychczasowego rodzica dla x (lub korzeniem drzewa, jeśli x nie miał rodzica).
- Jeśli x ma dwoje dzieci, wybieramy dziecko (z) o wyższym priorytecie. Następnie rotujemy z-x tak, żeby dziecko wynieść wyżej. Dzięki temu, że wybraliśmy dziecko o wyższym priorytecie, porządek kopcowy zostaje zachowany. Potarzamy operację tak długo, aż dojdziemy z wierzchołkiem x do któregoś z powyższych przypadków^[3].

Przypisy

↑ Cecilia R.C.R. Aragon Cecilia R.C.R., RaimundR. Seidel RaimundR., Randomized Search Trees - Proc. 30th Symp. Foundations of Computer Science (FOCS 1989), Washington, D.C.: IEEE Computer Society Press, 1989, s. 540–545, DOI: 10.1109/SFCS.1989.63531, ISBN 0-8186-1982-1 (ang.).
↑ Raimund Seidel, Cecilia R. Aragon. Randomized Search Trees. „Algorithmica”. 16 (4/5), s. 464–497, 1996. DOI: 10.1007/s004539900061. (ang.).
↑ Michał Karpiński: Drzewce | Wrocławski Portal Informatyczny. informatyka.wroc.pl, 2010-10-03. [dostęp 2016-06-19].

Read other articles:

Ettore Messina

Ettore Messina Ettore Messina nel 2021 Nazionalità Italia Pallacanestro Ruolo Allenatore Squadra Olimpia Milano Hall of fame FIBA Hall of Fame (2021)Italia Basket Hall of Fame (2008)VTB United League Hall of Fame (2019)Naismith Hall of Fame (2024) Carriera Carriera da allenatore 1980-1982 Basket Mestre(giov.)1982-1983 A.P.U. Udine(vice)1983-1989 Virtus Bologna(vice)1989-1993 Virtus Bologna83-371992-1997 Italia66-391997-2002 Virtus Bol...

Dojō nabe

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Oktober 2022. Dojō nabe Dojo nabe (Jepang: 泥鰌鍋 atau ドジョウ鍋; dojō nabe) adalah sebuah hidangan nabemono Jepang.[1] Untuk menyiapkan hidangan tersebut, ikan-ikan dimasak dalam sebuah panci panas. Referensi ^ Dojo : Bon Appetit! : NIP...

العلاقات الأوزبكستانية الكمبودية

العلاقات الأوزبكستانية الكمبودية أوزبكستان كمبوديا أوزبكستان كمبوديا تعديل مصدري - تعديل العلاقات الأوزبكستانية الكمبودية هي العلاقات الثنائية التي تجمع بين أوزبكستان وكمبوديا.[1][2][3][4][5] مقارنة بين البلدين هذه مقارنة عامة ومرجعية �...

HKBP Distrik XI Toba Hasundutan

Distrik XI Toba HasundutanGereja HKBP Balige, Ressort Balige, Gereja induk (sabungan) Distrik XI Toba Hasundutan2°20′00″N 99°04′00″E / 2.333413°N 99.066541°E / 2.333413; 99.066541GerejaHuria Kristen Batak ProtestanKantorJl. Raja Paindoan no. 21, Balige, Kabupaten TobaWilayah pelayananKabupaten Toba (Kecamatan Balige dan Tampahan)Ressort9[1]Gereja23[1]Persiapan gereja1[1]Jumlah anggota jemaat29.857 jiwa[2] Keluarga (Ripe)7.732...

2023 Sakhir Formula 3 round

First round of the 2023 Formula 3 season 2023 Sakhir Formula 3 roundRound detailsRound 1 of 9 in the 2023 FIA Formula 3 Championship.Layout of the Bahrain International CircuitLocationBahrain International CircuitSakhir, BahrainCoursePermanent racing facility 5.412 km (3.363 mi)Sprint RaceDate 4 March 2023Laps 19PodiumFirst Pepe Martí Campos RacingSecond Franco Colapinto MP MotorsportThird Caio Collet Van Amersfoort RacingFastest lapDriver Pepe Martí Campos RacingTime 1:50.867 (...

Guangdong Television

Halaman ini berisi artikel tentang sebuah stasiun TV Tiongkok pada 1959-2014. Untuk grup media saat ini, lihat Guangdong Radio and Television. Guangdong Television广东电视台IndustriTelevisi penyiaranProduksi TelevisiDidirikan1959; 65 tahun lalu (1959)Wilayah operasiGuangdong, TiongkokPemilikSouthern Media CorporationSitus webwww.gdtv.com.cn Guangdong Television (GDTV; Hanzi: 广东电视台; Pinyin: Guǎngdōng Diànshì Tái; Jyutping: Gwong2 dung1 din6 si6 toi4) adalah...

2006 United States House of Representatives elections in Maryland

2006 United States House of Representatives elections in Maryland ← 2004 November 7, 2006 (2006-11-07) 2008 → All 8 Maryland seats to the United States House of Representatives Majority party Minority party Party Democratic Republican Last election 6 seats, 58.17% 2 seats, 39.77% Seats won 6 2 Seat change Popular vote 1,099,441 546,862 Percentage 64.63% 32.15% Swing 6.46% 7.62% Democratic 60–70% ...

Komet Encke

Komet Encke (secara resmi dinamai 2P/Encke) adalah sebuah komet periodik dengan periode 3,3 tahun, dinamai menurut Johann Franz Encke, yang melalui studi kerasnya pada orbit komet tersebut dan melalui banyak perhitungan dapat menghubungkan pengamatan terdahulu pada 1786 (2P/1786 B1), 1795 (2P/1795 V1), 1805 (2P/1805 U1) dan 1818 (2P/1818 W1) pada satu objek yang sama. Pada 1819 ia menerbitkan kesimpulannya pada jurnal Correspondance astronomique, dan memprediksi dengan tepat kemunculan sang ...

Aaron Nola

American baseball player (born 1993) Baseball player Aaron NolaNola with the Philadelphia Phillies in 2020Philadelphia Phillies – No. 27PitcherBorn: (1993-06-04) June 4, 1993 (age 30)Baton Rouge, Louisiana, U.S.Bats: RightThrows: RightMLB debutJuly 21, 2015, for the Philadelphia PhilliesMLB statistics (through April 26, 2024)Win–loss record94–72Earned run average3.71Strikeouts1,618 Teams Philadelphia Phillies (2015–present) Career highlights and awards All-Star (20...

Halte Transjakarta Gambir 2

223 Gambir 2 Halte TransjakartaHalte Gambir 2 pada Januari 2024LetakKotaJakarta PusatDesa/kelurahanGambir, GambirKodepos10110AlamatJalan Silang Merdeka TenggaraKoordinat6°10′44″S 106°49′52″E / 6.178873°S 106.831092°E / -6.178873; 106.831092Koordinat: 6°10′44″S 106°49′52″E / 6.178873°S 106.831092°E / -6.178873; 106.831092Desain HalteStruktur BRT, median jalan bebas 1 tepi Pintu masukMelalui rampa di Jalan Silang Merd...

Gas balloon

Balloon containing gases which are lighter than air See also: Balloon (aeronautics) This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Gas balloon – news · newspapers · books · scholar · JSTOR (September 2015) (Learn how and when to remove this message) The first launch of a gas balloon by Jacques Charles and L...

Alberto Ascari

Pour les articles homonymes, voir Ascari. Alberto Ascari Alberto Ascari en 1950. Biographie Date de naissance 13 juillet 1918 Lieu de naissance Milan (Italie) Date de décès 26 mai 1955 (à 36 ans) Lieu de décès Monza (Italie) Nationalité Italien Carrière Années d'activité 1950 - 1955 Qualité Pilote automobile Parcours AnnéesÉcurie0C.0(V.) 1950-1953 Ferrari 26 (13) 1954 Maserati 2 (0) 1954 Ferrari 1 (0) 1954-1955 Lancia 3 (0) Statistiques Nombre de courses 33 (32 départs) Pol...

Leding

Sistem perledingan di lantai bawah tanah (basement). Leding (dari Belanda: ledingcode: nl is deprecated ) adalah saluran yang tersusun dari pipa-pipa yang terbuat dari besi atau paralon (PVC) beserta sambungan pipa (fitting), katup, keran, dan perlengkapan penunjang semacamnya. Leding biasa digunakan untuk mengalirkan air (biasanya air bersih), cairan pemanas ruangan, limbah, dan lain-lain. Sistem perledingan diatur sedemikian rupa, sehingga leding untuk pengaliran air bersih, drainase, atau ...

Facekini

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Oktober 2022. Seorang wanita mengenakan sebuah facekini Facekini (Hanzi: 脸基尼; Pinyin: liǎnjīní) adalah sebuah topeng yang dirancang untuk para perenang dan pengunjung pantai yang menutupi kepala dan hanya memperlihatkan mata, hidup, dan mulut.[1...

الاتحاد الأوروبي

الاتحاد الأوروبي علم الشعار:(بالبلغارية: Обединен в многообразието)‏[1] الإحداثيات 50°07′01″N 9°14′52″E / 50.116944444444°N 9.2477777777778°E / 50.116944444444; 9.2477777777778 [2] تاريخ التأسيس 1 نوفمبر 1993 أسسها إيطاليا، وفرنسا، ولوكسمبورغ، وبلجيكا، ومملكة ه...

Robert Jenkinson, 2nd Earl of Liverpool

Prime Minister of the United Kingdom from 1812 to 1827 Lord Liverpool and The Earl of Liverpool redirect here. For other holders of the title, see Earl of Liverpool. This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Robert Jenkinson, 2nd Earl of Liverpool – news · newspapers · books · scholar · JSTOR (January ...

List of Marine Protected Areas of Italy

Map all coordinates using OpenStreetMap Download coordinates as: KML GPX (all coordinates) GPX (primary coordinates) GPX (secondary coordinates) This list is of the Marine Protected Areas (Italian: aree marine protette) of Italy. As of the most recent Official list of natural protected areas [it], decreed on 27 April 2010 and published in the official gazette on 31 May 2010 by the Ministry for Environment, Land and Sea Protection, there were twenty-seven such marine protected areas, and a fu...

مصطفى السباعي

مصطفى السباعي معلومات شخصية الميلاد 1915مدينة حمص بسوريا الوفاة 3 أكتوبر 1964سوريا سبب الوفاة مرض الجنسية سوري مناصب المراقب العام لجماعة الإخوان المسلمين في سوريا (1 ) في المنصب1945 – 1964 عصام العطار الحياة العملية المدرسة الأم جامعة الأزهر التلامذة ا...

香港節日與公眾假期

本條目為香港人口及文化系列之一香港人口普查 2021年人口普查香港人新界原居民海外港人宗教與風俗哲學語文用語文學殯儀節日與公眾假期飲食燒烤文化傳媒電視電影藝術漫畫動畫音樂粵語流行音樂教育補習文化體育電子競技 �...

Cinderella Castle

Fairy tale castle at two Disney parks This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Cinderella Castle – news · newspapers · books · scholar · JSTOR (January 2018) (Learn how and when to remove this message)Cinderella CastleCinderella Castle at Magic Kingdom.Magic KingdomAreaFantasylandCoordinates28°25′1...