Implementations of AVL, Red-Black, and Huffman Trees

🌲 1. AVL Tree (Self-Balancing Binary Search Tree)

The core idea of an AVL tree:

Each node maintains a height. After insertion, rotations (left/right) are performed to maintain balance.

typescriptpythonkotlin

typescript

// AVL Tree in TypeScript

class AVLNode<T> {
  key: T;
  height: number;
  left: AVLNode<T> | null = null;
  right: AVLNode<T> | null = null;

  constructor(key: T) {
    this.key = key;
    this.height = 1;
  }
}

class AVLTree<T> {
  root: AVLNode<T> | null = null;

  private height(node: AVLNode<T> | null): number {
    return node ? node.height : 0;
  }

  private getBalance(node: AVLNode<T> | null): number {
    return node ? this.height(node.left) - this.height(node.right) : 0;
  }

  private rotateRight(y: AVLNode<T>): AVLNode<T> {
    const x = y.left!;
    const T2 = x.right;

    x.right = y;
    y.left = T2;

    y.height = Math.max(this.height(y.left), this.height(y.right)) + 1;
    x.height = Math.max(this.height(x.left), this.height(x.right)) + 1;

    return x;
  }

  private rotateLeft(x: AVLNode<T>): AVLNode<T> {
    const y = x.right!;
    const T2 = y.left;

    y.left = x;
    x.right = T2;

    x.height = Math.max(this.height(x.left), this.height(x.right)) + 1;
    y.height = Math.max(this.height(y.left), this.height(y.right)) + 1;

    return y;
  }

  insert(key: T): void {
    this.root = this._insert(this.root, key);
  }

  private _insert(node: AVLNode<T> | null, key: T): AVLNode<T> {
    if (!node) return new AVLNode(key);

    if (key < node.key) node.left = this._insert(node.left, key);
    else if (key > node.key) node.right = this._insert(node.right, key);
    else return node;

    node.height = 1 + Math.max(this.height(node.left), this.height(node.right));
    const balance = this.getBalance(node);

    if (balance > 1 && key < (node.left?.key ?? key)) return this.rotateRight(node); // LL
    if (balance < -1 && key > (node.right?.key ?? key)) return this.rotateLeft(node); // RR
    if (balance > 1 && key > (node.left?.key ?? key)) { // LR
      node.left = this.rotateLeft(node.left!);
      return this.rotateRight(node);
    }
    if (balance < -1 && key < (node.right?.key ?? key)) { // RL
      node.right = this.rotateRight(node.right!);
      return this.rotateLeft(node);
    }

    return node;
  }

  inorder(node = this.root): void {
    if (!node) return;
    this.inorder(node.left);
    console.log(node.key);
    this.inorder(node.right);
  }
}

// ✅ Example
const avl = new AVLTree<number>();
[10, 20, 30, 25, 28, 27].forEach(n => avl.insert(n));
avl.inorder(); // Outputs a sorted sequence

python

# AVL Tree in Python

class AVLNode:
    def __init__(self, key):
        self.key = key
        self.height = 1
        self.left = None
        self.right = None

class AVLTree:
    def __init__(self):
        self.root = None

    # 获取节点高度
    def _height(self, node):
        return node.height if node else 0

    # 获取平衡因子
    def _get_balance(self, node):
        return self._height(node.left) - self._height(node.right) if node else 0

    # 右旋
    def _rotate_right(self, y):
        x = y.left
        T2 = x.right

        x.right = y
        y.left = T2

        # 更新高度
        y.height = 1 + max(self._height(y.left), self._height(y.right))
        x.height = 1 + max(self._height(x.left), self._height(x.right))

        return x

    # 左旋
    def _rotate_left(self, x):
        y = x.right
        T2 = y.left

        y.left = x
        x.right = T2

        # 更新高度
        x.height = 1 + max(self._height(x.left), self._height(x.right))
        y.height = 1 + max(self._height(y.left), self._height(y.right))

        return y

    # 插入节点
    def insert(self, key):
        self.root = self._insert(self.root, key)

    def _insert(self, node, key):
        # 1. 执行标准BST插入
        if not node:
            return AVLNode(key)
        elif key < node.key:
            node.left = self._insert(node.left, key)
        elif key > node.key:
            node.right = self._insert(node.right, key)
        else:  # 不允许重复值
            return node

        # 2. 更新当前节点高度
        node.height = 1 + max(self._height(node.left), self._height(node.right))

        # 3. 获取平衡因子判断是否失衡
        balance = self._get_balance(node)

        # 4. 处理四种失衡情况
        # LL情况：左左失衡，右旋
        if balance > 1 and key < node.left.key:
            return self._rotate_right(node)
        # RR情况：右右失衡，左旋
        if balance < -1 and key > node.right.key:
            return self._rotate_left(node)
        # LR情况：左右失衡，先左旋后右旋
        if balance > 1 and key > node.left.key:
            node.left = self._rotate_left(node.left)
            return self._rotate_right(node)
        # RL情况：右左失衡，先右旋后左旋
        if balance < -1 and key < node.right.key:
            node.right = self._rotate_right(node.right)
            return self._rotate_left(node)

        return node

    # 中序遍历
    def inorder(self, node=None):
        if node is None:
            node = self.root
        return self._inorder(node)

    def _inorder(self, node):
        if not node:
            return
        self._inorder(node.left)
        print(node.key, end=' ')
        self._inorder(node.right)

if __name__ == "__main__":
    avl = AVLTree()
    for num in [10, 20, 30, 25, 28, 27]:
        avl.insert(num)
    avl.inorder()  # 输出有序序列：10 20 25 27 28 30

kotlin

// AVL Tree in Kotlin
class AVLNode(val key: Int) {
    var height = 1
    var left: AVLNode? = null
    var right: AVLNode? = null
}

class AVLTree {
    private var root: AVLNode? = null

    // 获取节点高度
    private fun height(node: AVLNode?): Int {
        return node?.height ?: 0
    }

    // 获取平衡因子
    private fun getBalance(node: AVLNode?): Int {
        return if (node == null) 0 else height(node.left) - height(node.right)
    }

    // 右旋
    private fun rotateRight(y: AVLNode): AVLNode {
        val x = y.left!!
        val t2 = x.right

        x.right = y
        y.left = t2

        // 更新高度
        y.height = 1 + maxOf(height(y.left), height(y.right))
        x.height = 1 + maxOf(height(x.left), height(x.right))

        return x
    }

    // 左旋
    private fun rotateLeft(x: AVLNode): AVLNode {
        val y = x.right!!
        val t2 = y.left

        y.left = x
        x.right = t2

        // 更新高度
        x.height = 1 + maxOf(height(x.left), height(x.right))
        y.height = 1 + maxOf(height(y.left), height(y.right))

        return y
    }

    // 插入节点
    fun insert(key: Int) {
        root = insert(root, key)
    }

    private fun insert(node: AVLNode?, key: Int): AVLNode {
        // 1. 执行标准BST插入
        if (node == null) {
            return AVLNode(key)
        } else if (key < node.key) {
            node.left = insert(node.left, key)
        } else if (key > node.key) {
            node.right = insert(node.right, key)
        } else { // 不允许重复值
            return node
        }

        // 2. 更新当前节点高度
        node.height = 1 + maxOf(height(node.left), height(node.right))

        // 3. 获取平衡因子判断是否失衡
        val balance = getBalance(node)

        // 4. 处理四种失衡情况
        // LL情况：左左失衡，右旋
        if (balance > 1 && key < node.left!!.key) {
            return rotateRight(node)
        }
        // RR情况：右右失衡，左旋
        if (balance < -1 && key > node.right!!.key) {
            return rotateLeft(node)
        }
        // LR情况：左右失衡，先左旋后右旋
        if (balance > 1 && key > node.left!!.key) {
            node.left = rotateLeft(node.left!!)
            return rotateRight(node)
        }
        // RL情况：右左失衡，先右旋后左旋
        if (balance < -1 && key < node.right!!.key) {
            node.right = rotateRight(node.right!!)
            return rotateLeft(node)
        }

        return node
    }

    // 中序遍历
    fun inorder() {
        inorder(root)
    }

    private fun inorder(node: AVLNode?) {
        if (node != null) {
            inorder(node.left)
            print("${node.key} ")
            inorder(node.right)
        }
    }
}

// 示例
fun main() {
    val avl = AVLTree()
    val numbers = listOf(10, 20, 30, 25, 28, 27)
    numbers.forEach { avl.insert(it) }
    avl.inorder()  // 输出有序序列：10 20 25 27 28 30
}

🔴 2. Red-Black Tree

Key points:

Nodes have a color (red/black)
Balance is maintained via rotations + recoloring
Satisfies the five properties of a red-black tree (root black, no consecutive red nodes, etc.)

typescriptpythonkotlin

typescript

// Red-Black Tree in TypeScript

enum Color { RED, BLACK }

class RBNode<T> {
  key: T;
  color: Color = Color.RED;
  left: RBNode<T> | null = null;
  right: RBNode<T> | null = null;
  parent: RBNode<T> | null = null;

  constructor(key: T) {
    this.key = key;
  }
}

class RedBlackTree<T> {
  root: RBNode<T> | null = null;

  private rotateLeft(x: RBNode<T>) { /* ... rotation logic ... */ }
  private rotateRight(y: RBNode<T>) { /* ... rotation logic ... */ }
  private fixInsert(z: RBNode<T>) { /* ... fix violations ... */ }

  insert(key: T) {
    const node = new RBNode(key);
    let y: RBNode<T> | null = null;
    let x = this.root;

    while (x) {
      y = x;
      if (node.key < x.key) x = x.left;
      else x = x.right;
    }

    node.parent = y;
    if (!y) this.root = node;
    else if (node.key < y.key) y.left = node;
    else y.right = node;

    this.fixInsert(node);
  }

  inorder(node = this.root): void {
    if (!node) return;
    this.inorder(node.left);
    console.log(`${node.key} (${node.color === Color.RED ? "R" : "B"})`);
    this.inorder(node.right);
  }
}

// ✅ Example
const rbt = new RedBlackTree<number>();
[10, 20, 30, 15, 25, 5].forEach(n => rbt.insert(n));
rbt.inorder();

python

# Red-Black Tree in Python
from enum import Enum

class Color(Enum):
    RED = 0
    BLACK = 1

class RBNode:
    def __init__(self, key):
        self.key = key
        self.color = Color.RED
        self.left = None
        self.right = None
        self.parent = None

class RedBlackTree:
    def __init__(self):
        self.root = None

    def rotate_left(self, x):
        y = x.right
        x.right = y.left
        if y.left:
            y.left.parent = x
        y.parent = x.parent

        if not x.parent:
            self.root = y
        elif x == x.parent.left:
            x.parent.left = y
        else:
            x.parent.right = y

        y.left = x
        x.parent = y

    def rotate_right(self, y):
        x = y.left
        y.left = x.right
        if x.right:
            x.right.parent = y
        x.parent = y.parent

        if not y.parent:
            self.root = x
        elif y == y.parent.left:
            y.parent.left = x
        else:
            y.parent.right = x

        x.right = y
        y.parent = x

    def fix_insert(self, z):
        while z.parent and z.parent.color == Color.RED:
            gp = z.parent.parent
            if not gp:
                break
            if z.parent == gp.left:
                uncle = gp.right
                if uncle and uncle.color == Color.RED:
                    z.parent.color = Color.BLACK
                    uncle.color = Color.BLACK
                    gp.color = Color.RED
                    z = gp
                else:
                    if z == z.parent.right:
                        z = z.parent
                        self.rotate_left(z)
                    z.parent.color = Color.BLACK
                    gp.color = Color.RED
                    self.rotate_right(gp)
            else:
                uncle = gp.left
                if uncle and uncle.color == Color.RED:
                    z.parent.color = Color.BLACK
                    uncle.color = Color.BLACK
                    gp.color = Color.RED
                    z = gp
                else:
                    if z == z.parent.left:
                        z = z.parent
                        self.rotate_right(z)
                    z.parent.color = Color.BLACK
                    gp.color = Color.RED
                    self.rotate_left(gp)
        self.root.color = Color.BLACK

    def insert(self, key):
        node = RBNode(key)
        y = None
        x = self.root

        while x:
            y = x
            if node.key < x.key:
                x = x.left
            else:
                x = x.right

        node.parent = y
        if not y:
            self.root = node
        elif node.key < y.key:
            y.left = node
        else:
            y.right = node

        self.fix_insert(node)

    def inorder(self, node=None):
        if node is None:
            node = self.root
        self._inorder(node)

    def _inorder(self, node):
        if not node:
            return
        self._inorder(node.left)
        color = "R" if node.color == Color.RED else "B"
        print(f"{node.key} ({color})", end=" ")
        self._inorder(node.right)

# 示例
if __name__ == "__main__":
    rbt = RedBlackTree()
    for n in [10, 20, 30, 15, 25, 5]:
        rbt.insert(n)
    rbt.inorder()

kotlin

// Red-Black Tree in Kotlin
enum class Color { RED, BLACK }

class RBNode<T : Comparable<T>>(val key: T) {
    var color: Color = Color.RED
    var left: RBNode<T>? = null
    var right: RBNode<T>? = null
    var parent: RBNode<T>? = null
}

class RedBlackTree<T : Comparable<T>> {
    private var root: RBNode<T>? = null

    private fun rotateLeft(x: RBNode<T>) {
        val y = x.right!!
        x.right = y.left
        y.left?.parent = x
        y.parent = x.parent

        if (x.parent == null) {
            root = y
        } else if (x == x.parent?.left) {
            x.parent?.left = y
        } else {
            x.parent?.right = y
        }

        y.left = x
        x.parent = y
    }

    private fun rotateRight(y: RBNode<T>) {
        val x = y.left!!
        y.left = x.right
        x.right?.parent = y
        x.parent = y.parent

        if (y.parent == null) {
            root = x
        } else if (y == y.parent?.left) {
            y.parent?.left = x
        } else {
            y.parent?.right = x
        }

        x.right = y
        y.parent = x
    }

    private fun fixInsert(z: RBNode<T>) {
        var current = z
        while (current.parent != null && current.parent?.color == Color.RED) {
            val gp = current.parent?.parent
            if (gp == null) break

            if (current.parent == gp.left) {
                val uncle = gp.right
                if (uncle != null && uncle.color == Color.RED) {
                    current.parent?.color = Color.BLACK
                    uncle.color = Color.BLACK
                    gp.color = Color.RED
                    current = gp
                } else {
                    if (current == current.parent?.right) {
                        current = current.parent!!
                        rotateLeft(current)
                    }
                    current.parent?.color = Color.BLACK
                    gp.color = Color.RED
                    rotateRight(gp)
                }
            } else {
                val uncle = gp.left
                if (uncle != null && uncle.color == Color.RED) {
                    current.parent?.color = Color.BLACK
                    uncle.color = Color.BLACK
                    gp.color = Color.RED
                    current = gp
                } else {
                    if (current == current.parent?.left) {
                        current = current.parent!!
                        rotateRight(current)
                    }
                    current.parent?.color = Color.BLACK
                    gp.color = Color.RED
                    rotateLeft(gp)
                }
            }
        }
        root?.color = Color.BLACK
    }

    fun insert(key: T) {
        val node = RBNode(key)
        var y: RBNode<T>? = null
        var x = root

        while (x != null) {
            y = x
            x = if (node.key < x.key) x.left else x.right
        }

        node.parent = y
        when {
            y == null -> root = node
            node.key < y.key -> y.left = node
            else -> y.right = node
        }

        fixInsert(node)
    }

    fun inorder() {
        inorder(root)
    }

    private fun inorder(node: RBNode<T>?) {
        if (node != null) {
            inorder(node.left)
            val color = if (node.color == Color.RED) "R" else "B"
            print("${node.key} ($color) ")
            inorder(node.right)
        }
    }
}

// 示例
fun main() {
    val rbt = RedBlackTree<Int>()
    listOf(10, 20, 30, 15, 25, 5).forEach { rbt.insert(it) }
    rbt.inorder()
}

🟡 3. Huffman Tree

Huffman trees are used to generate optimal codes for compression:

Repeatedly merge the two nodes with the smallest frequencies until only one node remains.

typescriptpythonkotlin

typescript

// Huffman Tree in TypeScript

class HuffmanNode {
  char?: string;
  freq: number;
  left: HuffmanNode | null = null;
  right: HuffmanNode | null = null;

  constructor(freq: number, char?: string) {
    this.freq = freq;
    this.char = char;
  }
}

class HuffmanTree {
  root: HuffmanNode | null = null;

  constructor(frequencies: Record<string, number>) {
    const nodes: HuffmanNode[] = Object.entries(frequencies)
      .map(([char, freq]) => new HuffmanNode(freq, char));

    while (nodes.length > 1) {
      nodes.sort((a, b) => a.freq - b.freq);
      const left = nodes.shift()!;
      const right = nodes.shift()!;
      const merged = new HuffmanNode(left.freq + right.freq);
      merged.left = left;
      merged.right = right;
      nodes.push(merged);
    }

    this.root = nodes[0];
  }

  generateCodes(node = this.root, code = "", result: Record<string, string> = {}): Record<string, string> {
    if (!node) return result;
    if (node.char) result[node.char] = code;
    this.generateCodes(node.left, code + "0", result);
    this.generateCodes(node.right, code + "1", result);
    return result;
  }
}

// ✅ Example
const freqs = { A: 5, B: 9, C: 12, D: 13, E: 16, F: 45 };
const huffman = new HuffmanTree(freqs);
const codes = huffman.generateCodes();
console.log("Huffman Codes:", codes);

python

# Huffman Tree in Python
class HuffmanNode:
    def __init__(self, freq: int, char: str = None):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None

class HuffmanTree:
    def __init__(self, frequencies: dict[str, int]):
        # 创建初始节点列表
        nodes = [HuffmanNode(freq, char) for char, freq in frequencies.items()]
        
        # 构建哈夫曼树
        while len(nodes) > 1:
            # 按频率排序
            nodes.sort(key=lambda x: x.freq)
            # 取出频率最小的两个节点
            left = nodes.pop(0)
            right = nodes.pop(0)
            # 合并为新节点
            merged = HuffmanNode(left.freq + right.freq)
            merged.left = left
            merged.right = right
            nodes.append(merged)
        
        self.root = nodes[0] if nodes else None
    
    # 生成哈夫曼编码
    def generate_codes(self) -> dict[str, str]:
        codes = {}
        self._generate_codes_recursive(self.root, "", codes)
        return codes
    
    def _generate_codes_recursive(self, node: HuffmanNode, current_code: str, codes: dict[str, str]) -> None:
        if not node:
            return
        # 如果是叶子节点，记录编码
        if node.char:
            codes[node.char] = current_code
        # 递归处理左右子树
        self._generate_codes_recursive(node.left, current_code + "0", codes)
        self._generate_codes_recursive(node.right, current_code + "1", codes)

# 示例
if __name__ == "__main__":
    freqs = {"A": 5, "B": 9, "C": 12, "D": 13, "E": 16, "F": 45}
    huffman = HuffmanTree(freqs)
    codes = huffman.generate_codes()
    print("Huffman Codes:", codes)

kotlin

// Huffman Tree in Kotlin
class HuffmanNode(
    val freq: Int,
    val char: Char? = null
) {
    var left: HuffmanNode? = null
    var right: HuffmanNode? = null
}

class HuffmanTree(frequencies: Map<Char, Int>) {
    private val root: HuffmanNode?

    init {
        // 创建初始节点列表
        val nodes = frequencies.map { (char, freq) -> HuffmanNode(freq, char) }.toMutableList()
        
        // 构建哈夫曼树
        while (nodes.size > 1) {
            // 按频率排序
            nodes.sortBy { it.freq }
            // 取出频率最小的两个节点
            val left = nodes.removeFirst()
            val right = nodes.removeFirst()
            // 合并为新节点
            val merged = HuffmanNode(left.freq + right.freq)
            merged.left = left
            merged.right = right
            nodes.add(merged)
        }
        
        root = if (nodes.isNotEmpty()) nodes[0] else null
    }

    // 生成哈夫曼编码
    fun generateCodes(): Map<Char, String> {
        val codes = mutableMapOf<Char, String>()
        generateCodesRecursive(root, "", codes)
        return codes
    }

    private fun generateCodesRecursive(
        node: HuffmanNode?,
        currentCode: String,
        codes: MutableMap<Char, String>
    ) {
        if (node == null) return
        // 如果是叶子节点，记录编码
        if (node.char != null) {
            codes[node.char] = currentCode
        }
        // 递归处理左右子树
        generateCodesRecursive(node.left, currentCode + "0", codes)
        generateCodesRecursive(node.right, currentCode + "1", codes)
    }
}

// 示例
fun main() {
    val freqs = mapOf('A' to 5, 'B' to 9, 'C' to 12, 'D' to 13, 'E' to 16, 'F' to 45)
    val huffman = HuffmanTree(freqs)
    val codes = huffman.generateCodes()
    println("Huffman Codes: $codes")
}

Sample output:

Huffman Codes: {
  F: '0',
  C: '100',
  D: '101',
  A: '1100',
  B: '1101',
  E: '111'
}

🧩 Comparison

Tree Type	Use Case	Core Logic	Time Complexity	TypeScript File
AVL Tree	Fast lookup	Rotations to maintain strict balance	O(log n)	`avl-tree.ts`
Red-Black Tree	Fast insert/delete	Colors + rotations for approximate balance	O(log n)	`red-black-tree.ts`
Huffman Tree	Optimal coding	Merge nodes with smallest frequency	O(n log n)	`huffman-tree.ts`

Implementations of AVL, Red-Black, and Huffman Trees ​

🌲 1. AVL Tree (Self-Balancing Binary Search Tree) ​

🔴 2. Red-Black Tree ​

🟡 3. Huffman Tree ​

🧩 Comparison ​

Implementations of AVL, Red-Black, and Huffman Trees

🌲 1. AVL Tree (Self-Balancing Binary Search Tree)

🔴 2. Red-Black Tree

🟡 3. Huffman Tree

🧩 Comparison