使用avl树实现像素网格

Question

我需要使用一定数量的avl树实现(x_coord, y_coord, color)类型的像素三元组网格。特别是，我应该能够执行以下函数:

• nextInRow(x,y)
• nextInCol(x,y)
• readColor(x,y)

复杂度O(log n)。

我完全迷路了，不知道如何有效地做这件事。如有任何帮助或指示，将不胜感激。

Answer 1

使用avl树实现这一点的一个聪明的方法是有两个单独的avl树，一个按x坐标排序，另一个按y坐标排序。因此，您将使用第一个实现nextInRow(x,y)，第二个实现nextInCol(x,y)。