Реализация итератора по бинарному дереву поиска
Недавно я написал множество различных реализаций бинарного дерева поиска (AVL, splay, treap), и мне любопытно, есть ли особенно "хороший" способ написать итератор для обхода этих структур. Решение, которое я использовал прямо сейчас, состоит в том, чтобы каждый узел в BST сохранял указатели на следующий и предыдущий элементы в дереве, что сводит итерацию к стандартной итерации связанного списка. Однако я не очень доволен этим ответом. Это увеличивает использование пространства каждого узла на два указателя (следующий и предыдущий), и в некотором смысле это просто обман.
Я знаю способ построения итератора бинарного дерева поиска, который использует O(h) вспомогательное пространство памяти (где h - высота дерева), используя стек для отслеживания пограничных узлов для дальнейшего изучения, но я ' мы сопротивлялись кодированию из-за использования памяти. Я надеялся, что есть какой-то способ построить итератор, который использует только постоянное пространство.
Мой вопрос заключается в следующем: есть ли способ создать итератор для двоичного дерева поиска со следующими свойствами?
- Элементы посещаются в порядке возрастания (т.е. обход по порядку)
next()а такжеhasNext()запросы выполняются за O(1) раз.- Использование памяти O(1)
Чтобы сделать это проще, хорошо, если вы предполагаете, что древовидная структура не меняет форму во время итерации (то есть без вставок, удалений или вращений), но было бы очень здорово, если бы было решение, которое действительно могло бы справиться с этим.
8 ответов
Простейший из возможных итераторов сохраняет последний увиденный ключ, а затем на следующей итерации ищет в дереве наименее верхнюю границу для этого ключа. Итерация O(log n). Это имеет то преимущество, что очень прост. Если ключи маленькие, итераторы тоже маленькие. конечно, у него есть недостаток, заключающийся в том, что он является относительно медленным способом итерации по дереву. Это также не будет работать для неуникальных последовательностей.
Некоторые деревья используют именно ту реализацию, которую вы уже используете, потому что для их конкретного использования важно, чтобы сканирование было очень быстрым. Если количество ключей в каждом узле велико, то наказание за хранение указателей на одноуровневый элемент не слишком обременительно. Большинство B-деревьев используют этот метод.
многие реализации дерева поиска поддерживают родительский указатель на каждом узле, чтобы упростить другие операции. Если у вас есть это, то вы можете использовать простой указатель на последний увиденный узел в качестве состояния вашего итератора. на каждой итерации вы ищите следующего потомка в последнем родительском узле. если больше нет братьев и сестер, тогда вы поднимаетесь на еще один уровень.
Если ни один из этих методов вам не подходит, вы можете использовать стек узлов, сохраненных в итераторе. Это выполняет ту же функцию, что и стек вызовов функций, когда выполняется итерация по дереву поиска в обычном режиме, но вместо того, чтобы циклически проходить по одноуровневым элементам и возвращаться к дочерним элементам, вы помещаете дочерние элементы в стек и возвращаете каждого последующего одноуровневого элемента.
Как упомянул TokenMacGuy, вы можете использовать стек, хранящийся в итераторе. Вот быстрая проверенная реализация этого в Java:
/**
* An iterator that iterates through a tree using in-order tree traversal
* allowing a sorted sequence.
*
*/
public class Iterator {
private Stack<Node> stack = new Stack<>();
private Node current;
private Iterator(Node argRoot) {
current = argRoot;
}
public Node next() {
while (current != null) {
stack.push(current);
current = current.left;
}
current = stack.pop();
Node node = current;
current = current.right;
return node;
}
public boolean hasNext() {
return (!stack.isEmpty() || current != null);
}
public static Iterator iterator(Node root) {
return new Iterator(root);
}
}
Другим вариантом может быть обход дерева во время создания и сохранение обхода в списке. Вы можете использовать итератор списка впоследствии.
Хорошо, я знаю, что это старо, но меня спросили об этом в интервью с Microsoft некоторое время назад, и я решил немного поработать над этим. Я проверил это, и это работает довольно хорошо.
template <typename E>
class BSTIterator
{
BSTNode<E> * m_curNode;
std::stack<BSTNode<E>*> m_recurseIter;
public:
BSTIterator( BSTNode<E> * binTree )
{
BSTNode<E>* root = binTree;
while(root != NULL)
{
m_recurseIter.push(root);
root = root->GetLeft();
}
if(m_recurseIter.size() > 0)
{
m_curNode = m_recurseIter.top();
m_recurseIter.pop();
}
else
m_curNode = NULL;
}
BSTNode<E> & operator*() { return *m_curNode; }
bool operator==(const BSTIterator<E>& other)
{
return m_curNode == other.m_curNode;
}
bool operator!=(const BSTIterator<E>& other)
{
return !(*this == other);
}
BSTIterator<E> & operator++()
{
if(m_curNode->GetRight())
{
m_recurseIter.push(m_curNode->GetRight());
if(m_curNode->GetRight()->GetLeft())
m_recurseIter.push(m_curNode->GetRight()->GetLeft());
}
if( m_recurseIter.size() == 0)
{
m_curNode = NULL;
return *this;
}
m_curNode = m_recurseIter.top();
m_recurseIter.pop();
return *this;
}
BSTIterator<E> operator++ ( int )
{
BSTIterator<E> cpy = *this;
if(m_curNode->GetRight())
{
m_recurseIter.push(m_curNode->GetRight());
if(m_curNode->GetRight()->GetLeft())
m_recurseIter.push(m_curNode->GetRight()->GetLeft());
}
if( m_recurseIter.size() == 0)
{
m_curNode = NULL;
return *this;
}
m_curNode = m_recurseIter.top();
m_recurseIter.pop();
return cpy;
}
};
Обход дерева, из Википедии:
Для всех примеров реализации потребуется пространство стека вызовов, пропорциональное высоте дерева. В плохо сбалансированном дереве это может быть довольно значительным.
Мы можем удалить требование стека, поддерживая родительские указатели в каждом узле, или поточив дерево. В случае использования потоков это позволит значительно улучшить обход по порядку, хотя извлечение родительского узла, необходимого для обхода по предварительному заказу и после заказа, будет медленнее, чем простой алгоритм на основе стека.
В статье приведен псевдокод для итерации с состоянием O(1), который можно легко адаптировать к итератору.
По определению, next() и hasNext() не могут быть запущены за O(1) раз. Когда вы смотрите на конкретный узел в BST, вы не имеете представления о высоте и структуре других узлов, поэтому вы не можете просто "перейти" к правильному следующему узлу.
Однако сложность пространства может быть уменьшена до O(1) (за исключением памяти для самого BST). Вот как я мог бы сделать это в C:
struct node{
int value;
struct node *left, *right, *parent;
int visited;
};
struct node* iter_next(struct node* node){
struct node* rightResult = NULL;
if(node==NULL)
return NULL;
while(node->left && !(node->left->visited))
node = node->left;
if(!(node->visited))
return node;
//move right
rightResult = iter_next(node->right);
if(rightResult)
return rightResult;
while(node && node->visited)
node = node->parent;
return node;
}
Хитрость заключается в том, чтобы иметь и родительскую ссылку, и флаг посещения для каждого узла. На мой взгляд, мы можем утверждать, что это не дополнительное использование пространства, это просто часть структуры узла. И очевидно, что iter_next() должен вызываться без изменения состояния древовидной структуры (конечно), но также и то, что "посещенные" флаги не изменяют значения.
Вот функция тестера, которая вызывает iter_next() и печатает значение каждый раз для этого дерева:
27
/ \
20 62
/ \ / \
15 25 40 71
\ /
16 21
int main(){
//right root subtree
struct node node40 = {40, NULL, NULL, NULL, 0};
struct node node71 = {71, NULL, NULL, NULL, 0};
struct node node62 = {62, &node40, &node71, NULL, 0};
//left root subtree
struct node node16 = {16, NULL, NULL, NULL, 0};
struct node node21 = {21, NULL, NULL, NULL, 0};
struct node node15 = {15, NULL, &node16, NULL, 0};
struct node node25 = {25, &node21, NULL, NULL, 0};
struct node node20 = {20, &node15, &node25, NULL, 0};
//root
struct node node27 = {27, &node20, &node62, NULL, 0};
//set parents
node16.parent = &node15;
node21.parent = &node25;
node15.parent = &node20;
node25.parent = &node20;
node20.parent = &node27;
node40.parent = &node62;
node71.parent = &node62;
node62.parent = &node27;
struct node *iter_node = &node27;
while((iter_node = iter_next(iter_node)) != NULL){
printf("%d ", iter_node->value);
iter_node->visited = 1;
}
printf("\n");
return 1;
}
Который будет печатать значения в отсортированном порядке:
15 16 20 21 25 27 40 62 71
Если вы используете стек, вы получаете только "Использование дополнительной памяти O(h), h - высота дерева"). Однако, если вы хотите использовать только O(1) дополнительной памяти, вам необходимо записать следующий анализ: - Если у текущего узла есть правильный дочерний элемент: найдите минимум правого поддерева - Если у текущего узла нет правого дочернего элемента, вам нужно искать его из корня и постоянно обновлять его самого нижнего предка, который является его самым низким следующим узлом
public class Solution {
//@param root: The root of binary tree.
TreeNode current;
TreeNode root;
TreeNode rightMost;
public Solution(TreeNode root) {
if(root==null) return;
this.root = root;
current = findMin(root);
rightMost = findMax(root);
}
//@return: True if there has next node, or false
public boolean hasNext() {
if(current!=null && rightMost!=null && current.val<=rightMost.val) return true;
else return false;
}
//O(1) memory.
public TreeNode next() {
//1. if current has right child: find min of right sub tree
TreeNode tep = current;
current = updateNext();
return tep;
}
public TreeNode updateNext(){
if(!hasNext()) return null;
if(current.right!=null) return findMin(current.right);
//2. current has no right child
//if cur < root , go left; otherwise, go right
int curVal = current.val;
TreeNode post = null;
TreeNode tepRoot = root;
while(tepRoot!=null){
if(curVal<tepRoot.val){
post = tepRoot;
tepRoot = tepRoot.left;
}else if(curVal>tepRoot.val){
tepRoot = tepRoot.right;
}else {
current = post;
break;
}
}
return post;
}
public TreeNode findMin(TreeNode node){
while(node.left!=null){
node = node.left;
}
return node;
}
public TreeNode findMax(TreeNode node){
while(node.right!=null){
node = node.right;
}
return node;
}
}
Используйте O(1) пробел, что означает, что мы не будем использовать O(h) стек.
Начать:
hasNext ()? current.val <= endNode.val, чтобы проверить, является ли дерево полностью пройденным.
Найти мин через крайнее левое: мы можем всегда искать крайнее левое, чтобы найти следующее минимальное значение.
Как только крайний левый мин проверен (назовите его
current). Следующая минута будет в 2 случаях: Если current.right!= Null, мы можем продолжить поиск самого левого потомка current.right, как в следующую минуту. Или нам нужно оглянуться назад на родителя. Используйте двоичное дерево поиска, чтобы найти текущий родительский узел.
Примечание: при выполнении бинарного поиска для родителя убедитесь, что он удовлетворяет parent.left = current.
Потому что: если parent.right == текущий, этот родитель должен был посещаться раньше. В бинарном дереве поиска мы знаем, что parent.valpublic class BSTIterator {
public TreeNode root;
public TreeNode current;
public TreeNode endNode;
//@param root: The root of binary tree.
public BSTIterator(TreeNode root) {
if (root == null) {
return;
}
this.root = root;
this.current = root;
this.endNode = root;
while (endNode != null && endNode.right != null) {
endNode = endNode.right;
}
while (current != null && current.left != null) {
current = current.left;
}
}
//@return: True if there has next node, or false
public boolean hasNext() {
return current != null && current.val <= endNode.val;
}
//@return: return next node
public TreeNode next() {
TreeNode rst = current;
//current node has right child
if (current.right != null) {
current = current.right;
while (current.left != null) {
current = current.left;
}
} else {//Current node does not have right child.
current = findParent();
}
return rst;
}
//Find current's parent, where parent.left == current.
public TreeNode findParent(){
TreeNode node = root;
TreeNode parent = null;
int val = current.val;
if (val == endNode.val) {
return null;
}
while (node != null) {
if (val < node.val) {
parent = node;
node = node.left;
} else if (val > node.val) {
node = node.right;
} else {//node.val == current.val
break;
}
}
return parent;
}
}
Как насчет использования техники поиска в глубину? Объект итератора просто должен иметь стек уже посещенных узлов.