《戀上數(shù)據(jù)結(jié)構(gòu)與算法一》筆記（八）二叉搜索樹(shù)

目錄
  • 二叉搜索樹(shù)概念
  • 二叉搜索樹(shù)的接口設(shè)計(jì)，包括增，刪，改，查
  • 平衡二叉搜索樹(shù)
一 二叉搜索樹(shù)

二叉搜索樹(shù)是二叉樹(shù)的一種，是應(yīng)用非常廣泛的一種二叉樹(shù)，英文簡(jiǎn)稱(chēng)為 BST

  • 又被稱(chēng)為:二叉查找樹(shù)、二叉排序樹(shù)
  • 任意一個(gè)節(jié)點(diǎn)的值都大于其左子樹(shù)所有節(jié)點(diǎn)的值
  • 任意一個(gè)節(jié)點(diǎn)的值都小于其右子樹(shù)所有節(jié)點(diǎn)的值
  • 它的左右子樹(shù)也是一棵二叉搜索樹(shù)

二叉搜索樹(shù)可以大大提高搜索數(shù)據(jù)的效率

二叉搜索樹(shù)存儲(chǔ)的元素必須具備可比較性

  • 比如 int、double 等
  • 如果是自定義類(lèi)型，需要指定比較方式
  • 不允許為 null
二叉搜索樹(shù).png
二 二叉搜索樹(shù)的接口設(shè)計(jì)
/**
 * 清除所有元素
 */
- (void)clear;

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

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

/**
 * 刪除元素
 * @param element
 */
- (void)remove:(id)element;
2.1 添加節(jié)點(diǎn)

添加步驟
1.找到父節(jié)點(diǎn) parent
2.創(chuàng)建新節(jié)點(diǎn) node
3.parent.left = node 或者 parent.right = node

遇到值相等的元素如何處理？ 覆蓋舊的值

  • 代碼實(shí)現(xiàn)
- (void)add:(id)element {
    [self elementNotNullCheck:element];
    
    // 添加第一個(gè)節(jié)點(diǎn)
    if (_root == nil) {
        _root = [[TreeNode alloc] initWithElement:element parent:nil];
        _size++;
        return;
    }
    
    // 添加的不是第一個(gè)節(jié)點(diǎn)
    // 找到父節(jié)點(diǎn)
    TreeNode *parent = _root;
    TreeNode *node = _root;
    int cmp = 0;
    
    while (node != nil) {
        cmp = [self compare:element element2:node.element];
        parent = node;
        
        if (cmp > 0) {  // 右節(jié)點(diǎn)
            node = node.right;
        } else if (cmp < 0) {   // 左節(jié)點(diǎn)
            node = node.left;
        } else {    // 相對(duì) - 覆蓋
            node.element = element;
            return;
        }
    }
    
    // 查看插入到父節(jié)點(diǎn)的哪個(gè)位置
    TreeNode *newNode = [[TreeNode alloc] initWithElement:element parent:parent];
    if (cmp > 0) {
        parent.right = newNode;
    } else {
        parent.left = newNode;
    }
    _size++;
}
  • 測(cè)試代碼
// 打印一棵二叉樹(shù)
- (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);
}

  • 運(yùn)行結(jié)果


    添加節(jié)點(diǎn).png
2.2 根據(jù)元素內(nèi)容獲取節(jié)點(diǎn)
  • 核心代碼如下
- (TreeNode *)node:(id)element {
    TreeNode *node = _root;
    int cmp = 0;
    while (node != nil) {
        cmp = [self compare:element element2:node.element];
        if (cmp == 0) { // 當(dāng)前節(jié)點(diǎn)
            return node;
        } else if (cmp > 0) {   // 右子樹(shù)
            node = node.right;
        } else {    // 左子樹(shù)
            node = node.left;
        }
    }
    return nil;
}
2.3 刪除節(jié)點(diǎn)

接下來(lái)我們分為三種情況分別處理，即 葉子節(jié)點(diǎn)，度為1的節(jié)點(diǎn)，度為2的節(jié)點(diǎn)

2.3.1 刪除節(jié)點(diǎn) - 葉子節(jié)點(diǎn)

直接刪除

  • 為左子樹(shù)節(jié)點(diǎn) node == node.parent.left，則 node.parent.left = nil
  • 為右子樹(shù)節(jié)點(diǎn) node == node.parent.right，則 node.parent.right = nil
  • 為根節(jié)點(diǎn) node.parent == nil，則root = nil
刪除葉子節(jié)點(diǎn).png
2.3.2 刪除節(jié)點(diǎn) - 度為1的節(jié)點(diǎn)

用子節(jié)點(diǎn)代替原節(jié)點(diǎn)的位置
其中 child是node.left或者child是node.right

用child替代node的位置

  • 如果node是左子節(jié)點(diǎn) 
child.parent = node.parent
node.parent.left = child
  • 如果node是右子節(jié)點(diǎn) 
child.parent = node.parent
node.parent.right = child
  • 如果node是根節(jié)點(diǎn)
root = child
child.parent = nil
刪除度為1的節(jié)點(diǎn).png
2.3.3 刪除節(jié)點(diǎn) - 度為2的節(jié)點(diǎn)

如下圖所示：先刪除5，再刪除4

  • 先用前驅(qū)或者后繼節(jié)點(diǎn)的值覆蓋原節(jié)點(diǎn)的值
  • 然后刪除相應(yīng)的前驅(qū)或者后繼節(jié)點(diǎn)

如果一個(gè)節(jié)點(diǎn)的度為2，那么它的前驅(qū)，后繼節(jié)點(diǎn)的度只可能是1或者0

刪除度為2的節(jié)點(diǎn).png
  • 代碼實(shí)現(xiàn)如下
/// 刪除節(jié)點(diǎn) node
- (void)removeNode:(TreeNode *)node {
    if (node == nil) {
        return;
    }
    
    self.size--;
    
    if (node.hasTwoChildren) {  // 度為2的節(jié)點(diǎn)
        // 找到后繼節(jié)點(diǎn)
        TreeNode *s = [self successor:node];
        // 用后繼節(jié)點(diǎn)的值覆蓋度為2的節(jié)點(diǎn)的值
        node.element = s.element;
        // 刪除后繼節(jié)點(diǎn)
        node = s;
    }
    
    // 刪除node節(jié)點(diǎn)(node的度必然是1或者0)
    TreeNode *replacement = node.left != nil ? node.left : node.right;
    
    if (replacement != nil) {   // 1.node是度為1的節(jié)點(diǎn)
        // 更改parent
        replacement.parent = node.parent;
        // 更改parent的left,right的指向
        if (node.parent == nil) {   // node是度為1的節(jié)點(diǎn)并且是根節(jié)點(diǎn)
            self.root = replacement;
        } else if (node == node.parent.left) {  // 左子節(jié)點(diǎn)
            node.parent.left = replacement;
        } else {    // node == node.parent.right
            node.parent.right = replacement;
        }
    } else if (node.parent == nil) {    // 2.node是葉子節(jié)點(diǎn)并且是根節(jié)點(diǎn)
        self.root = nil;
    } else {    // 3.node是葉子節(jié)點(diǎn),但不是根節(jié)點(diǎn)
        if (node == node.parent.left) {
            node.parent.left = nil;
        } else {    // node == node.parent.right
            node.parent.right = nil;
        }
    }
}
  • 測(cè)試代碼
// 刪節(jié)點(diǎn)
- (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);
}

  • 運(yùn)行結(jié)果


    image.png
三 平衡二叉搜索樹(shù)
3.1 二叉搜索樹(shù)的復(fù)雜度分析
  1. 如果是按照 7、4、9、2、5、8、11 的順序添加節(jié)點(diǎn)
image.png

復(fù)雜度：O(h) == O(logn)

  1. 如果是從小到大添加節(jié)點(diǎn) 2，4，5，7，8，9，11
image.png

復(fù)雜度：O(h) == O(h)

  • 當(dāng) n 比較大時(shí)，兩者的性能差異比較大
  • 比如 n = 1000000 時(shí)，二叉搜索樹(shù)的最低高度是 20
3.2 退化成鏈表的另一種情況

刪除節(jié)點(diǎn)時(shí)也可能會(huì)導(dǎo)致二叉搜索樹(shù)退化成鏈表

       7
  4         9
2   5    8   11
  • 添加、刪除節(jié)點(diǎn)時(shí)，都可能會(huì)導(dǎo)致二叉搜索樹(shù)退化成鏈表
  • 有沒(méi)有辦法防止二叉搜索樹(shù)退化成鏈表? 讓添加、刪除、搜索的復(fù)雜度維持在 O(logn)
3.3 平衡（Balance）

平衡:當(dāng)節(jié)點(diǎn)數(shù)量固定時(shí)，左右子樹(shù)的高度越接近，這棵二叉樹(shù)就越平衡(高度越低)

image.png
3.4 理想平衡

最理想的平衡，就是像完全二叉樹(shù)、滿(mǎn)二叉樹(shù)那樣，高度是最小的

image.png
3.5 如何改進(jìn)二叉搜索樹(shù)

首先，節(jié)點(diǎn)的添加、刪除順序是無(wú)法限制的，可以認(rèn)為是隨機(jī)的

  • 所以，改進(jìn)方案是:在節(jié)點(diǎn)的添加、刪除操作之后，想辦法讓二叉搜索樹(shù)恢復(fù)平衡(減小樹(shù)的高度)
  • 如果接著繼續(xù)調(diào)整節(jié)點(diǎn)的位置，完全可以達(dá)到理想平衡，但是付出的代價(jià)可能會(huì)比較大
    • 比如調(diào)整的次數(shù)會(huì)比較多，反而增加了時(shí)間復(fù)雜度

總結(jié)來(lái)說(shuō)，比較合理的改進(jìn)方案是:用盡量少的調(diào)整次數(shù)達(dá)到適度平衡即可

  • 一棵達(dá)到適度平衡的二叉搜索樹(shù)，可以稱(chēng)之為:平衡二叉搜索樹(shù)
3.6 平衡二叉搜索樹(shù)（Balanced Binary）

英文簡(jiǎn)稱(chēng)為:BBST

經(jīng)典常見(jiàn)的平衡二叉搜索樹(shù)有

AVL樹(shù)

  • Windows NT 內(nèi)核中廣泛使用

紅黑樹(shù)

  • C++ STL(比如 map、set )
  • Java 的 TreeMap、TreeSet、HashMap、HashSet
  • Linux 的進(jìn)程調(diào)度
  • Ngix 的 timer 管理

一般也稱(chēng)它們?yōu)?自平衡的二叉搜索樹(shù)(Self-balancing Binary Search Tree)

本文會(huì)持續(xù)更新中，更多精彩內(nèi)容敬請(qǐng)期待。

本文參考 MJ老師的 戀上數(shù)據(jù)結(jié)構(gòu)與算法

《戀上數(shù)據(jù)結(jié)構(gòu)與算法一》筆記

本人技術(shù)水平有限，如有錯(cuò)誤歡迎指正。
書(shū)寫(xiě)整理不易，您的打賞點(diǎn)贊是對(duì)我最大的支持和鼓勵(lì)，歡迎點(diǎn)贊打賞。

項(xiàng)目連接鏈接 - 09_Tree

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容