Мне нравятся разные деревья, но больше всего мне нравится бинарное дерево поиска. Когда я читал студенческий курс по структурам данных в UT Austin, моим любимым вопросом на выпускном экзамене было удаление элемента в двоичном дереве поиска или перебалансировка кучи. Я надеюсь, что любимыми деревьями моих аспирантов являются «абстрактные синтаксические деревья», поскольку большинство моих аспирантов работают над анализом программного обеспечения и инструментарием, а их исследования включают обход, манипулирование и извлечение информации из абстрактных синтаксических деревьев.
Поэтому я начала задавать вопросы Софии и ее друзьям — какое ваше любимое дерево? Их ответы: цветочные деревья, фруктовые деревья, радужные деревья и радужные фруктовые деревья. эм>. Я сказал Софии и ее друзьям, что в компьютерных науках большинство деревьев перевернуты. Для наглядности я поместил плакат с изображением дерева вверх ногами с такими ключевыми терминами, как ствол, ветка и лист.
Затем я принесла карточки с совами, которые сделала, наклеив на них наклейки с цифрами. Двоичное дерево поиска — это структура данных, предназначенная для быстрого поиска и проверки содержимого. У каждого узла есть два дочерних узла, где левый дочерний элемент меньше своего родителя, а правый дочерний элемент больше своего родителя.
Затем мы начали вставлять сов в бинарное дерево поиска. Сначала я попрошу каждого ребенка выбрать карточку с совой. (София любит розовый!) Затем мы начнем с корня дерева, чтобы увидеть, в какой узел мы можем вставить карту совы.
София и ее подруга Айрис создали свое собственное бинарное дерево поиска, приклеивая на плакат каждую карточку с изображением совы по одной.
Затем я рассказал о том, сколько всего сов на дереве. Затем я посчитал глубину дерева. Суть структуры данных бинарного дерева поиска заключается в том, что в среднем она обеспечивает log n времени для поиска, когда дерево имеет n узлов. Поэтому я объяснил Софии, на сколько там больше сов по сравнению с высотой дерева. Мы также использовали бинарное дерево поиска, чтобы проверить, содержится ли сова с определенным числом, путем моделирования определенного пути обхода поиска — например, есть ли у нас сова с номером 5 на этом дереве?
