Ключ в поле данных работает как этикетка, с помощью которой можно идентифицировать узел. Во многих приложениях элементы данных являются записями, состоящими из отдельных полей. Ключом может быть все поле данных, или только его часть. Например, номер социальной страховки является ключом, идентифицирующим студента университета.
| Номер социальной страховки (9-символьная строка)
| Имя студента (строка)
| Средний балл (число с плавающей точкой)
|
| ключевое поле
| |
|
struct Student
{
String ssn;
String name;
float gpa;
}
Рис. 11. Примеры деревьев бинарного поиска
На Рис. 11 узлы содержат единственное целочисленное значение, которое и является ключом. В этом случае узел 25 имеет ключ 25, и мы сравниваем два узла путем сравнения целых чисел. Сравнение производится с помощью целочисленных операторов отношения "<" и "==". Для студента университета ключом является ssn, и мы сравниваем две символьные строки. Это делается с помощью перегрузки операций. Например, следующий код реализует отношение "<" для двух объектов Student:
int operator < (const Student& s, const Student& t)
{
return s.ssn < t.ssn; // сравнить ключи ssn
}
В наших приложениях мы приводим ряд примеров ключ/данные. В иллюстрациях мы используем простой формат, где ключ и данные - одно и то же.
