Урок 12: Деревья и бинарные деревья поиска

Представьте генеалогическое древо или папки внутри папок: нечто «сверху» разветвляется на элементы «снизу». Это «дерево» — каждая точка является «узлом» (node). В «бинарном дереве поиска» (BST) у каждого узла слева находятся меньшие значения, а справа — большие — прямо как при поиске слова в словаре

BST — это как поиск слова в словаре: открываете середину, и если слово идёт «раньше», вы пропускаете всю правую половину сразу. Каждое сравнение экономит половину работы — но только если страницы разделены поровну.

класс (class): Шаблон для небольшой коробки с полями. class TreeNode определяет коробку с тремя полями: val (значение) и left/right (потомки). TreeNode(5) создаёт такую коробку, а self просто означает «эта коробка» (та же идея, что и в уроке о связных списках).
бинарное дерево поиска: Бинарное дерево, в котором для каждого узла все значения в левом поддереве меньше, а все значения в правом поддереве больше.
обход дерева: Посещение каждого узла дерева в определённом порядке. Inorder (левый, узел, правый) на BST выдаёт значения отсортированными.
сбалансированное дерево: Дерево, высота которого составляет примерно log n, поэтому поиск занимает O(log n). Вырожденное дерево теряет это преимущество и достигает O(n).