4)Деревья двоичного поиска. Методы их реализации.
Дерево двоичного поиска - это двоичное дерево, узлы которого помечены элементами множеств (узлы дерева содержат или хранят элементы множества). Определяющее свойство дерева двоичного поиска заключается в том, что все элементы, хранящиеся в узлах левого поддерева любого узла х, меньше элемента, содержащегося в узле х, а все элементы, хранящиеся в узлах правого поддерева узла х, больше элемента, содержащегося в узле х.
Это свойство называется характеристическим свойством дерева двоичного поиска и выполняется для любого узла дерева двоичного поиска, включая его корень.
Отметим интересное свойство деревьев двоичного поиска:
если составить список узлов этого дерева, обходя его во внутреннем (симметричном) порядке, то полученный список будет отсортирован в порядке возрастания (в соответствии с заданным на множестве отношением линейного порядка).
Пусть дерево двоичного поиска представляет некоторое множество элементов. Характеристическое свойство дерева двоичного поиска позволяет легко проверить принадлежность любого элемента исходному множеству.
Для того чтобы определить, принадлежит ли элемент х исходному множеству, сначала сравним его с элементом r, находящимся в корне дерева.
Если х = r, то вопрос о принадлежности элемента х множеству решен положительно.
В случае х < r по характеристическому свойству дерева двоичного поиска элемент х может быть потомком только левого сына корня дерева.
А
налогично,
если х > r,
то элемент х
может быть потомком только правого
сына корня дерева.
На рисунке показаны два дерева двоичного поиска, представляющие одно и то же множество целых чисел.
Пусть дерево двоичного поиска представляет некоторое множество элементов. Характеристическое свойство дерева двоичного поиска позволяет легко проверить принадлежность любого элемента исходному множеству.
Для того чтобы определить, принадлежит ли элемент х исходному множеству, сначала сравним его с элементом r, находящимся в корне дерева.
Если х = r, то вопрос о принадлежности элемента х множеству решен положительно.
В случае х < r по характеристическому свойству дерева двоичного поиска элемент х может быть потомком только левого сына корня дерева.
Аналогично, если х > r, то элемент х может быть потомком только правого сына корня дерева
Тип данных nodetype узлов дерева, содержащих поле element для элементов множества и два поля leftchild и rightchild указателей на левого и правого сыновей, определен следующим образом:
type nodetype = record
element: elementtype;
leftchild, rightchild: ^nodetype
end;
Тип данных SET (Множество) определен как указатель на узел, который будет корнем дерева двоичного поиска при представлении множества:
type SET: ^nodetype;
function MEMBER ( х: elementtype; A: SET ): boolean;
begin if A = nil then MEMBER:=false { x не может принадлежать }
else if x = A^.element then MEMBER:= true
else if x < A^.element then MEMBER:=MEMBER(x, A^.leftchild)
else { x > A^.element } MEMBER:=(MEMBER(x, A^.rightchild))
end;
Билет №16.