免费A级毛片无码专区网站-成人国产精品视频一区二区-啊 日出水了 用力乖乖在线-国产黑色丝袜在线观看下-天天操美女夜夜操美女-日韩网站在线观看中文字幕-AV高清hd片XXX国产-亚洲av中文字字幕乱码综合-搬开女人下面使劲插视频

  1. 首頁(yè) > 生活 > >

二叉搜索樹(shù) - C++ 實(shí)現(xiàn)

生活百科

二叉搜索樹(shù) - C++ 實(shí)現(xiàn)概述 Overview二叉查找樹(shù)（英語(yǔ)：Binary Search Tree, 后文中簡(jiǎn)稱(chēng) BST）, 也稱(chēng)為二叉搜索樹(shù)、有序二叉樹(shù)（ordered binary tree）或排序二叉樹(shù)（sorted binary tree）,是在 20 世紀(jì) 60 年代為解決標(biāo)記數(shù)據(jù)的高效存儲(chǔ)問(wèn)題而設(shè)計(jì)的, 由 Conway Berners-Lee 和 David Wheeler 發(fā)明.
具體指的是一棵空樹(shù)或者具有下列性質(zhì)的二叉樹(shù):

  1. 若任意節(jié)點(diǎn)的左子樹(shù)不空, 則左子樹(shù)上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值；
  2. 若任意節(jié)點(diǎn)的右子樹(shù)不空, 則右子樹(shù)上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；
  3. 任意節(jié)點(diǎn)的左、右子樹(shù)也分別為二叉查找樹(shù)；
簡(jiǎn)單來(lái)說(shuō), 二叉搜索樹(shù)中的每一個(gè)節(jié)點(diǎn)都滿(mǎn)足: 左子樹(shù)中的所有元素均小于該節(jié)點(diǎn)元素; 右子樹(shù)中的所有元素均大于該節(jié)點(diǎn)元素. \(左子樹(shù)元素 \le 本節(jié)點(diǎn)元素 \le 右子樹(shù)元素\). 左小右大.
這種結(jié)構(gòu)上的設(shè)計(jì)使得 BST 可以以二分查找思路實(shí)現(xiàn) \(\Omega(\log n)\) （不是大o, 而是下限在logn）級(jí)別的快速增, 刪, 查等操作, 因?yàn)樵跇?shù)中的每一步操作都能排除一半的元素. 完成一顆二叉搜索樹(shù)的建立之后, 我們還可以以中序遍歷的方式得到排序后的序列, 這也是二叉搜索樹(shù)被稱(chēng)為排序二叉樹(shù)的原因.
需要注意的是, 二叉搜索樹(shù)的效率與在建立時(shí)輸入的元素順序有很大的關(guān)系. 在最壞情況下, 二叉搜索樹(shù)會(huì)退化成鏈表. 樹(shù)層數(shù)大大增加使得查找等操作需要消耗更多的時(shí)間）此時(shí), 需要對(duì)樹(shù)進(jìn)行額外的優(yōu)化 - 平衡, 來(lái)保證高效的運(yùn)行效率. 在本文中我們不作討論, 本文僅介紹樸素的二叉搜索樹(shù).
如果看完之后還是不太理解的話(huà), 可以看看這個(gè)美國(guó)舊金山大學(xué)CS做的一個(gè)算法可視化. Binary Search Tree Visualization (usfca.edu) 在這個(gè)網(wǎng)站上詳細(xì)地看到 BST 每一步的操作.做的很好, 不妨去玩玩!
基本操作 Operations和其他的數(shù)據(jù)結(jié)構(gòu)類(lèi)似, 二叉搜索樹(shù)也有著這樣的幾個(gè)基本操作.
搜索 Search?根據(jù)元素值直接搜索節(jié)點(diǎn)假設(shè)要搜素的節(jié)點(diǎn)的元素值為 item.
那么搜索就是要從數(shù)的根節(jié)點(diǎn) root 開(kāi)始, 逐節(jié)點(diǎn)遍歷該樹(shù).
若當(dāng)前掃描到的節(jié)點(diǎn)的元素值小于 item, 則往右走; 若元素值大于 item 則左走. 直到掃描到目標(biāo)節(jié)點(diǎn)或遇到 nil 節(jié)點(diǎn)時(shí)（未找到該元素）停止搜索, 返回結(jié)果.
具體的代碼實(shí)現(xiàn)如下.
void insert(const int item){TreeNode *scan = root;TreeNode *prev = root;while (scan != nullptr){prev = scan;scan = item < scan->data ? scan->left : scan->right;}TreeNode *newNode = new TreeNode(item);if (root){(item < prev->data ? prev->left : prev->right) = newNode;newNode->parent = prev;}else{root = newNode;}return;}? 找節(jié)點(diǎn)的前驅(qū)/后繼前驅(qū)節(jié)點(diǎn)指的是樹(shù)在中序遍歷的序列中, 目標(biāo)結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)(類(lèi)似鏈表中前驅(qū)的定義).（當(dāng)目標(biāo)結(jié)點(diǎn)為第一個(gè)結(jié)點(diǎn)是返回nil）
e.g. 如一顆樹(shù)的中序遍歷序列為: {1, 2, 3, 4, 5}, 那么元素值為 2 的節(jié)點(diǎn)的前驅(qū)就是元素值為 1 的節(jié)點(diǎn); 元素值為 1 的節(jié)點(diǎn)的前驅(qū)就是 nil.
在BST中, 因?yàn)锽ST 的定義, 其中序遍歷序列就是樹(shù)中所有元素按元素值大小排序而輸出的序列.
因此, 前驅(qū)節(jié)點(diǎn)也可以被定義成所有小于目標(biāo)元素的所有元素中的最大值 \(\max( \{item\ |\ item \in tree\and item < target\})\).
根據(jù)此定義我們來(lái)完成搜索前驅(qū)節(jié)點(diǎn)的算法.
由 BST 的定義我們可以得到一個(gè)結(jié)論,
設(shè)有一個(gè)節(jié)點(diǎn) node, 在中序遍歷的序列中:
  1. 如果 node 是父節(jié)點(diǎn)的左節(jié)點(diǎn)
    左子樹(shù)中的所有節(jié)點(diǎn) < node < 父節(jié)點(diǎn)
  2. 如果 node 是父節(jié)點(diǎn)的右節(jié)點(diǎn)
    父節(jié)點(diǎn) < node < 左子樹(shù)中的所有節(jié)點(diǎn)

    經(jīng)驗(yàn)總結(jié)擴(kuò)展閱讀