HeadSet, TailSet, SubSet in TreeSet

Question

Как работает связь между (headSet, TailSet, Subset) и TreeSet? Когда вы удаляете некоторые элементы из дерева, если эти элементы содержатся в Headset, TailSet или SubSet, они будут удалены в этих наборах. Я хочу сделать свою собственную реализацию двоичного дерева поиска, и я хочу знать, как работает это отношение. Может кто-нибудь объяснить или дать некоторые ресурсы, где я могу найти информацию? Это все, что у меня есть:
Интерфейс:

import java.util.*
interface CheckableSortedSet<T> : SortedSet<T> {
    fun checkInvariant(): Boolean
}

класс

    import java.util.*
    import kotlin.NoSuchElementException
    import java.util.TreeSet

class KtBinaryTree<T : Comparable<T>> : AbstractMutableSet<T>(), CheckableSortedSet<T> {

private var root: Node<T>? = null

override var size = 0
    private set

private class Node<T>(val value: T) {

    var left: Node<T>? = null

    var right: Node<T>? = null
}

override fun add(element: T): Boolean {
    val closest = find(element)
    val comparison = if (closest == null) -1 else element.compareTo(closest.value)
    if (comparison == 0) {
        return false
    }
    val newNode = Node(element)
    when {
        closest == null -> root = newNode
        comparison < 0 -> {
            assert(closest.left == null)
            closest.left = newNode
        }
        else -> {
            assert(closest.right == null)
            closest.right = newNode
        }
    }
    size++
    return true
}

override fun checkInvariant(): Boolean =
        root?.let { checkInvariant(it) } ?: true

private fun checkInvariant(node: Node<T>): Boolean {
    val left = node.left
    if (left != null && (left.value >= node.value || !checkInvariant(left))) return false
    val right = node.right
    return right == null || right.value > node.value && checkInvariant(right)
}

override fun remove(element: T): Boolean {
    var currentNode = root ?: return false
    var parentNode = root ?: return false
    var onRight = true
    while (currentNode.value != element) {
        parentNode = currentNode
        if (element > currentNode.value) {
            currentNode = currentNode.right ?: return false
            onRight = true
        } else if (element < currentNode.value) {
            currentNode = currentNode.left ?: return false
            onRight = false
        }
    }
    if (currentNode.left == null && currentNode.right == null) {
        //if removal point is leaf
        when {
            currentNode == root -> root = null
            onRight -> parentNode.right = null
            else -> parentNode.left = null
        }
    } else if (currentNode.left == null) {
        //if removal point have only right child
        if (currentNode == root) root = currentNode.right
        else {
            val right = currentNode.right ?: return false
            setNode(onRight, parentNode, right)
        }
    } else if (currentNode.right == null) {
        //if removal point have only left child
        if (currentNode == root) root = currentNode.left
        else {
            val left = currentNode.left ?: return false
            setNode(onRight, parentNode, left)
        }
    } else {
        //worst case - if removal point have both children
        var minNode = currentNode.right ?: return false
        var parentMinNode = currentNode.right ?: return false
        while (minNode.left != null) {
            parentMinNode = minNode
            val left = minNode.left ?: return false
            minNode = left
        }
        when {
            currentNode == root && parentMinNode == minNode -> {
                val rootLeft = root!!.left
                root = minNode
                minNode.left = rootLeft
            }
            currentNode == root && parentMinNode != minNode -> {
                parentMinNode.left = minNode.right
                root = minNode
                minNode.left = currentNode.left
                minNode.right = currentNode.right
            }
            parentMinNode == minNode -> setNode(onRight, parentNode, minNode)
            else -> {
                parentMinNode.left = minNode.right
                minNode.right = currentNode.right
                minNode.left = currentNode.left
                setNode(onRight, parentNode, minNode)
            }
        }
        minNode.left = currentNode.left
    }
    size--
    return true
}

private fun setNode(onRight: Boolean, parentNode: Node<T>, currentNode: Node<T>) {
    if (onRight)
        parentNode.right = currentNode
    else parentNode.left = currentNode
}

override operator fun contains(element: T): Boolean {
    val closest = find(element)
    return closest != null && element.compareTo(closest.value) == 0
}

private fun find(value: T): Node<T>? =
        root?.let { find(it, value) }

private fun find(start: Node<T>, value: T): Node<T> {
    val comparison = value.compareTo(start.value)
    return when {
        comparison == 0 -> start
        comparison < 0 -> start.left?.let { find(it, value) } ?: start
        else -> start.right?.let { find(it, value) } ?: start
    }
}

inner class BinaryTreeIterator : MutableIterator<T> {

    private var current: Node<T>? = null

    private fun findNext(): Node<T>? {
        val currentNode = current ?: return find(first())
        if (currentNode.value == last()) return null
        if (currentNode.right != null) {
            var successor = currentNode.right ?: throw IllegalArgumentException()
            while (successor.left != null) {
                successor = successor.left ?: return successor
            }
            return successor
        } else {
            var successor = root ?: throw IllegalArgumentException()
            var ancestor = root ?: throw IllegalArgumentException()
            while (ancestor != currentNode) {
                if (currentNode.value < ancestor.value) {
                    successor = ancestor
                    ancestor = ancestor.left ?: return null
                } else ancestor = ancestor.right ?: return null
            }
            return successor
        }
    }

    override fun hasNext(): Boolean = findNext() != null

    override fun next(): T {
        current = findNext()
        return (current ?: throw NoSuchElementException()).value
    }


override fun subSet(fromElement: T, toElement: T): SortedSet<T> =
        tailSet(fromElement).intersect(headSet(toElement)).toSortedSet()

override fun headSet(toElement: T): SortedSet<T> {
    val flag = this.contains(toElement)
    if (!flag) this.add(toElement)
    val setOfMax = mutableSetOf<T>()
    val iter = iterator()
    var element: T = iter.next()
    while (element != toElement) {
        if (!iter.hasNext()) throw IllegalArgumentException()
        setOfMax.add(element)
        element = iter.next()
    }
    if (!flag) this.remove(toElement)
    return setOfMax.toSortedSet()
}


override fun tailSet(fromElement: T): SortedSet<T> {
    val flag = !this.contains(fromElement)
    if (flag) this.add(fromElement)
    val setOfMax = mutableSetOf<T>()
    val iter = this.iterator()
    var element: T = iter.next()
    while (element != fromElement) {
        element = iter.next()
    }
    while (element != last()) {
        setOfMax.add(element)
        element = iter.next()
    }
    if (flag) this.remove(fromElement)
    setOfMax.add(element)
    return setOfMax.toSortedSet()
}

override fun first(): T {
    var current: Node<T> = root ?: throw NoSuchElementException()
    while (current.left != null) {
        current = current.left!!
    }
    return current.value
}

override fun last(): T {
    var current: Node<T> = root ?: throw NoSuchElementException()
    while (current.right != null) {
        current = current.right!!
    }
    return current.value
}

}

Answer 1

Я нашел, как я могу это сделать, я создал класс, которому будут предоставлены те же узлы. И измените итератор этого дополнительного дерева, которое я назвал SubSet. это изменения в дереве KtBinary:

override fun subSet(fromElement: T, toElement: T): SortedSet<T> =
            SubSet(this, fromElement, toElement)

override fun headSet(toElement: T): SortedSet<T> =
            SubSet(this, null, toElement)

override fun tailSet(fromElement: T): SortedSet<T> =
            SubSet(this, fromElement, null)

и это SubSet (дополнительное дерево)

import java.util.*

class SubSet<T : Comparable<T>>(private val delegate: SortedSet<T>,
                                private val fromElement: T?,
                                private val toElement: T?) : AbstractMutableSet<T>(), SortedSet<T> {
    override fun comparator(): Comparator<in T>? = delegate.comparator()

    override fun subSet(fromElement: T, toElement: T): SortedSet<T> {
        return SubSet(this, fromElement, toElement)
    }

    override fun headSet(toElement: T): SortedSet<T> {
        return SubSet(this, null, toElement)
    }

    override fun tailSet(fromElement: T): SortedSet<T> {
        return SubSet(this, fromElement, null)
    }

    override fun last(): T {
        val iter = iterator()
        var element = iter.next()
        while (iter.hasNext()) {
            element = iter.next()
        }
        return element
    }

    override fun first(): T {
        return iterator().next()
    }

    override fun add(element: T): Boolean {
        return when {
            fromElement == null && toElement == null -> false
            fromElement == null && element < toElement!! -> delegate.add(element)
            toElement == null && element >= fromElement!! -> delegate.add(element)
            element >= fromElement!! && element < toElement!! -> delegate.add(element)
            else -> false
        }
    }

    override fun remove(element: T): Boolean {
        return when {
            fromElement == null && toElement == null -> false
            fromElement == null && element < toElement!! -> delegate.remove(element)
            toElement == null && element >= fromElement!! -> delegate.remove(element)
            element >= fromElement!! && element < toElement!! -> delegate.remove(element)
            else -> false
        }
    }

    override fun iterator(): MutableIterator<T> = object : MutableIterator<T> {
        private val delegate = this@SubSet.delegate.iterator()

        private var next: T? = null

        init {
            while (delegate.hasNext()) {
                if (fromElement == null) {
                    this.next = delegate.next()
                    break
                }
                val next = delegate.next()
                if (next >= fromElement) {
                    this.next = next
                    break
                }
            }
        }

        override fun hasNext(): Boolean {
            val n = next ?: return false
            return n < toElement ?: return true
        }

        override fun next(): T {
            val result = next ?: throw NoSuchElementException()
            next = if (delegate.hasNext()) delegate.next() else null
            return result
        }

        override fun remove() {
            delegate.remove()
        }

    }

    override val size: Int
        get() = when {
            fromElement == null && toElement == null -> 0
            fromElement == null -> delegate.count { it < toElement!! }
            toElement == null -> delegate.count { it >= fromElement }
            else -> delegate.count { it >= fromElement && it < toElement }
        }
}