avl_tree_multiset¶
ソースコード¶
from titan_pylib.data_structures.avl_tree.avl_tree_multiset import AVLTreeMultiset
展開済みコード¶
1# from titan_pylib.data_structures.avl_tree.avl_tree_multiset import AVLTreeMultiset
2# from titan_pylib.my_class.ordered_multiset_interface import OrderedMultisetInterface
3# from titan_pylib.my_class.supports_less_than import SupportsLessThan
4from typing import Protocol
5
6
7class SupportsLessThan(Protocol):
8
9 def __lt__(self, other) -> bool: ...
10from abc import ABC, abstractmethod
11from typing import Iterable, Optional, Iterator, TypeVar, Generic
12
13T = TypeVar("T", bound=SupportsLessThan)
14
15
16class OrderedMultisetInterface(ABC, Generic[T]):
17
18 @abstractmethod
19 def __init__(self, a: Iterable[T]) -> None:
20 raise NotImplementedError
21
22 @abstractmethod
23 def add(self, key: T, cnt: int) -> None:
24 raise NotImplementedError
25
26 @abstractmethod
27 def discard(self, key: T, cnt: int) -> bool:
28 raise NotImplementedError
29
30 @abstractmethod
31 def discard_all(self, key: T) -> bool:
32 raise NotImplementedError
33
34 @abstractmethod
35 def count(self, key: T) -> int:
36 raise NotImplementedError
37
38 @abstractmethod
39 def remove(self, key: T, cnt: int) -> None:
40 raise NotImplementedError
41
42 @abstractmethod
43 def le(self, key: T) -> Optional[T]:
44 raise NotImplementedError
45
46 @abstractmethod
47 def lt(self, key: T) -> Optional[T]:
48 raise NotImplementedError
49
50 @abstractmethod
51 def ge(self, key: T) -> Optional[T]:
52 raise NotImplementedError
53
54 @abstractmethod
55 def gt(self, key: T) -> Optional[T]:
56 raise NotImplementedError
57
58 @abstractmethod
59 def get_max(self) -> Optional[T]:
60 raise NotImplementedError
61
62 @abstractmethod
63 def get_min(self) -> Optional[T]:
64 raise NotImplementedError
65
66 @abstractmethod
67 def pop_max(self) -> T:
68 raise NotImplementedError
69
70 @abstractmethod
71 def pop_min(self) -> T:
72 raise NotImplementedError
73
74 @abstractmethod
75 def clear(self) -> None:
76 raise NotImplementedError
77
78 @abstractmethod
79 def tolist(self) -> list[T]:
80 raise NotImplementedError
81
82 @abstractmethod
83 def __iter__(self) -> Iterator:
84 raise NotImplementedError
85
86 @abstractmethod
87 def __next__(self) -> T:
88 raise NotImplementedError
89
90 @abstractmethod
91 def __contains__(self, key: T) -> bool:
92 raise NotImplementedError
93
94 @abstractmethod
95 def __len__(self) -> int:
96 raise NotImplementedError
97
98 @abstractmethod
99 def __bool__(self) -> bool:
100 raise NotImplementedError
101
102 @abstractmethod
103 def __str__(self) -> str:
104 raise NotImplementedError
105
106 @abstractmethod
107 def __repr__(self) -> str:
108 raise NotImplementedError
109# from titan_pylib.my_class.supports_less_than import SupportsLessThan
110# from titan_pylib.data_structures.bst_base.bst_multiset_array_base import (
111# BSTMultisetArrayBase,
112# )
113from typing import TypeVar, Generic, Optional
114
115T = TypeVar("T")
116BST = TypeVar("BST")
117# protcolで、key,val,left,right を規定
118
119
120class BSTMultisetArrayBase(Generic[BST, T]):
121
122 @staticmethod
123 def _rle(a: list[T]) -> tuple[list[T], list[int]]:
124 keys, vals = [a[0]], [1]
125 for i, elm in enumerate(a):
126 if i == 0:
127 continue
128 if elm == keys[-1]:
129 vals[-1] += 1
130 continue
131 keys.append(elm)
132 vals.append(1)
133 return keys, vals
134
135 @staticmethod
136 def count(bst: BST, key: T) -> int:
137 keys, left, right = bst.key, bst.left, bst.right
138 node = bst.root
139 while node:
140 if keys[node] == key:
141 return bst.val[node]
142 node = left[node] if key < keys[node] else right[node]
143 return 0
144
145 @staticmethod
146 def le(bst: BST, key: T) -> Optional[T]:
147 keys, left, right = bst.key, bst.left, bst.right
148 res = None
149 node = bst.root
150 while node:
151 if key == keys[node]:
152 res = key
153 break
154 if key < keys[node]:
155 node = left[node]
156 else:
157 res = keys[node]
158 node = right[node]
159 return res
160
161 @staticmethod
162 def lt(bst: BST, key: T) -> Optional[T]:
163 keys, left, right = bst.key, bst.left, bst.right
164 res = None
165 node = bst.root
166 while node:
167 if key <= keys[node]:
168 node = left[node]
169 else:
170 res = keys[node]
171 node = right[node]
172 return res
173
174 @staticmethod
175 def ge(bst: BST, key: T) -> Optional[T]:
176 keys, left, right = bst.key, bst.left, bst.right
177 res = None
178 node = bst.root
179 while node:
180 if key == keys[node]:
181 res = key
182 break
183 if key < keys[node]:
184 res = keys[node]
185 node = left[node]
186 else:
187 node = right[node]
188 return res
189
190 @staticmethod
191 def gt(bst: BST, key: T) -> Optional[T]:
192 keys, left, right = bst.key, bst.left, bst.right
193 res = None
194 node = bst.root
195 while node:
196 if key < keys[node]:
197 res = keys[node]
198 node = left[node]
199 else:
200 node = right[node]
201 return res
202
203 @staticmethod
204 def index(bst: BST, key: T) -> int:
205 keys, left, right, vals, valsize = (
206 bst.key,
207 bst.left,
208 bst.right,
209 bst.val,
210 bst.valsize,
211 )
212 k = 0
213 node = bst.root
214 while node:
215 if key == keys[node]:
216 if left[node]:
217 k += valsize[left[node]]
218 break
219 if key < keys[node]:
220 node = left[node]
221 else:
222 k += valsize[left[node]] + vals[node]
223 node = right[node]
224 return k
225
226 @staticmethod
227 def index_right(bst: BST, key: T) -> int:
228 keys, left, right, vals, valsize = (
229 bst.key,
230 bst.left,
231 bst.right,
232 bst.val,
233 bst.valsize,
234 )
235 k = 0
236 node = bst.root
237 while node:
238 if key == keys[node]:
239 k += valsize[left[node]] + vals[node]
240 break
241 if key < keys[node]:
242 node = left[node]
243 else:
244 k += valsize[left[node]] + vals[node]
245 node = right[node]
246 return k
247
248 @staticmethod
249 def _kth_elm(bst: BST, k: int) -> tuple[T, int]:
250 left, right, vals, valsize = bst.left, bst.right, bst.val, bst.valsize
251 if k < 0:
252 k += len(bst)
253 node = bst.root
254 while True:
255 t = vals[node] + valsize[left[node]]
256 if t - vals[node] <= k < t:
257 return bst.key[node], vals[node]
258 if t > k:
259 node = left[node]
260 else:
261 node = right[node]
262 k -= t
263
264 @staticmethod
265 def contains(bst: BST, key: T) -> bool:
266 left, right, keys = bst.left, bst.right, bst.key
267 node = bst.root
268 while node:
269 if keys[node] == key:
270 return True
271 node = left[node] if key < keys[node] else right[node]
272 return False
273
274 @staticmethod
275 def tolist(bst: BST) -> list[T]:
276 left, right, keys, vals = bst.left, bst.right, bst.key, bst.val
277 node = bst.root
278 stack, a = [], []
279 while stack or node:
280 if node:
281 stack.append(node)
282 node = left[node]
283 else:
284 node = stack.pop()
285 key = keys[node]
286 for _ in range(vals[node]):
287 a.append(key)
288 node = right[node]
289 return a
290from typing import Generic, Iterable, Iterator, TypeVar, Optional
291from array import array
292
293T = TypeVar("T", bound=SupportsLessThan)
294
295
296class AVLTreeMultiset(OrderedMultisetInterface, Generic[T]):
297 """
298 多重集合としての AVL 木です。
299 配列を用いてノードを表現しています。
300 size を持ちます。
301 """
302
303 def __init__(self, a: Iterable[T] = []):
304 self.root = 0
305 self.key = [0]
306 self.val = [0]
307 self.valsize = [0]
308 self.size = array("I", bytes(4))
309 self.left = array("I", bytes(4))
310 self.right = array("I", bytes(4))
311 self.balance = array("b", bytes(1))
312 self.end = 1
313 if not isinstance(a, list):
314 a = list(a)
315 if a:
316 self._build(a)
317
318 def _make_node(self, key: T, val: int) -> int:
319 end = self.end
320 if end >= len(self.key):
321 self.key.append(key)
322 self.val.append(val)
323 self.valsize.append(val)
324 self.size.append(1)
325 self.left.append(0)
326 self.right.append(0)
327 self.balance.append(0)
328 else:
329 self.key[end] = key
330 self.val[end] = val
331 self.valsize[end] = val
332 self.end += 1
333 return end
334
335 def reserve(self, n: int) -> None:
336 a = [0] * n
337 self.key += a
338 self.val += a
339 self.valsize += a
340 a = array("I", bytes(4 * n))
341 self.left += a
342 self.right += a
343 self.size += array("I", [1] * n)
344 self.balance += array("b", bytes(n))
345
346 def _build(self, a: list[T]) -> None:
347 left, right, size, valsize, balance = (
348 self.left,
349 self.right,
350 self.size,
351 self.valsize,
352 self.balance,
353 )
354
355 def sort(l: int, r: int) -> tuple[int, int]:
356 mid = (l + r) >> 1
357 node = mid
358 hl, hr = 0, 0
359 if l != mid:
360 left[node], hl = sort(l, mid)
361 size[node] += size[left[node]]
362 valsize[node] += valsize[left[node]]
363 if mid + 1 != r:
364 right[node], hr = sort(mid + 1, r)
365 size[node] += size[right[node]]
366 valsize[node] += valsize[right[node]]
367 balance[node] = hl - hr
368 return node, max(hl, hr) + 1
369
370 if not all(a[i] <= a[i + 1] for i in range(len(a) - 1)):
371 a = sorted(a)
372 if not a:
373 return
374 x, y = BSTMultisetArrayBase[AVLTreeMultiset, T]._rle(a)
375 n = len(x)
376 end = self.end
377 self.end += n
378 self.reserve(n)
379 self.key[end : end + n] = x
380 self.val[end : end + n] = y
381 self.valsize[end : end + n] = y
382 self.root = sort(end, n + end)[0]
383
384 def _rotate_L(self, node: int) -> int:
385 left, right, size, valsize, balance = (
386 self.left,
387 self.right,
388 self.size,
389 self.valsize,
390 self.balance,
391 )
392 u = left[node]
393 size[u] = size[node]
394 valsize[u] = valsize[node]
395 if left[u] == 0:
396 size[node] -= 1
397 valsize[node] -= self.val[u]
398 else:
399 size[node] -= size[left[u]] + 1
400 valsize[node] -= valsize[left[u]] + self.val[u]
401 left[node] = right[u]
402 right[u] = node
403 if balance[u] == 1:
404 balance[u] = 0
405 balance[node] = 0
406 else:
407 balance[u] = -1
408 balance[node] = 1
409 return u
410
411 def _rotate_R(self, node: int) -> int:
412 left, right, size, valsize, balance = (
413 self.left,
414 self.right,
415 self.size,
416 self.valsize,
417 self.balance,
418 )
419 u = right[node]
420 size[u] = size[node]
421 valsize[u] = valsize[node]
422 if right[u] == 0:
423 size[node] -= 1
424 valsize[node] -= self.val[u]
425 else:
426 size[node] -= size[right[u]] + 1
427 valsize[node] -= valsize[right[u]] + self.val[u]
428 right[node] = left[u]
429 left[u] = node
430 if balance[u] == -1:
431 balance[u] = 0
432 balance[node] = 0
433 else:
434 balance[u] = 1
435 balance[node] = -1
436 return u
437
438 def _update_balance(self, node: int) -> None:
439 left, right, balance = self.left, self.right, self.balance
440 if balance[node] == 1:
441 balance[right[node]] = -1
442 balance[left[node]] = 0
443 elif balance[node] == -1:
444 balance[right[node]] = 0
445 balance[left[node]] = 1
446 else:
447 balance[right[node]] = 0
448 balance[left[node]] = 0
449 balance[node] = 0
450
451 def _rotate_LR(self, node: int) -> int:
452 left, right, size, valsize = self.left, self.right, self.size, self.valsize
453 B = left[node]
454 E = right[B]
455 size[E] = size[node]
456 valsize[E] = valsize[node]
457 if right[E] == 0:
458 size[node] -= size[B]
459 valsize[node] -= valsize[B]
460 size[B] -= 1
461 valsize[B] -= self.val[E]
462 else:
463 size[node] -= size[B] - size[right[E]]
464 valsize[node] -= valsize[B] - valsize[right[E]]
465 size[B] -= size[right[E]] + 1
466 valsize[B] -= valsize[right[E]] + self.val[E]
467 right[B] = left[E]
468 left[E] = B
469 left[node] = right[E]
470 right[E] = node
471 self._update_balance(E)
472 return E
473
474 def _rotate_RL(self, node: int) -> int:
475 left, right, size, valsize = self.left, self.right, self.size, self.valsize
476 C = right[node]
477 D = left[C]
478 size[D] = size[node]
479 valsize[D] = valsize[node]
480 if left[D] == 0:
481 size[node] -= size[C]
482 valsize[node] -= valsize[C]
483 size[C] -= 1
484 valsize[C] -= self.val[D]
485 else:
486 size[node] -= size[C] - size[left[D]]
487 valsize[node] -= valsize[C] - valsize[left[D]]
488 size[C] -= size[left[D]] + 1
489 valsize[C] -= valsize[left[D]] + self.val[D]
490 left[C] = right[D]
491 right[D] = C
492 right[node] = left[D]
493 left[D] = node
494 self._update_balance(D)
495 return D
496
497 def _kth_elm(self, k: int) -> tuple[T, int]:
498 return BSTMultisetArrayBase[AVLTreeMultiset, T]._kth_elm(self, k)
499
500 def _kth_elm_tree(self, k: int) -> tuple[T, int]:
501 left, right, vals, size = self.left, self.right, self.val, self.size
502 if k < 0:
503 k += self.len_elm()
504 assert 0 <= k < self.len_elm()
505 node = self.root
506 while True:
507 t = size[left[node]]
508 if t == k:
509 return self.key[node], vals[node]
510 if t > k:
511 node = left[node]
512 else:
513 node = right[node]
514 k -= t + 1
515
516 def _discard(self, node: int, path: list[int], di: int) -> bool:
517 left, right, keys, vals = self.left, self.right, self.key, self.val
518 balance, size, valsize = self.balance, self.size, self.valsize
519 fdi = 0
520 if left[node] and right[node]:
521 path.append(node)
522 di <<= 1
523 di |= 1
524 lmax = left[node]
525 while right[lmax]:
526 path.append(lmax)
527 di <<= 1
528 fdi <<= 1
529 fdi |= 1
530 lmax = right[lmax]
531 lmax_val = vals[lmax]
532 keys[node] = keys[lmax]
533 vals[node] = lmax_val
534 node = lmax
535 cnode = right[node] if left[node] == 0 else left[node]
536 if path:
537 if di & 1:
538 left[path[-1]] = cnode
539 else:
540 right[path[-1]] = cnode
541 else:
542 self.root = cnode
543 return True
544 while path:
545 new_node = 0
546 pnode = path.pop()
547 balance[pnode] -= 1 if di & 1 else -1
548 size[pnode] -= 1
549 valsize[pnode] -= lmax_val if fdi & 1 else 1
550 di >>= 1
551 fdi >>= 1
552 if balance[pnode] == 2:
553 new_node = (
554 self._rotate_LR(pnode)
555 if balance[left[pnode]] < 0
556 else self._rotate_L(pnode)
557 )
558 elif balance[pnode] == -2:
559 new_node = (
560 self._rotate_RL(pnode)
561 if balance[right[pnode]] > 0
562 else self._rotate_R(pnode)
563 )
564 elif balance[pnode] != 0:
565 break
566 if new_node:
567 if not path:
568 self.root = new_node
569 return
570 if di & 1:
571 left[path[-1]] = new_node
572 else:
573 right[path[-1]] = new_node
574 if balance[new_node] != 0:
575 break
576 while path:
577 pnode = path.pop()
578 size[pnode] -= 1
579 valsize[pnode] -= lmax_val if fdi & 1 else 1
580 fdi >>= 1
581 return True
582
583 def discard(self, key: T, val: int = 1) -> bool:
584 keys, vals, left, right, valsize = (
585 self.key,
586 self.val,
587 self.left,
588 self.right,
589 self.valsize,
590 )
591 path = []
592 di = 0
593 node = self.root
594 while node:
595 if key == keys[node]:
596 break
597 path.append(node)
598 di <<= 1
599 if key < keys[node]:
600 di |= 1
601 node = left[node]
602 else:
603 node = right[node]
604 else:
605 return False
606 if val > vals[node]:
607 val = vals[node] - 1
608 vals[node] -= val
609 valsize[node] -= val
610 for p in path:
611 valsize[p] -= val
612 if vals[node] == 1:
613 self._discard(node, path, di)
614 else:
615 vals[node] -= val
616 valsize[node] -= val
617 for p in path:
618 valsize[p] -= val
619 return True
620
621 def discard_all(self, key: T) -> None:
622 self.discard(key, self.count(key))
623
624 def remove(self, key: T, val: int = 1) -> None:
625 if self.discard(key, val):
626 return
627 raise KeyError(key)
628
629 def add(self, key: T, val: int = 1) -> None:
630 if self.root == 0:
631 self.root = self._make_node(key, val)
632 return
633 left, right, keys, valsize = self.left, self.right, self.key, self.valsize
634 size, balance = self.size, self.balance
635 node = self.root
636 di = 0
637 path = []
638 while node:
639 if key == keys[node]:
640 self.val[node] += val
641 valsize[node] += val
642 for p in path:
643 valsize[p] += val
644 return
645 path.append(node)
646 di <<= 1
647 if key < keys[node]:
648 di |= 1
649 node = left[node]
650 else:
651 node = right[node]
652 if di & 1:
653 left[path[-1]] = self._make_node(key, val)
654 else:
655 right[path[-1]] = self._make_node(key, val)
656 new_node = 0
657 while path:
658 node = path.pop()
659 size[node] += 1
660 valsize[node] += val
661 balance[node] += 1 if di & 1 else -1
662 di >>= 1
663 if balance[node] == 0:
664 break
665 if balance[node] == 2:
666 new_node = (
667 self._rotate_LR(node)
668 if balance[left[node]] < 0
669 else self._rotate_L(node)
670 )
671 break
672 elif balance[node] == -2:
673 new_node = (
674 self._rotate_RL(node)
675 if balance[right[node]] > 0
676 else self._rotate_R(node)
677 )
678 break
679 if new_node:
680 if path:
681 if di & 1:
682 left[path[-1]] = new_node
683 else:
684 right[path[-1]] = new_node
685 else:
686 self.root = new_node
687 for p in path:
688 size[p] += 1
689 valsize[p] += val
690
691 def count(self, key: T) -> int:
692 return BSTMultisetArrayBase[AVLTreeMultiset, T].count(self, key)
693
694 def le(self, key: T) -> Optional[T]:
695 return BSTMultisetArrayBase[AVLTreeMultiset, T].le(self, key)
696
697 def lt(self, key: T) -> Optional[T]:
698 return BSTMultisetArrayBase[AVLTreeMultiset, T].lt(self, key)
699
700 def ge(self, key: T) -> Optional[T]:
701 return BSTMultisetArrayBase[AVLTreeMultiset, T].ge(self, key)
702
703 def gt(self, key: T) -> Optional[T]:
704 return BSTMultisetArrayBase[AVLTreeMultiset, T].gt(self, key)
705
706 def index(self, key: T) -> int:
707 return BSTMultisetArrayBase[AVLTreeMultiset, T].index(self, key)
708
709 def index_right(self, key: T) -> int:
710 return BSTMultisetArrayBase[AVLTreeMultiset, T].index_right(self, key)
711
712 def index_keys(self, key: T) -> int:
713 keys, left, right, vals, size = (
714 self.key,
715 self.left,
716 self.right,
717 self.val,
718 self.size,
719 )
720 k = 0
721 node = self.root
722 while node:
723 if key == keys[node]:
724 if left[node]:
725 k += size[left[node]]
726 break
727 if key < keys[node]:
728 node = left[node]
729 else:
730 k += size[left[node]] + vals[node]
731 node = right[node]
732 return k
733
734 def index_right_keys(self, key: T) -> int:
735 keys, left, right, vals, size = (
736 self.key,
737 self.left,
738 self.right,
739 self.val,
740 self.size,
741 )
742 k = 0
743 node = self.root
744 while node:
745 if key == keys[node]:
746 k += size[left[node]] + vals[node]
747 break
748 if key < keys[node]:
749 node = left[node]
750 else:
751 k += size[left[node]] + vals[node]
752 node = right[node]
753 return k
754
755 def get_min(self) -> Optional[T]:
756 if self.root == 0:
757 return
758 left = self.left
759 node = self.root
760 while left[node]:
761 node = left[node]
762 return self.key[node]
763
764 def get_max(self) -> Optional[T]:
765 if self.root == 0:
766 return
767 right = self.right
768 node = self.root
769 while right[node]:
770 node = right[node]
771 return self.key[node]
772
773 def pop(self, k: int = -1) -> T:
774 left, right, vals, valsize = self.left, self.right, self.val, self.valsize
775 keys = self.key
776 node = self.root
777 if k < 0:
778 k += valsize[node]
779 path = []
780 if k == valsize[node] - 1:
781 while right[node]:
782 path.append(node)
783 node = right[node]
784 x = keys[node]
785 if vals[node] == 1:
786 self._discard(node, path, 0)
787 else:
788 vals[node] -= 1
789 valsize[node] -= 1
790 for p in path:
791 valsize[p] -= 1
792 return x
793 di = 0
794 while True:
795 t = vals[node] + valsize[left[node]]
796 if t - vals[node] <= k < t:
797 x = keys[node]
798 break
799 path.append(node)
800 di <<= 1
801 if t > k:
802 di |= 1
803 node = left[node]
804 else:
805 node = right[node]
806 k -= t
807 if vals[node] == 1:
808 self._discard(node, path, di)
809 else:
810 vals[node] -= 1
811 valsize[node] -= 1
812 for p in path:
813 valsize[p] -= 1
814 return x
815
816 def pop_max(self) -> T:
817 assert self
818 return self.pop()
819
820 def pop_min(self) -> T:
821 assert self
822 return self.pop(0)
823
824 def items(self) -> Iterator[tuple[T, int]]:
825 for i in range(self.len_elm()):
826 yield self._kth_elm_tree(i)
827
828 def keys(self) -> Iterator[T]:
829 for i in range(self.len_elm()):
830 yield self._kth_elm_tree(i)[0]
831
832 def values(self) -> Iterator[int]:
833 for i in range(self.len_elm()):
834 yield self._kth_elm_tree(i)[1]
835
836 def len_elm(self) -> int:
837 return self.size[self.root]
838
839 def show(self) -> None:
840 print(
841 "{" + ", ".join(map(lambda x: f"{x[0]}: {x[1]}", self.tolist_items())) + "}"
842 )
843
844 def clear(self) -> None:
845 self.root = 0
846
847 def get_elm(self, k: int) -> T:
848 return self._kth_elm_tree(k)[0]
849
850 def tolist(self) -> list[T]:
851 return BSTMultisetArrayBase[AVLTreeMultiset, T].tolist(self)
852
853 def tolist_items(self) -> list[tuple[T, int]]:
854 left, right, keys, vals = self.left, self.right, self.key, self.val
855 node = self.root
856 stack, a = [], []
857 while stack or node:
858 if node:
859 stack.append(node)
860 node = left[node]
861 else:
862 node = stack.pop()
863 a.append((keys[node], vals[node]))
864 node = right[node]
865 return a
866
867 def __getitem__(self, k: int) -> T:
868 return self._kth_elm(k)[0]
869
870 def __contains__(self, key: T):
871 return BSTMultisetArrayBase[AVLTreeMultiset, T].contains(self, key)
872
873 def __iter__(self):
874 self.__iter = 0
875 return self
876
877 def __next__(self):
878 if self.__iter == len(self):
879 raise StopIteration
880 res = self._kth_elm(self.__iter)
881 self.__iter += 1
882 return res
883
884 def __reversed__(self):
885 for i in range(len(self)):
886 yield self._kth_elm(-i - 1)[0]
887
888 def __len__(self):
889 return self.valsize[self.root]
890
891 def __bool__(self):
892 return self.root != 0
893
894 def __str__(self):
895 return "{" + ", ".join(map(str, self.tolist())) + "}"
896
897 def __repr__(self):
898 return f"{self.__class__.__name__}({self.tolist()})"
仕様¶
- class AVLTreeMultiset(a: Iterable[T] = [])[source]¶
Bases:
OrderedMultisetInterface,Generic[T]多重集合としての AVL 木です。 配列を用いてノードを表現しています。 size を持ちます。