Tree Data Structure - tenji/ks GitHub Wiki

树

一、分类

二叉树
- 二叉查找树（二分查找树，二叉搜索树，Binary Search Tree）
- 平衡二叉树（Balanced Binary Tree）
- 平衡二叉查找树
  - AVL 树
  - 红黑树
- 完全二叉树（Complete Binary Tree）
- 满二叉树（Full Binary Tree）
多路查找树
- B 树（B- 树、B_ 树）
- B+ 树
- 2-3 树
- 2-3-4 树
堆
- 二叉堆（Binary Heap）
  - 小顶堆
  - 大顶堆
- 二顶堆（Binomial Heap）
- 优先队列
- 斐波那契堆

二、二叉树

2.1 二叉查找树

二叉查找树也可叫做二分查找树。它不仅可以查找数据，还可以高效地插入、删除数据。每个节点的 key 值大于左子节点，小于右子节点。

2.1.1 属性

二叉查找树有两个属性：

所有节点都比左子树中的节点大
所有节点都小于右子树中的节点

通过这两个属性，可以推断出以下结论：

二叉查找树最小的节点位于最顶端节点的最左边子树行的末尾
二叉查找树的最大节点位于最顶端节点的最右边的子树行的末尾

2.1.2 添加元素

相对而言，二叉查找树添加元素比删除元素逻辑要简单很多：

待插入节点比根节点小，则插入左子树；
待插入节点比根节点大，则插入右子树；

public TreeNode insertIntoBST(TreeNode root, int val) {

    // 当前节点为空，直接插入当前节点
    if (root == null) {
        return new TreeNode(val);
    }

    // 值比根节点小，插入左子树
    if (val < root.val) {
        root.left = insertIntoBST(root.left, val);
    }

    // 值比根节点大，插入右子树
    if (val > root.val) {
        root.right = insertIntoBST(root.right, val);
    }

    return root;
}

2.1.3 删除元素

需要分以下几种情况处理：

无左子树，无右子树；
无左子树，有右子树；
有左子树，无右子树；
有左子树，有右子树；

public TreeNode deleteNode(TreeNode root, int key) {

    if (root == null) {
        return null;
    }

    if (root.val == key) {
        if (root.left == null && root.right == null) {
            // 情况一：无左子树，无右子树，直接删除节点即可
            return null;
        } else if (root.left == null) {
            // 情况二：无左子树，有右子树，则右子树上移
            return root.right;
        } else if (root.right == null) {
            // 情况三：有左子树，无右子树，则左子树上移
            return root.left;
        } else {
            // 情况四：有左子树，有右子树，则搜索右子树中最小的节点，并将待删除节点左子树下移
            TreeNode curNode = root.right;
            while (curNode.left != null) {
                curNode = curNode.left;
            }
            curNode.left = root.left;

            return root.right;
        }
    }

    if (root.val > key) {
        root.left = deleteNode(root.left, key);
    }

    if (root.val < key) {
        root.right = deleteNode(root.right, key);
    }

    return root;
}

2.1.4 遍历元素

2.2 平衡二叉树

2.3 平衡二叉查找树

2.3.1 属性

在二叉树的基础上，要求两个子树的高度差不能超过1；
每次增删都会通过一次或多次旋转来平衡二叉树；

调整平衡的基本思想：

当在二叉排序树中插入一个节点时，首先检查是否因插入而破坏了平衡，若破坏，则找出其中的最小不平衡二叉树，在保持二叉排序树特性的情况下，调整最小不平衡子树中节点之间的关系，以达到新的平衡。所谓最小不平衡子树，指离插入节点最近且以平衡因子的绝对值大于 1 的节点作为根的子树。

2.3.1 AVL 树

2.3.2 红黑树

2.4 完全二叉树

2.5 满二叉树

三、多路查找树

四、堆

堆是一种非线性结构，可以把堆看作一棵二叉树，也可以看作一个数组，即：堆就是利用完全二叉树的结构来维护的一维数组。