В языках, подобных С, мы бы делали это, изменяя указатели и значения внутри дерева. В Haskell мы на самом деле не можем изменять наше дерево – придётся создавать новое поддерево каждый раз, когда мы переходим к левому или правому поддереву. Таким образом, в конце функции добавления мы вернём полностью новое дерево, потому что в языке Haskell нет концепции указателей, есть только значения. Следовательно, тип функции для добавления элемента будет примерно следующим: >a –> Tree a – > Tree a. Она принимает элемент и дерево и возвращает новое дерево с уже добавленным элементом. Это может показаться неэффективным, но язык Haskell умеет организовывать совместное владение большей частью поддеревьев старым и новым деревьями.
Итак, напишем две функции. Первая будет вспомогательной функцией для создания дерева, состоящего из одного элемента; вторая будет вставлять элемент в дерево.
>singleton :: a –> Tree a
>singleton x = Node x EmptyTree EmptyTree
>treeInsert :: (Ord a) => a –> Tree a –> Tree a
>treeInsert x EmptyTree = singleton x
>treeInsert x (Node a left right)
> | x == a = Node x left right
> | x < a = Node a (treeInsert x left) right
> | x > a = Node a left (treeInsert x right)
Функция >singleton служит для создания узла, который хранит некоторое значение и два пустых поддерева. В функции для добавления нового элемента в дерево мы вначале обрабатываем граничное условие. Если мы достигли пустого поддерева, это значит, что мы в нужном месте нашего дерева, и вместо пустого дерева помещаем одноэлементное дерево, созданное из нашего значения. Если мы вставляем не в пустое дерево, следует кое-что проверить. Первое: если вставляемый элемент равен корневому элементу – просто возвращаем дерево текущего элемента. Если он меньше, возвращаем дерево, которое имеет то же корневое значение и то же правое поддерево, но вместо левого поддерева помещаем дерево с добавленным элементом. Так же (но с соответствующими поправками) обстоит дело, если значение больше, чем корневой элемент.
Следующей мы напишем функцию для проверки, входит ли некоторый элемент в наше дерево или нет. Для начала определим базовые случаи. Если мы ищем элемент в пустом дереве, его там определённо нет. Заметили – такой же базовый случай мы использовали для поиска элемента в списке? Если мы ищем в пустом списке, то ничего не найдём. Если ищем не в пустом дереве, надо проверить несколько условий. Если элемент в текущем корне равен тому, что мы ищем, – отлично. Ну а если нет, тогда как быть?.. Мы можем извлечь пользу из того, что все элементы в левом поддереве меньше корневого элемента. Поэтому, если искомый элемент меньше корневого, начинаем искать в левом поддереве. Если он больше – ищем в правом поддереве.