分類(lèi):
數(shù)據(jù)結(jié)構(gòu)
2012-10-11 07:25
208人閱讀
收藏
舉報(bào)
1.定義
二叉排序樹(shù)(Binary Sort Tree)又稱(chēng)二叉查找樹(shù),。 它或者是一棵空樹(shù),;或者是具有下列性質(zhì)的二叉樹(shù): (1)若左子樹(shù)不空,則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值,; (2)若右子樹(shù)不空,,則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值; (3)左,、右子樹(shù)也分別為二叉排序樹(shù),;
2.節(jié)點(diǎn)結(jié)構(gòu)
2.1 擁有key值(排序)
2.2 擁有value值(實(shí)用)
2.3左子樹(shù)指針
2.4右子樹(shù)指針
2.5父親節(jié)點(diǎn)指針(刪除節(jié)點(diǎn)需要處理節(jié)點(diǎn)上界)
3.優(yōu)/缺點(diǎn)
假設(shè)一個(gè)BST是平衡的,,那么CRUD一個(gè)元素的時(shí)間復(fù)雜度為 O(logN) 即為樹(shù)高。那么插入/刪除頻繁(很多動(dòng)態(tài)數(shù)據(jù))的處理性能會(huì)很好,。
但是插入與刪除操作容易讓一棵樹(shù)不平衡:
插入:如果插入數(shù)據(jù)有序性較好,,產(chǎn)生的樹(shù)將趨近于鏈表。 如 1,2,3,4,5 全部只有右節(jié)點(diǎn),。 只有當(dāng)插入很均勻的時(shí)候可能出現(xiàn)平衡(程序員不可控,,后續(xù)文章會(huì)有平衡樹(shù))
刪除:二叉查找樹(shù)一般的刪除策略(左右子節(jié)點(diǎn)都有的情況)是替換左子樹(shù)最大節(jié)點(diǎn),或者右子樹(shù)最小節(jié)點(diǎn),。長(zhǎng)期使用一種方式也會(huì)讓樹(shù)趨近鏈表,。
4處理過(guò)程
插入:二分處理過(guò)程。相等則更新節(jié)點(diǎn)/不處理,;小則往左走,,大則往右走,直到發(fā)現(xiàn)一個(gè)空節(jié)點(diǎn),,創(chuàng)建并添加,。添加一對(duì)指針關(guān)系:父親指向新節(jié)點(diǎn)/新節(jié)點(diǎn)指向父親。
查找:二分處理過(guò)程,。
查找最大值:二分處理過(guò)程,,不過(guò)一直往右走到底即可。
刪除:分情況:1.葉節(jié)點(diǎn)刪除,,只考慮父節(jié)點(diǎn)對(duì)應(yīng)子指針,。2.只有左/右子樹(shù)的節(jié)點(diǎn)刪除,把子樹(shù)往上“提”一層,,類(lèi)似于雙向鏈表刪除,,考慮下刪除節(jié)
點(diǎn)是父親的左節(jié)點(diǎn)還是右節(jié)點(diǎn)。3.左右子樹(shù)都存在,,找到左子樹(shù)最大值/右子樹(shù)最小值,,與刪除節(jié)點(diǎn)進(jìn)行k,v交換,之后刪除找到的節(jié)點(diǎn),,即1,2的情況,。
5.一個(gè)粗略的實(shí)現(xiàn)
- #include <iostream>
- using namespace std;
-
-
-
-
-
-
-
- struct BST_DATA{
- int key;
- int value;
- };
-
- class BinarySearchTreeNode{
- public:
- BinarySearchTreeNode(BST_DATA newdata)
- {
- key=newdata.key;
- value=newdata.value;
- left=NULL;
- right=NULL;
- parent=NULL;
- }
- public:
- int key;
- int value;
- BinarySearchTreeNode * left;
- BinarySearchTreeNode * right;
- BinarySearchTreeNode * parent;
- };
-
-
- bool binarySearchTreeInsert(BinarySearchTreeNode ** ppNode, BST_DATA newdata,BinarySearchTreeNode *pParentNode)
- {
- if(NULL == *ppNode){
- *ppNode= new BinarySearchTreeNode(newdata);
- (*ppNode)->parent=pParentNode;
- return true;
- }
-
- if((newdata.key == (*ppNode)->key))
- {
- (*ppNode)->value=newdata.value;
- return true;
- }
- if((newdata.key < (*ppNode)->key))
- {
- return binarySearchTreeInsert( & ((*ppNode)->left), newdata, *ppNode );
- }
- else
- {
- return binarySearchTreeInsert( & ((*ppNode)->right), newdata, *ppNode );
- }
- }
-
- bool insert(BinarySearchTreeNode ** ppNode, BST_DATA newdata){
-
- if(NULL==ppNode){return false;}
-
- if(NULL==*ppNode){
- *ppNode= new BinarySearchTreeNode(newdata);
- return true;
- }
-
- return binarySearchTreeInsert(ppNode, newdata,NULL);
- }
-
-
-
-
- void pre_scan(BinarySearchTreeNode ** ppNode){
- if(NULL!=ppNode && NULL !=*ppNode){
-
- printf("%d,",(*ppNode)->key);
- pre_scan(&((*ppNode)->left));
- pre_scan(&((*ppNode)->right));
- }
- }
-
- void in_scan(BinarySearchTreeNode ** ppNode){
- if(NULL!=ppNode && NULL !=*ppNode){
- in_scan(&((*ppNode)->left));
-
- printf("%d,",(*ppNode)->key);
- in_scan(&((*ppNode)->right));
- }
- }
-
-
-
-
-
- BinarySearchTreeNode * find_node(BinarySearchTreeNode ** ppNode,BST_DATA newdata)
- {
- BinarySearchTreeNode * pHead = * ppNode;
- while(pHead!=NULL){
- if(pHead->key==newdata.key)
- {
- return pHead;
- }else if(pHead->key>newdata.key)
- {
- pHead=pHead->left;
- }else
- {
- pHead=pHead->right;
- }
- }
- return NULL;
- }
-
-
- BinarySearchTreeNode * find_max_node(BinarySearchTreeNode ** ppNode)
- {
- BinarySearchTreeNode * pHead = * ppNode;
- while(pHead->right!=NULL){pHead=pHead->right;}
- return pHead;
- }
-
-
-
- void delete_tree(BinarySearchTreeNode ** ppNode)
- {
- if(NULL==ppNode || NULL==*ppNode){return ;}
- delete_tree(&((* ppNode)->left));
- delete_tree(&((* ppNode)->right));
- delete (*ppNode);
- }
-
-
-
-
-
- bool delete_node_from_tree(BinarySearchTreeNode** ppNode, BST_DATA data)
- {
-
- if(NULL == ppNode || NULL == *ppNode) {return false;}
-
- BinarySearchTreeNode *deleteNode = * ppNode;
- BinarySearchTreeNode * l_maxNode;
-
-
- if(deleteNode->key==data.key)
- {
-
-
- if(deleteNode->left!=NULL && deleteNode->right!=NULL)
- {
- l_maxNode = find_max_node(&(deleteNode->left));
-
- l_maxNode->key = l_maxNode->key + deleteNode->key;
- deleteNode->key = l_maxNode->key - deleteNode->key;
- l_maxNode->key = l_maxNode->key - deleteNode->key;
- l_maxNode->value = l_maxNode->value + deleteNode->value;
- deleteNode->value = l_maxNode->value - deleteNode->value;
- l_maxNode->value = l_maxNode->value - deleteNode->value;
-
- if(l_maxNode->parent->right==l_maxNode){
- l_maxNode->parent->right=l_maxNode->left;
- }else{
- l_maxNode->parent->left=l_maxNode->left;
- }
-
- if (NULL != l_maxNode->left) {
- l_maxNode->left->parent = l_maxNode->parent;
- }
-
- delete l_maxNode;
- }
- else{
-
-
- if(deleteNode->left!=NULL)
- {
- if(deleteNode->parent!=NULL)
- {
-
- if(deleteNode->parent->left==deleteNode)
- {
- deleteNode->parent->left=deleteNode->left;
- }else
- {
- deleteNode->parent->right=deleteNode->left;
- }
- }
-
- deleteNode->left->parent = deleteNode->parent;
- }
-
- else if(deleteNode->right!=NULL)
- {
- if(deleteNode->parent!=NULL)
- {
-
- if(deleteNode->parent->left==deleteNode)
- {
- deleteNode->parent->left=deleteNode->right;
- }else
- {
- deleteNode->parent->right=deleteNode->right;
- }
- }
-
- deleteNode->right->parent = deleteNode->parent;
- }
-
- else
- {
- if(deleteNode->parent!=NULL)
- {
-
- if(deleteNode->parent->left==deleteNode)
- {
- deleteNode->parent->left=NULL;
- }else
- {
- deleteNode->parent->right=NULL;
- }
- }
- }
-
- delete deleteNode;
- }
- return true;
- }
- else if(deleteNode->key<data.key)
- {
- return delete_node_from_tree(&((*ppNode)->right), data);
- }
- else
- {
- return delete_node_from_tree(&((*ppNode)->left), data);
- }
-
- return true;
- }
-
-
-
- int main(void)
- {
- int key_array[10] = {12,5,18,2,15,9,19,13,17,3};
- int value_array[10]={ 1,2, 3,4, 5,6, 7, 8, 9,10};
- BST_DATA bst_data_array[10]={0};
- for(int i=0;i<10;i++)
- {
- bst_data_array[i].key=key_array[i];
- bst_data_array[i].value=value_array[i];
- }
-
- BinarySearchTreeNode * ppNode=NULL;
- for(int j=0;j<10;j++){
- insert(&ppNode, bst_data_array[j]);
- }
-
-
- pre_scan(&ppNode);
- printf("\n");
- in_scan(&ppNode);
- printf("\n");
-
- BST_DATA td;
- td.key=1;
- td.value=2;
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- delete_node_from_tree(&ppNode,bst_data_array[1]);
- pre_scan(&ppNode);
- printf("\n");
- delete_tree(&ppNode);
- return 0;
- }
|