Левосторонние красно-чёрные деревья — различия между версиями
м (переименовал Left-leaning Red-Black Trees в Left-leaningRed-BlackTrees: /) |
|||
| Строка 2: | Строка 2: | ||
|definition = Left-leaning Red-Black Trees . | |definition = Left-leaning Red-Black Trees . | ||
}} | }} | ||
| + | ==Вращения== | ||
| + | |||
| + | * <tex> \mathrm{push}(i, x)</tex> {{---}} добавляет элемент <tex>x</tex> в стек узла <tex>i</tex>, | ||
| + | '''Stack''' push(i : '''Node''', x : '''T'''): | ||
| + | k.value = x | ||
| + | k.prev = i | ||
| + | s.top = k | ||
| + | '''return''' s | ||
| + | |||
| + | * <tex>\mathrm{pop}(i)</tex> {{---}} возвращает значение, хранящееся в узле <tex>i</tex> и копирует элемент, предыдущий для него. | ||
| + | '''pair<T, Stack>''' pop(i : '''Node'''): | ||
| + | '''T''' val = i.value | ||
| + | i = i.prev | ||
| + | '''return''' pair(val, s) | ||
| + | |||
| + | |||
| + | <code> | ||
| + | '''Node '''rotateRight(h : '''Node '''): | ||
| + | x = h.left | ||
| + | h.left= x.right | ||
| + | x.right= h | ||
| + | x.color = h.color | ||
| + | h.color = RED | ||
| + | '''return ''' x | ||
| + | </code> | ||
| + | |||
| + | <code> | ||
| + | '''Node''' rotateLeft(h : '''Node'''): | ||
| + | x = h.right | ||
| + | h.right = x.left | ||
| + | x.left = h | ||
| + | x.color = h.color | ||
| + | h.color = RED | ||
| + | '''return''' x | ||
| + | </code> | ||
Версия 01:07, 8 декабря 2017
| Определение: |
| Left-leaning Red-Black Trees . |
Вращения
- — добавляет элемент в стек узла ,
Stack push(i : Node, x : T): k.value = x k.prev = i s.top = k return s
- — возвращает значение, хранящееся в узле и копирует элемент, предыдущий для него.
pair<T, Stack> pop(i : Node): T val = i.value i = i.prev return pair(val, s)
Node rotateRight(h : Node ): x = h.left h.left= x.right x.right= h x.color = h.color h.color = RED return x
Node rotateLeft(h : Node): x = h.right h.right = x.left x.left = h x.color = h.color h.color = RED return x
