AVL、BlackRed、Huffman的实现方式

🌲 一、AVL 树实现（自平衡二叉搜索树）

AVL 树核心思想：

每个节点维护一个“高度（height）”，插入后通过**旋转（左旋/右旋）**保持平衡。

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);

    // 4种旋转情况
    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);
  }
}

// ✅ 示例
const avl = new AVLTree<number>();
[10, 20, 30, 25, 28, 27].forEach(n => avl.insert(n));
avl.inorder(); // 输出有序序列

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
}

🔴 二、红黑树（Red-Black Tree）

红黑树关键点：

节点有颜色属性（red/black）
通过“旋转 + 变色”保持平衡
满足五大性质（根黑、红节点不能相连等）

下面是一个简化版的红黑树实现（只包含插入核心逻辑）：

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>) {
    const y = x.right!;
    x.right = y.left;
    if (y.left) y.left.parent = x;
    y.parent = x.parent;

    if (!x.parent) this.root = y;
    else if (x === x.parent.left) x.parent.left = y;
    else x.parent.right = y;

    y.left = x;
    x.parent = y;
  }

  private rotateRight(y: RBNode<T>) {
    const x = y.left!;
    y.left = x.right;
    if (x.right) x.right.parent = y;
    x.parent = y.parent;

    if (!y.parent) this.root = x;
    else if (y === y.parent.left) y.parent.left = x;
    else y.parent.right = x;

    x.right = y;
    y.parent = x;
  }

  // 修复红黑树性质
  private fixInsert(z: RBNode<T>) {
    while (z.parent && z.parent.color === Color.RED) {
      const gp = z.parent.parent;
      if (!gp) break;
      if (z.parent === gp.left) {
        const uncle = gp.right;
        if (uncle && 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;
            this.rotateLeft(z);
          }
          z.parent!.color = Color.BLACK;
          gp.color = Color.RED;
          this.rotateRight(gp);
        }
      } else {
        const uncle = gp.left;
        if (uncle && 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;
            this.rotateRight(z);
          }
          z.parent!.color = Color.BLACK;
          gp.color = Color.RED;
          this.rotateLeft(gp);
        }
      }
    }
    this.root!.color = Color.BLACK;
  }

  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);
  }
}

// ✅ 示例
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()
}

🟡 三、哈夫曼树（Huffman Tree）

哈夫曼树用于生成最优编码（常用于压缩）。构建逻辑：

每次取权值最小的两个节点合并为新节点，重复直到只剩一棵树。

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;
  }
}

// ✅ 示例
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")
}

输出示例：

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

🧩 总结对比

树类型	用途	关键逻辑	时间复杂度	TypeScript文件
AVL树	快速查找	旋转保持严格平衡	O(log n)	`avl-tree.ts`
红黑树	快速插入+删除	颜色+旋转保持近似平衡	O(log n)	`red-black-tree.ts`
哈夫曼树	最优编码	合并最小权值节点	O(n log n)	`huffman-tree.ts`

AVL、BlackRed、Huffman的实现方式 ​

🌲 一、AVL 树实现（自平衡二叉搜索树） ​

🔴 二、红黑树（Red-Black Tree） ​

🟡 三、哈夫曼树（Huffman Tree） ​

🧩 总结对比 ​

AVL、BlackRed、Huffman的实现方式

🌲 一、AVL 树实现（自平衡二叉搜索树）

🔴 二、红黑树（Red-Black Tree）

🟡 三、哈夫曼树（Huffman Tree）

🧩 总结对比