树论_二叉查找树

二叉查找树适合动态查找，即随时可能有插入和删除操作

Binary Search Tree的定义

• 对于一颗非空BST，其左子树上的所有节点的data小于其根节点的data，其右子树上的所有节点的data大于其根节点的data
• BST的非空左子树和非空右子树也是BST

利用BST左小于右的特性，可以用来找到BST中两个节点的最近的共同的祖先节点（这里可以把节点自己也算作祖先）
从根节点开始，若两个节点的key都小于当前节点的key，说明公共祖先在左子树上，递归左子树
若两个节点的key都大于当前节点的key，说明公共祖先在右子树上，递归右子树
否则说明公共祖先就是这个节点

BST查找特定key

递归实现

假设在函数外有一个指针接收找到的节点的地址，没找到返回空

对于当前访问的节点，若不为空，有三种：

1. 要查找的key小于当前节点，则递归查找左子树
2. 要查找的key大于当前节点，则递归查找右子树
3. 要查找的key等于当前节点，则返回当前节点的指针

TreeNode* BSTfind(TreeNode* t,DataType key){ if(!root)return nullptr; if(key<t->data)return BSTfind(t->left,key); //1. else if(key>t->data)return BSTfind(t->right,key); //2. else return t; //3. }

注意到这是尾递归，所以可以写成迭代函数

迭代实现

TreeNode* BSTfind(TreeNode* t,DataType key){ TreeNode* p=t; //用p指针来访问节点 while(p){ if(key<p->data)p=p->left; //1. else if(key>p->data)p=p->right; //2. else break; //3. } return p; }

BST查找最小值和最大值

根据BST的特性，一颗BST的最小值在最左端的节点上，最大值在最右端的节点上
也是尾递归

递归实现

TreeNode* findMin(TreeNode* t){ //找最小值 if(!t)return nullptr; //空树的情况 if(t->left)return findMin(t->left); //没到最左端 else return t; //到了最左端 } TreeNode* findMax(TreeNode* t){ if(!t)return nullptr; if(t->right)return findMax(t->right); else return t; }

迭代实现

TreeNode* findMin(TreeNode* t){ if(!t)return nullptr; while(t->left){ t=t->left; } return t; } TreeNode* findMax(TreeNode* t){ if(!t)return nullptr; while(t->right){ t=t->right; } return t; }

BST的插入

与查找类似，若走到空节点，说明需要在这里插入，若走到与key相等的节点，则根据实际需要处理（插入失败或插在子树的根节点上）

返回已经插入了的根节点

bool isInsert=true; //判断是否插入成功 TreeNode* BSTinsert(TreeNode* t,DataType key){ if(!t){ //空节点 t=new TreeNode; t->data=key; t->left=t->right=nullptr; return t; } if(key<t->data)t->left=BSTinsert(t->left); //1. else if(key>t->data)t->right=BSTinsert(t->right); //2. else isInsert=false; //3. return t;

也可以看作是尾递归

BST的删除

与查找类似，若走到与key相等的节点，说明需要在这里删除，若走到空节点，则说明BST中找不到需要删除的节点

返回已经删除了的根节点

若找到了需要删除的节点

1. 若该节点左子树和右子树都为空，则返回空（其实就是返回空左子树和空右子树其中之一，可合并为下面两种情况）
2. 若该节点存在左子树，右子树为空，则返回左子树，回收该节点
3. 若该节点存在右子树，左子树为空，则返回右子树，回收该节点
4. 若左右子树都不空，有两种方案
   • 找到左子树上的最大值节点leftMax，与该节点交换data，然后递归删除leftMax
   • 找到右子树上的最小值节点rightMin，与该节点交换data，然后递归删除rightMin
     leftMax和rightMin都是存在空子树的情况，删除比较简单

bool isDelete=true; TreeNode* BSTdelete(TreeNode* t,key){ if(!t){ //找不到要删除的节点 isDelete=false; return t; //不做处理，直接返回 } if(key<t->data)t->left=BSTdelete(t->left,key); else if(key>t->data)t->right=BSTdelete(t->right,key); else { if(t->left&&t->right){ //左右子树都不空 TreeNode* leftMin; leftMax=findMin(t->left); t->data=leftMin->data; //和t交换 t->left=BSTdelete(t->left,leftMin->data); //删除leftMax } else if(t->left){ //左子树不空 TreeNode* tmp=t; t=t->left; delete tmp; //回收 } else { TreeNode* tmp=t; t=t->right; delete tmp; } } return t; //返回已经删除了的根节点 }

BST的缺点

随着插入和删除操作增多，可能出现斜二叉树这种极端情况，因为BST的查找和删除操作的最坏时间复杂度都是树的高度，所以树的高度越小越好

优化：平衡二叉树