文章目錄

• • 1.二叉查找樹概念
  • 2.二叉查找樹操作
  • • 2.1 查找
    • 2.2 插入
    • 2.3 刪除
    • 2.4 其他
  • 3. 支持重復數據的二叉查找樹
  • 4 有散列表了，還需要二叉查找樹？
  • 5 代碼實現

1.二叉查找樹概念

二叉查找樹要求，在樹中的任意一個節點，其左子樹中的每個節點的值，都要小于這個節點的值，而右子樹節點的值都大于這個節點的值。

2.二叉查找樹操作

2.1 查找

2.2 插入

2.3 刪除

2.4 其他

• 支持快速地查找最大節點和最小節點、前驅節點和后繼節點。
• 中序遍歷二又查找樹，可以輸出有序的數據序列，時間復雜度是 O(n) ，非常高效。因此，二叉查找樹也叫作二叉排序樹。

3. 支持重復數據的二叉查找樹

• 通過鏈表和支持動態擴容的數組等數據結構，把值相同的數據都存儲在同一個節點上。
• 每個節點仍然只存儲一個數據。在查找插入位置的過程中，如果碰到一個節點的值，與要插入數據的值相同，我們就將這個要插入的數據放到這個節點的右子樹，也就是說，把這個新插入的數據當作大于這個節點的值來處理。

• 在二叉查找樹中，查找、插入、刪除等很多操作的時間復雜度都跟樹的高度成正比。兩個極端情況的時間復雜度分別是 O(n) 和 O(logn) ，分別對應二叉樹退化成鏈表的情況和完全二叉樹。
• 為了避免時間復雜度的退化，針對二又查找樹，我們又設計了一種更加復雜的樹，平衡二叉查找樹，時間復雜度可以做到穩定的 O(logn)

4 有散列表了，還需要二叉查找樹？

• 散列表時間復雜度可以做到常量級的O(1), 而二叉查找樹在比較平衡的情況下, 時間復雜度才是 O(logn), 相對散列表,好像并沒有什么優勢,那我們為什么還要用二叉查找樹呢?
  幾個原因:
• 第一, 散列表中的數據是無序存儲的, 如果要輸出有序的數據,需要先進行排序.而對于二叉查找樹來說,我們只需要中序遍歷,就可以在O(n)的時間復雜度內,輸出有序的數據序列.
• 第二, 散列表擴容耗時很多,而且當遇到散列沖突時,性能不穩定,盡管二叉查找樹的性能不穩定,但是在工程中,我們最常用的平衡二叉查找樹的性能非常穩定,時間復雜度穩定在O(logn).
• 第三, 盡管散列表的查找等操作的時間復雜度是常量級的,但因為哈希沖突的存在,這個常量不一定比 logn 小,所以實際的查找速度可能不一定比 O(logn) 快. 加上哈希函數的耗時,也不一定就比平衡二又查找樹的效率高.
• 第四, 散列表的構造比二又查找樹要復雜,需要考慮的東西很多. 比如散列函數的設計、沖突解決辦法、擴容、縮容等.平衡二又查找樹只需要考慮平衡性這一個問題,而且這個問題的解決方案比較成熟、固定.
• 最后,為了避免過多的散列沖突,散列表裝載因子不能太大,特別是基于開放尋址法解決沖突的散列表,不然會浪費一定的存儲空間.
• 綜合這幾點, 平衡二又查找樹在某些方面還是優于散列表的, 所以,這兩者的存在并不沖突. 我們在實際的開發過程中,需要結合具體的需求來選擇使用哪一個.

5 代碼實現

/*** @description: 二叉查找樹* @author: michael ming* @date: 2019/5/16 23:48* @modified by: */ #include <iostream> #include <random> #include <time.h> using namespace std; template <class T> class BSTNode { public:T data;BSTNode<T> *left, *right;BSTNode():left(NULL), right(NULL){}BSTNode(const T& d, BSTNode<T> *l = NULL, BSTNode<T> *r = NULL){data = d; left = l; right = r;} }; template <class T> class BST { private:BSTNode<T>* root;int nodeLen; public:BST():root(NULL){}~BST(){clear(root);root = NULL;}void clear(BSTNode<T>* nodeP){if(nodeP == NULL)return;if (nodeP == NULL)return;clear(nodeP->left);clear(nodeP->right);delete nodeP;}BSTNode<T>* get_root() const { return root; }bool isEmpty() const { return root == NULL; }T* search(const T& d) const{return search(d, root);}T* search(const T& d, BSTNode<T>* p) const{while(p != NULL){if(d == p->data)return &(p->data);else if(d < p->data)p = p->left;elsep = p->right;}return 0;}T* get_max_data(){if(root == NULL)return NULL;BSTNode<T>* temp = root;while(temp->right != NULL)temp = temp->right;return &temp->data;}T* get_min_data(){if(root == NULL)return NULL;BSTNode<T>* temp = root;while(temp->left != NULL)temp = temp->left;return &temp->data;}void insert(const T& d){BSTNode<T> *p = root, *prev = NULL;while(p != NULL){prev = p;if(d < p->data)p = p->left;elsep = p->right;}if(root == NULL)root = new BSTNode<T>(d);else if(d < prev->data)prev->left = new BSTNode<T>(d);elseprev->right = new BSTNode<T>(d);}void del(T d){if(root == NULL)return;BSTNode<T> *p = root, *pfather = NULL;while(p != NULL && p->data != d){pfather = p;if(d > p->data)p = p->right;elsep = p->left;}if(p == NULL) //沒找到dreturn;if(p->left != NULL && p->right != NULL)//要刪除的節點有2個子節點{BSTNode<T> *minP = p->right, *minPFather = p;//找到右子樹最小的跟要刪的交換while(minP->left != NULL) //右子樹最小的肯定在左節點{minPFather = minP;minP = minP->left;}p->data = minP->data; //把右子樹最小的數付給要刪除的節點datap = minP; //minP付給p，刪除ppfather = minPFather;}//要刪除的是葉節點或者只有1個節點BSTNode<T>* child;if(p->left != NULL)child = p->left;else if(p->right != NULL)child = p->right;elsechild = NULL;if(pfather == NULL)//p是根節點root = child;else if(p == pfather->left)pfather->left = child;elsepfather->right = child;delete p;p = NULL;}int get_height(BSTNode<T>* nodep) //遞歸法, 求左右子樹高度，較大的+1{if(nodep == NULL)return 0;int leftheight = get_height(nodep->left);int rightheight = get_height(nodep->right);return max(leftheight, rightheight) + 1;}void inOrderPrint(BSTNode<T>* nodep) //二叉查找樹用中序打印，是有序的{if (nodep == NULL)return;inOrderPrint(nodep->left);cout << nodep->data << " ";inOrderPrint(nodep->right);} };int main() {BST<int> intBST;srand(time(0));for(int i = 0; i < 6; ++i){intBST.insert(rand());}intBST.insert(7);if(intBST.search(7))cout << *(intBST.search(7)) << endl;cout << "BST height: " << intBST.get_height(intBST.get_root()) << endl;intBST.inOrderPrint(intBST.get_root());cout << "max : " << *(intBST.get_max_data()) << ", min : " << *(intBST.get_min_data()) << endl;intBST.del(7);intBST.inOrderPrint(intBST.get_root());return 0; }

總結

以上是生活随笔為你收集整理的数据结构--二叉查找树 Binary Search Tree的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。