BinarySearchTree

Двоичное дерево поиска, или BST, — это структура данных, предназначенная для работы с упорядоченными множествами.

Свойство дерева: если мы находимся в вершине с ключом k, то в левом поддереве находятся только ключи, которые строго меньше k, а в правом — строго больше.

Описание методов, реализованных в классе BinarySearchTree:

  • метод add():
    • если дерево пустое, то говорим, что корень — это наш узел;
    • сравниваем поступивший ключ с ключом узла:
      • если ключ меньше, то идём в левое поддерево;
      • если ключ равен, то задаём узлу новое поступившее значение;
      • если ключ больше, то идём в правое поддерево;
  • методы minKey() и maxKey():
    • по свойству дерева, минимальный ключ располагается в самом левом поддереве, а максимальный — в самом правом;
  • метод delete():
    • сначала находим нужный элемент по ключу (если такового нет, то выходим из метода);
    • если у удаляемого узла нет правого поддерева, то мы просто замещаем узел его левым поддеревом;
    • иначе находим в правом поддереве узел с минимальным ключом:
      • если у этого узла родитель — это удаляемый узел, то мы просто говорим, что правое поддерево удаляемого узла есть правое поддерево найденного, а ключ и значение удаляемого узла — это ключ и значение найденного;
      • если у этого узла другой родитель, то мы замещаем найденный узел его же правым поддеревом, а ключ и значение удаляемого узла — это ключ и значение найденного;

Код программы (http://ideone.com/Z2hbBv):

 

One thought on “BinarySearchTree

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *