스칼라에서 사용할 표준 이진 검색 트리 구조는 무엇입니까?

Question

스칼라 2.10.x에서 사용해야하는 표준 밸런스 이진 검색 트리 구현은 무엇입니까? 나는 주위를 둘러 보는데 AVLTree이 제거되었고 RedBlack은 (는) 메시지로 대체됩니다 ((Since version 2.10.0) use TreeMap or TreeSet instead). 그러나 TreeMap 및 TreeSet은 필요한 기능을 제공하지 않으므로 트리를 탐색하여이를 기반으로보다 복잡한 데이터 구조를 구축 할 수 있어야합니다.

더 이상 사용되지 않는 일반 균형 조정 된 이진 트리 기능을 제공하는 새로운 클래스가 있습니까?

당신은 이진 검색 나무의 집에서 만든 버전을 시도 할 수 있습니다

Answer 1

:

https://github.com/melvic-ybanez/scala-bst

내가 걱정으로 지금까지, 내가 사용하고있는 매우 효율적으로 그들이 불변 때 종류의 키를 기준으로 데이터를 HashSet의 .

Answer 2

나무는 함수 프로그래밍과 스칼라의 기본이며, 요구 사항의 복잡성에 따라 어떤 연결 유형과 순회 방식이든 상관없이 자신의 BTree를 굴리는 것이 좋지 않습니다.

trait BSTree[+A] { 
    def value: Option[A] = this match { 
    case n: Node[A] => Some(n.v) 
    case l: Leaf[A] => Some(l.v) 
    case Empty  => None 
    } 

    def left: Option[BSTree[A]] = this match { 
    case n: Node[A] => Some(n.l) 
    case l: Leaf[A] => None 
    case Empty  => None 
    } 

    def right: Option[BSTree[A]] = this match { 
    case n: Node[A] => Some(n.r) 
    case l: Leaf[A] => None 
    case Empty  => None 
    } 
} 

case class Node[A](v: A, l: BSTree[A], r: BSTree[A]) extends BSTree[A] 
case class Leaf[A](v: A) extends BSTree[A] 
case object Empty extends BSTree[Nothing]