算法设计------Binary Search Tree

发表于 | 分类于 ，

二叉搜索树

定义：二叉搜索树为具有以下性质的二叉树：对于每个节点 v

  • v 的值 > v的左子树的每个节点的值
  • v 的值 < v的右子树的每个节点的值
  • 没有重复的节点

性质

基于二叉搜索树的上述性质，相比于其他数据结构的优势在于：

  • 查找、插入、删除的时间复杂度较低，为O(log n)，最坏为O( n )（数列有序，树退化为线性表）。
  • 很容易获取最大值（树的最右结点）、最小值（树的最左节点）、某元素的前驱（左子树的最右）、某元素的后继（右子树的最左）
  • 每次插入新的节点都是二叉树线上新的叶子节点，在进行插入操作时，不必移动其他节点，只需改动某节点指针，由空变为非空即可。
  • 对二叉搜索树进行中序遍历可得到有序数列。

基本操作

查找算法

  1. 给定值等于根，返回根。
  2. 给定值小于根，在根的左子树查找。
  3. 给定值大于根，在根的右子树查找。

插入算法

从根开始搜索，直到找到一个叶子节点，新的节点作为该叶子的子节点插入。

1
2
3
4
5
6
7
    100                               100
    /   \        Insert 40            /    \
  20     500    --------->          20     500 
 /  \                              /  \  
10   30                           10   30
                                          \   
                                          40

删除算法

删除的节点为叶子节点，直接删除即可。

1
2
3
4
5
       50                            50
    /     \         delete(20)      /   \
   30      70       --------->    30     70 
  /  \    /  \                     \    /  \ 
20   40  60   80                   40  60   80

删除的节点有一个子节点，删除该子节点，并用其唯一子节点代替其位置。

1
2
3
4
5
    50                            50
 /     \         delete(30)      /   \
30      70       --------->    40     70 
  \    /  \                          /  \ 
  40  60   80                       60   80

删除的节点有两个子节点，找到该节点的右子树的最小节点k，以k替换掉待删除节点。

1
2
3
4
5
50                            60
 /     \         delete(50)      /   \
40      70       --------->    40    70 
       /  \                            \ 
      60   80                           80

代码实现

.h文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct tree_Node{
    int memeber;//数据域
    struct tree_Node * left_Child;//左孩子
    struct tree_Node * right_Child;//右孩子
}Tree_Node, * p_Tree_Node;

p_Tree_Node newNode(int member);
p_Tree_Node insert(p_Tree_Node node, int member);//插入
p_Tree_Node searchNode(p_Tree_Node root, int key);//搜索
p_Tree_Node maxValue(p_Tree_Node root);//最大值
p_Tree_Node minValue(p_Tree_Node root);//最小值
p_Tree_Node deleteNode(p_Tree_Node root, int member);//删除
//中序遍历
void inorderTree(p_Tree_Node root);

.c文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
p_Tree_Node newNode(int member){
    p_Tree_Node node = (p_Tree_Node) malloc(sizeof(Tree_Node));
    if (node == NULL) {
        printf("分配内存失败！");
        exit(-1);
    }
    node -> memeber = member;
    node -> left_Child = NULL;
    node -> right_Child = NULL;
    return node;
}

p_Tree_Node insert(p_Tree_Node node, int member){
    
    if (node == NULL) return newNode(member);
    
    if (member < node -> memeber) {
        node -> left_Child = insert(node -> left_Child, member);
    }else if (member > node -> memeber){
        node -> right_Child = insert(node -> right_Child, member);
    }
    return node;
}

p_Tree_Node minValue(p_Tree_Node root){
    p_Tree_Node minNode = root;
    while (minNode -> left_Child) {
        minNode = minNode -> left_Child;
    }
    return minNode;
}

p_Tree_Node maxValue(p_Tree_Node root){
    p_Tree_Node maxNode = root;
    while (maxNode -> right_Child) {
        maxNode = maxNode -> right_Child;
    }
    return maxNode;
}

p_Tree_Node deleteNode(p_Tree_Node root, int member){
    if (root == NULL) {
        return root;
    }
    if (member < root -> memeber) {
        root -> left_Child = deleteNode(root -> left_Child, member);
    }else if (member > root -> memeber){
        root -> right_Child = deleteNode(root -> right_Child, member);
    }else{
        if (root -> left_Child == NULL) {
            p_Tree_Node temp = root -> right_Child;
            free(root);
            return temp;
        }else if (root -> right_Child == NULL){
            p_Tree_Node temp = root -> left_Child;
            free(root);
            return temp;
        }
        p_Tree_Node temp = minValue(root -> right_Child);
        root -> memeber = temp -> memeber;
        root -> right_Child = deleteNode(root -> right_Child, temp -> memeber);
    }
    return root;
}

p_Tree_Node searchNode(p_Tree_Node root, int key){
    if (root == NULL) {
        return NULL;
    }
    if (root -> memeber == key) {
        return root;
    }else if (root -> memeber > key){
        return searchNode(root -> left_Child, key);
    }else{
        return searchNode(root -> right_Child, key);
    }
}

void inorderTree(p_Tree_Node root){
    if (root != NULL) {
        inorderTree(root -> left_Child);
        printf("%d \n", root -> memeber);
        inorderTree(root -> right_Child);
    }
}

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void testBinarySearchTree(){
    /* 创建一个如下 BST
     50
     /     \
     30      70
     /  \    /  \
     20   40  60   80 */
    p_Tree_Node root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);
    
    inorderTree(root);
    
    p_Tree_Node serNode = searchNode(root, 20);
    printf("\nserNode ----- %d\n",serNode -> memeber);
    deleteNode(root, 30);
    inorderTree(root);
    
}

进阶

二叉搜索树，在插入数列有序时会退化为链表，插入、删除、查找时间复杂度退化为O( n )，为降低二叉搜索树的高度可以通过构建平衡二叉树，它要求左右两个子树的高度差的绝对值不超过1，这样就可以将搜索树的高度尽可能减小。常用的算法有红黑树、AVL Tree、SBT等。

如果对你有帮助的话，Star✨下一吧！