数据结构与算法之二叉搜索树(八)

目录

• 二叉搜索树概念
• 二叉搜索树的接口设计，包括增，删，改，查
• 平衡二叉搜索树

一 二叉搜索树

二叉搜索树是二叉树的一种，是应用非常广泛的一种二叉树，英文简称为 BST

• 又被称为:二叉查找树、二叉排序树
• 任意一个节点的值都大于其左子树所有节点的值
• 任意一个节点的值都小于其右子树所有节点的值
• 它的左右子树也是一棵二叉搜索树

二叉搜索树可以大大提高搜索数据的效率

二叉搜索树存储的元素必须具备可比较性

• 比如 int、double 等
• 如果是自定义类型，需要指定比较方式
• 不允许为 null

二叉搜索树.png

二 二叉搜索树的接口设计

/**
 * 清除所有元素
 */
- (void)clear;

/**
 * 是否包含某个元素
 * @param element
 * @return bool
 */
- (bool)contains:(id)element;

/**
 * 添加元素到尾部
 * @param element
 */
- (void)add:(id)element;

/**
 * 删除元素
 * @param element
 */
- (void)remove:(id)element;

2.1 添加节点

添加步骤
1.找到父节点 parent
2.创建新节点 node
3.parent.left = node 或者 parent.right = node

遇到值相等的元素如何处理？ 覆盖旧的值

• 代码实现

- (void)add:(id)element {
    [self elementNotNullCheck:element];
    
    // 添加第一个节点
    if (_root == nil) {
        _root = [[TreeNode alloc] initWithElement:element parent:nil];
        _size++;
        return;
    }
    
    // 添加的不是第一个节点
    // 找到父节点
    TreeNode *parent = _root;
    TreeNode *node = _root;
    int cmp = 0;
    
    while (node != nil) {
        cmp = [self compare:element element2:node.element];
        parent = node;
        
        if (cmp > 0) {  // 右节点
            node = node.right;
        } else if (cmp < 0) {   // 左节点
            node = node.left;
        } else {    // 相对 - 覆盖
            node.element = element;
            return;
        }
    }
    
    // 查看插入到父节点的哪个位置
    TreeNode *newNode = [[TreeNode alloc] initWithElement:element parent:parent];
    if (cmp > 0) {
        parent.right = newNode;
    } else {
        parent.left = newNode;
    }
    _size++;
}

• 测试代码

// 打印一棵二叉树
- (void)test1 {
    NSArray *data = @[@7, @4, @9, @2, @5, @8, @11, @3, @12, @1];
    
    BST *tree = [[BST alloc] init];
    for (int i = 0; i < data.count; i++) {
        [tree add:data[i]];
    }
    
    NSLog(@"tree = %@",tree);
}

• 运行结果

  
  添加节点.png

2.2 根据元素内容获取节点

• 核心代码如下

- (TreeNode *)node:(id)element {
    TreeNode *node = _root;
    int cmp = 0;
    while (node != nil) {
        cmp = [self compare:element element2:node.element];
        if (cmp == 0) { // 当前节点
            return node;
        } else if (cmp > 0) {   // 右子树
            node = node.right;
        } else {    // 左子树
            node = node.left;
        }
    }
    return nil;
}

2.3 删除节点

接下来我们分为三种情况分别处理，即 叶子节点，度为1的节点，度为2的节点

2.3.1 删除节点 - 叶子节点

直接删除

• 为左子树节点 node == node.parent.left，则 node.parent.left = nil
• 为右子树节点 node == node.parent.right，则 node.parent.right = nil
• 为根节点 node.parent == nil，则root = nil

删除叶子节点.png

2.3.2 删除节点 - 度为1的节点

用子节点代替原节点的位置
其中 child是node.left或者child是node.right

用child替代node的位置

• 如果node是左子节点

child.parent = node.parent
node.parent.left = child

• 如果node是右子节点

child.parent = node.parent
node.parent.right = child

• 如果node是根节点

root = child
child.parent = nil

删除度为1的节点.png

2.3.3 删除节点 - 度为2的节点

如下图所示：先删除5，再删除4

• 先用前驱或者后继节点的值覆盖原节点的值
• 然后删除相应的前驱或者后继节点

如果一个节点的度为2，那么它的前驱，后继节点的度只可能是1或者0

删除度为2的节点.png

• 代码实现如下

/// 删除节点 node
- (void)removeNode:(TreeNode *)node {
    if (node == nil) {
        return;
    }
    
    self.size--;
    
    if (node.hasTwoChildren) {  // 度为2的节点
        // 找到后继节点
        TreeNode *s = [self successor:node];
        // 用后继节点的值覆盖度为2的节点的值
        node.element = s.element;
        // 删除后继节点
        node = s;
    }
    
    // 删除node节点(node的度必然是1或者0)
    TreeNode *replacement = node.left != nil ? node.left : node.right;
    
    if (replacement != nil) {   // 1.node是度为1的节点
        // 更改parent
        replacement.parent = node.parent;
        // 更改parent的left,right的指向
        if (node.parent == nil) {   // node是度为1的节点并且是根节点
            self.root = replacement;
        } else if (node == node.parent.left) {  // 左子节点
            node.parent.left = replacement;
        } else {    // node == node.parent.right
            node.parent.right = replacement;
        }
    } else if (node.parent == nil) {    // 2.node是叶子节点并且是根节点
        self.root = nil;
    } else {    // 3.node是叶子节点,但不是根节点
        if (node == node.parent.left) {
            node.parent.left = nil;
        } else {    // node == node.parent.right
            node.parent.right = nil;
        }
    }
}

• 测试代码

// 删节点
- (void)removeNode {
    NSArray *data = @[@7, @4, @9, @2, @5, @8, @11, @3, @12, @1];
    
    BST *tree = [[BST alloc] init];
    for (int i = 0; i < data.count; i++) {
        [tree add:data[i]];
    }
    
    NSLog(@"tree = %@",tree);
    
    [tree remove:@7];
    
    NSLog(@"tree = %@",tree);
}

• 运行结果

  
  image.png

三 平衡二叉搜索树

3.1 二叉搜索树的复杂度分析

1. 如果是按照 7、4、9、2、5、8、11 的顺序添加节点

image.png

复杂度：O(h) == O(logn)

2. 如果是从小到大添加节点 2，4，5，7，8，9，11

image.png

复杂度：O(h) == O(h)

• 当 n 比较大时，两者的性能差异比较大
• 比如 n = 1000000 时，二叉搜索树的最低高度是 20

3.2 退化成链表的另一种情况

删除节点时也可能会导致二叉搜索树退化成链表

       7
  4         9
2   5    8   11

• 添加、删除节点时，都可能会导致二叉搜索树退化成链表
• 有没有办法防止二叉搜索树退化成链表? 让添加、删除、搜索的复杂度维持在 O(logn)

3.3 平衡（Balance）

平衡:当节点数量固定时，左右子树的高度越接近，这棵二叉树就越平衡(高度越低)

image.png

3.4 理想平衡

最理想的平衡，就是像完全二叉树、满二叉树那样，高度是最小的

image.png

3.5 如何改进二叉搜索树

首先，节点的添加、删除顺序是无法限制的，可以认为是随机的

• 所以，改进方案是:在节点的添加、删除操作之后，想办法让二叉搜索树恢复平衡(减小树的高度)
• 如果接着继续调整节点的位置，完全可以达到理想平衡，但是付出的代价可能会比较大
  • 比如调整的次数会比较多，反而增加了时间复杂度

总结来说，比较合理的改进方案是:用尽量少的调整次数达到适度平衡即可

• 一棵达到适度平衡的二叉搜索树，可以称之为:平衡二叉搜索树

3.6 平衡二叉搜索树（Balanced Binary）

英文简称为:BBST

经典常见的平衡二叉搜索树有

AVL树

• Windows NT 内核中广泛使用

红黑树

• C++ STL(比如 map、set )
• Java 的 TreeMap、TreeSet、HashMap、HashSet
• Linux 的进程调度
• Ngix 的 timer 管理

一般也称它们为:自平衡的二叉搜索树(Self-balancing Binary Search Tree)

---

本文会持续更新中，更多精彩内容敬请期待。

---

本文参考 MJ老师的 恋上数据结构与算法

---

本人技术水平有限，如有错误欢迎指正。
书写整理不易，您的打赏点赞是对我最大的支持和鼓励，欢迎点赞打赏。

---

项目连接链接 - 09_Tree