Table of Contents

Class ScapegoatTreeRecordStore

Namespace
BelNytheraSeiche.TrieDictionary
Assembly
BelNytheraSeiche.TrieDictionary.dll

A concrete implementation of BinaryTreeRecordStore that uses a self-balancing Scapegoat tree.

public sealed class ScapegoatTreeRecordStore : BinaryTreeRecordStore, ICloneable
Inheritance
ScapegoatTreeRecordStore
Implements
Inherited Members

Remarks

A Scapegoat tree is a self-balancing binary search tree that provides amortized time efficiency. Instead of rebalancing on every operation, it rebuilds subtrees only when an insertion or deletion causes a node (the "scapegoat") to become too unbalanced. Note: This implementation can be slow on certain operations that trigger a full subtree rebuild and is generally not recommended for performance-critical applications.

Serialization Limits: The binary serialization format for this class imposes certain constraints on the data. Exceeding these limits will result in an InvalidDataException during serialization.

  • Max Records per List: A single identifier can have a maximum of 16,777,215 records in its linked list.
  • Max Record Content Size: The Content byte array of any single record cannot exceed 65,535 bytes.

Methods

Clone()

Creates a deep copy of the ScapegoatTreeRecordStore.

public object Clone()

Returns

object

A new ScapegoatTreeRecordStore instance with the same structure and record data as the original.

Remarks

The method creates a new tree and copies all records, ensuring that the new store is independent of the original.

Deserialize(Stream)

Deserializes a ScapegoatTreeRecordStore from a stream.

public static ScapegoatTreeRecordStore Deserialize(Stream stream)

Parameters

stream Stream

The stream to read the serialized data from.

Returns

ScapegoatTreeRecordStore

A new instance of ScapegoatTreeRecordStore reconstructed from the stream.

Exceptions

ArgumentNullException

stream is null.

InvalidDataException

The stream data is corrupted, in an unsupported format, or contains invalid values.

IsBalanced()

Overrides the base method to check if the tree conforms to the alpha-weight-balanced property of a tree.

public override bool IsBalanced()

Returns

bool

true if no subtree violates the alpha-weight balance condition; otherwise, false.

Remove(int)

Removes the node with the specified identifier from the tree. May trigger a rebuild of the entire tree if the number of nodes drops significantly.

public override void Remove(int identifier)

Parameters

identifier int

The identifier of the node to remove.

Exceptions

ArgumentOutOfRangeException

identifier is MinValue.

Serialize(ScapegoatTreeRecordStore, Stream, SerializationOptions?)

Serializes the entire state of the tree store into a stream.

public static void Serialize(ScapegoatTreeRecordStore store, Stream stream, BasicRecordStore.SerializationOptions? options = null)

Parameters

store ScapegoatTreeRecordStore

The ScapegoatTreeRecordStore instance to serialize.

stream Stream

The stream to write the serialized data to.

options BasicRecordStore.SerializationOptions

Options to control the serialization process. If null, the settings from Default will be used.

Remarks

The serialization format is specific to this tree implementation, using Brotli compression and an XxHash32 checksum for data integrity.

Exceptions

ArgumentNullException

store or stream is null.