二叉树在高效排序中的魔法

创作时间:

2025-01-22 07:56:39

作者:

@小白创作中心

二叉树在高效排序中的魔法

二叉树作为一种重要的数据结构，在排序算法中展现出了神奇的力量。通过二叉树的巧妙运用，我们可以快速地对大量数据进行排序，从而提高程序运行效率。本文将带你探索二叉树在高效排序中的奥秘。

二叉查找树（BST）

二叉查找树（Binary Search Tree，简称 BST），又称为二叉搜索树、有序二叉树。它具有以下性质：

若其左子树非空，则左子树上所有节点的值都小于根节点的值
若其右子树非空，则右子树上所有节点的值都大于根节点的值
其左右子树也分别是一棵二叉查找树

二叉查找树的这些特性使得它在排序过程中具有独特的优势。通过中序遍历二叉查找树，得到的序列是有序的递增序列。这一特性为排序算法提供了便利。

插入操作

二叉查找树的插入操作遵循以下规则：

如果二叉查找树为空树，则插入的节点成为新的根节点
如果二叉查找树不为空：
- 如果新节点的值小于根节点的值，则递归插入左子树
- 如果新节点的值大于根节点的值，则递归插入右子树

function BinaryTree() {
    var Node = function(key) {
        this.key = key;
        this.left = null;
        this.right = null;
    };

    var root = null;

    var insertNode = function(node, newNode) {
        if (newNode.key < node.key) {
            if (node.left === null) {
                node.left = newNode;
            } else {
                insertNode(node.left, newNode);
            }
        } else {
            if (node.right === null) {
                node.right = newNode;
            } else {
                insertNode(node.right, newNode);
            }
        }
    };

    this.insert = function(key) {
        var newNode = new Node(key);
        if (root === null) {
            root = newNode;
        } else {
            insertNode(root, newNode);
        }
    };
}

查找操作

二叉查找树的查找操作类似于二分查找法：

如果二叉查找树为空树，则查找失败，返回 NULL
如果二叉查找树不为空：
- 如果 T->data == data，则返回该节点
- 如果 T->data > data，则递归查找左子树
- 如果 T->data < data，则递归查找右子树

时间复杂度分析：

最好情况：O(1)
最坏情况：O(n)
平均时间复杂度：O(log n)

删除操作

删除二叉查找树中的节点需要考虑三种情况：

节点为叶子节点，直接删除
节点只有一个子树，用子树替换
节点有两个子树，用左子树中最大的节点或右子树中最小的节点替换

中序遍历

中序遍历二叉查找树可以得到一个递增的有序序列。遍历规则是从根节点出发，先遍历左子树，然后访问根节点，最后遍历右子树。

var inOrderTraverseNode = function(node, callback) {
    if (node !== null) {
        inOrderTraverseNode(node.left, callback);
        callback(node.key);
        inOrderTraverseNode(node.right, callback);
    }
};

this.inOrderTraverse = function(callback) {
    inOrderTraverseNode(root, callback);
};

堆排序

堆排序是由罗伯特.弗洛伊德和威廉姆斯在1964年共同发明的一种排序算法。它利用堆积树（堆）这种数据结构进行排序，可以将元素按照大小在二叉树位置上排列。堆分为大根堆和小根堆，大根堆要求每个节点的值都不大于其父节点的值，小根堆则相反。

堆排序的基本思想是：

将待排序的序列构造成一个大根堆
将堆顶元素（最大值）与最后一个元素交换
调整剩余元素，重新构建大根堆
重复步骤2和3，直到堆中只剩下一个元素

堆排序的时间复杂度为 O(n log n)，空间复杂度为 O(1)。

#include <stdio.h>
#include <stdlib.h>

#define LEN 12

// 打印数组
void print_array(int *array, int length) {
    int index = 0;
    printf("array:\n");
    for (; index < length; index++) {
        printf(" %d,", *(array + index));
    }
    printf("\n\n");
}

// 堆化函数
void _heapSort(int *array, int i, int length) {
    int child, tmp;
    for (; 2 * i + 1 < length; i = child) {
        child = 2 * i + 1;
        if ((child + 1 < length) && (array[child + 1] > array[child])) child++;
        if (array[i] < array[child]) {
            tmp = array[i];
            array[i] = array[child];
            array[child] = tmp;
        } else break;
    }
}

void heapSort(int *array, int length) {
    int i, tmp;

    if (length <= 1) return;

    // 构建大根堆
    for (i = length / 2 - 1; i >= 0; i--) _heapSort(array, i, length);

    // 依次取出堆顶元素
    for (i = length - 1; i > 0; i--) {
        tmp = array[0];
        array[0] = array[i];
        array[i] = tmp;
        _heapSort(array, 0, i);
    }
}