Is féidir le CRB simpli a bheith dégéarnaithe go liosta slabhra (oibríochtaí O(n)) má thagann na heochracha in ord sórtáilte. Déanann CRB féin-chothromaithe — mar shampla, crann AVL agus crann dearg-dubh — rothlúcháin nóid a dhéanamh go huathoibríoch tar éis insertshunn/scriosadh chun an airde ~ a choinneáil, rud a ráthaíonn oibríochtaí .
log nUnbalanced (insert 1,2,3,4): Balanced after rotations:
1 2
\ / \
2 1 3
\ \
3 4
height ~ n (BAD) height ~ log n (GOOD)
| Crann AVL | Crann dearg-dubh | |
|---|---|---|
| Docht na cothromaíochta | righin (cothromaithe-in-airde) | níos bog |
| Cuardach | níos tapa (níos giorra) | beagáinín níos mall |
| Insertion/scriosadh | níos mó rothlúcháin | níos lú rothlúcháin |
| Is fearr do | ultrasholadh léitheoireachta | ultrasholadh scríbhneoireachta |
| Oibríocht | Am |
|---|---|
| search | O(log n) |
| insert | O(log n) |
| delete | O(log n) |
Coimeádann an bheirt chothromaíochta trí rothlúcháin — athstruchtúirítí áitiúla O(1) a chaomhnaíonn ord CRB agus airde a laghdú.
Tacaíonn cranna cothromaithe do léarscáileanna agus tacair ordaithe i leabharlanna caighdeánacha (m.sh., Java TreeMap, C++ std::map ag baint úsáide as crann dearg-dubh), ag soláthar atriall sórtáilte agus oibríochtaí logartamúla ráthaithaithe.
Is iad an fhreagra atá ag teastáil nuair a bhíonn ord CRB de dhíth agus ráthaíochta feidhmíochta crua i gcoinne iontrálacha freasúracha.
Leabharlann de cheisteanna agallaimh TF le freagraí mionsonraithe — ó Shóisearach go Sinsearach.
Síntiús