The one or two fork search tree is the two fork tree.lookupThe extension of the domain has the efficiency of two points lookup and flexibility of chain entry.
- The efficiency of two point lookup: once every iteration, the scope of search is reduced by half. For binary search trees, the scope of each search is reduced by one subtree (ideally half of the nodes).
- Flexibility of chain insertion: Binary lookup tree is chain structure, so it has O (1) time efficiency of inserting and deleting list.
Note: After each iteration, the search range is reduced by only one node, and the search time efficiency is O (n). The time efficiency of the two point lookup is O (logn), so the time efficiency of the two fork search tree is specific.Tree shapeIt can be either O (logn) or O (n).
Figure 1
Figure 1 shows.Two fork search tree degenerate into linked listTherefore, in order to maintain the efficiency of binary search tree, the balanced binary tree with equilibrium condition will be introduced.
Two. Search operation
1. recursive lookup
BinaryTreeNode* find(BinaryTreeNode *pRoot, int x)
{
if(pRoot == nullptr)
return nullptr;
if(pRoot->value == x)
return pRoot;
else if(pRoot->value > x)
return find(pRoot->lChild, x);
else
return find(pRoot->rChild, x);
}
2. Non recursive search
BinaryTreeNode* find(BinaryTreeNode *pRoot, int x)
{
if(pRoot == nullptr)
return nullptr;
while(pRoot != nullptr && pRoot->value != x) {
if(pRoot->value > x)
pRoot = pRoot->lChild;
if(pRoot->value < x)
pRoot = pRoot->rChild;
}
return pRoot;
}
Three. Insert operation
1. No duplicate nodes
BinaryTreeNode* insert(BinaryTreeNode *pRoot, int x)
{
if(pRoot == nullptr) {
pRoot = new BinaryTreeNode;
pRoot->value = x;
pRoot->lChild = nullptr;
pRoot->rChild = nullptr;
}
else {
if(pRoot->value > x)
pRoot->lChild = insert(pRoot->lChild, x);
if(pRoot->value < x)
pRoot->rChild = insert(pRoot->rChild, x);
// If the node to be inserted already exists, it returns the existing node directly.}// After each recursion, the current root value is returned for use by the upper level, and finally the root node of the entire tree is returnedReturn pRoot;}
Analysis: There is a bug in the code that does not insert when an empty tree is passed in. The reason for this is that when we insert a node into an empty list, the newly inserted node is the head pointer of the list, because this is the caseChanging head pointer，Therefore, the pRoot parameter must be set as a pointer to the pointer.Out of the function, pRoot is still a null pointer.。In short, for any function that involves changing the head pointer, the incoming pointer should be the pointer to the head pointer.
BinaryTreeNode* insert(BinaryTreeNode **pRoot, int x) // pRootPointer to pointer{If (*pRoot = = nullptr) {*pRoot = new BinaryTreeNode;(*pRoot) -> value = x;(*pROOT) -> lChild = nullptr;(*pRoot) -> rChild = nullptr;}Else {If ((*pRoot) -> value >X)(*pRoot) -> lChild = insert (& ((*pRoot) -> lChild), x);If ((*pRoot) -> value < x)(*pRoot) -> rChild = insert (& ((*pRoot) -> rChild), x);}Return *pRoot;}
2. Repeated nodes
If the binary search tree contains duplicate elements, the duplicate elements can be handled by retaining an auxiliary variable in the node structure to indicate the frequency of occurrence.
struct BinaryTreeNode {
int value;
unsigned int occur;
BinaryTreeNode *lChild;
BinaryTreeNode *rChild;
};
BinaryTreeNode* insert(BinaryTreeNode **pRoot, int x) // pRootPointer to pointer{If (*pRoot = = nullptr) {*pRoot = new BinaryTreeNode;(*pRoot) -> value = x;(*pROOT) -> occur = 1;(*pRoot) -> lChild = nullptr;(*pRoot) -> rChild = nullptr;}Else {IF ((*pRoot) -> value > x)(*pRoot) -> lChild = insert (& ((*pRoot) -> lChild), x);If (*PRoot) -> value < x)(*pRoot) -> rChild = insert (& ((*pRoot) -> rChild), x);If (*pRooT) -> value = = x)(*pRoot) -> occur++;}Return *pRoot;}
Four. Delete operation
BinaryTreeNode* DeleteNode(BinaryTreeNode *pRoot, int x)
{
if(pRoot == nullptr)
return nullptr;
if(pRoot->value > x)
pRoot->lChild = DeleteNode(pRoot->lChild, x);
if(pRoot->value < x)
pRoot->rChild = DeleteNode(pRoot->rChild, x);
if(pRoot->value == x) {
// The deleted node has two children.If (pRoot-> lChild & & pRoot-> rChild) {BinaryTreeNode *temp = findMin(pRoot-> rChild);PRoot-> value = temp-> value;PRoot-> lChild = DeleteNode (pRoot->);RChild, x);}/ / the deleted node has zero or one child.Else {BinaryTreeNode *pNode = pRoot;If (pRoot-> lChi)LD = = nullptr)PRoot = pRoot-> rChild;Else if (pRoot-> rChild = = nullptr)PRoot = pRoOt-> lChild;Delete pNode;}}Return pRoot;}
Analysis: the deletion operation is rather complicated and needs to be discussed in different cases. If a node has no children, it can be deleted directly; if a node has a child, the pointer of its parent node needs to be adjustedBypassing the node，Then delete the node; if the node has two children, the general strategy is to use it.The smallest data of the right subtreeReplace the data of the node and delete the node recursively.
【Excerpt
Assuming that P is the node to delete, there are three cases.
（1）pIt is a leaf node.
If P is the parent’s left and right child, the left/right of the p.parent node is empty, that is to delete the P node.
（2）pIt’s a 1 degree node.
Delete the P node and replace the child with P as the parent child.
①If P is the left child of the parents, and P has only the left child, then set P. parent. left pointing to the left child of p, including P is the leaf.
②If P is a parent with children, and P has only right children, then set P. parent. right to point to the right child of p, including P is the leaf.
（3）pIt’s a 2 degree node.
In order to reduce the influence on the morphology of binary search tree, instead of deleting a 2-degree node P directly, the value of the subsequent node Q of P is replaced by the value of the subsequent node Q of P in the middle order, and then the subsequent node q is deleted. In this way, delete the 2 degree node problem to delete the 1 degree node or leaf node. Because q is p.If the right child of P is the leaf node, then q is the right child of p; otherwise q is the leftmost descendant node of the right child of p, and the degree of Q is 0 or 1.
Five. Complete code
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
struct BinaryTreeNode {
int value;
BinaryTreeNode *lChild;
BinaryTreeNode *rChild;
};
/* Create a two fork search tree * /BinaryTreeNode* create (int InOrder[], int PostOrder[], int n){If (InOrder = = nullptr)PostOrder = = nullptr / N = = 0)Return nullptr;BinaryTreeNode *pRoot = new BinaryTreeNode;PRoot-> value = PostOrder[n-1];Int lChildNum = 0, rChildNum = 0;For ((lChildNum <); n; ++lChIldNum) {If (InOrder[lChildNum] = = pRoot-> value)Break;}RChildNum = n - lChildNum - 1;PRoot-> lChild = create (InOrder, PostOrder, lChildNum);PRoot-> rChild = create (InOrder + lC)HildNum + 1, PostOrder + lChildNum, rChildNum);Return pRoot;}/ * sequential traversal of two fork search tree * /Void InOrderTrAverse (BinaryTreeNode *pRoot){If (pRoot) {InOrderTraverse (pRoot-> lChild);Cout < < pROot-> value;InOrderTraverse (pRoot-> rChild);}}/ * query a node * /BinaryTreeNode* find (Binary)TreeNode *pRoot, int x){If (pRoot = = nullptr)Return nullptr;While (pRoot! = nullptr & &am)P; pRoot-> value! = x) {If (pRoot-> value > x)PRoot = pRoot-> lChild;If (pRoot->Value < x)PRoot = pRoot-> rChild;}Return pRoot;}/ * find the minimum element * /BinaryTreeNode* findMin(BinaryTreeNode *pRoot){If (pRoot = = nullptr)Return nullptr;While (pRoot-> lChild! = nullptr)) {PRoot = pRoot-> lChild;}Return pRoot;}/ * find the maximum element * /BinaryTreeNode* findMax (BinaryTree)Node *pRoot){If (pRoot = = nullptr)Return nullptr;While (pRoot-> rChild! = nullptr) {PRoot= pRoot-> rChild;}Return pRoot;}/ * insert operation * /BinaryTreeNode* insert (BinaryTreeNode **pRoot)Int x) / / pRoot is a pointer to the pointer.{If (*pRoot = = nullptr) {*pRoot = new BinaryTreeNode;(*pRoot) ->Value = x;(*pRoot) -> lChild = nullptr;(*pRoot) -> rChild = nullptr;}Else {If (*pRooT) -> value > x)(*pRoot) -> lChild = insert (& ((*pRoot) -> lChild), x);If ((*pRoot) - ≫ value < x)(*pRoot) -> rChild = insert (& ((*pRoot) -> rChild), x);}Return *pRooT;}/ * delete operation * /BinaryTreeNode* DeleteNode (BinaryTreeNode *pRoot, int x){If (pRoot = = nullptr)Return nullptr;If (pRoot-> value > x)PRoot-> lChild = DeleteNode (pRoot-> lChild, x);If (pRoot-> value < x)PRoot-> rChild = DeleteNode (pRoot-> rChild, x);If (pRoot-> value)= = = x) {/ / the deleted node has two children.If (pRoot-> lChild & & pRoot-> rChild) {BinaryTreeNode *Temp = findMin (pRoot-> rChild);PRoot-> value = temp-> value;PRoot-> lChild = DeleteNODE (pRoot-> rChild, x);}/ / the deleted node has zero or one child.Else {BinaryTreeNode *pNode = pRoot;If (PRoot-> lChild = = nullptr)PRoot = pRoot-> rChild;Else if (pRoot-> rChild = = nullptr)PRoot = pRoot-> lChild;Delete pNode;}}Return pRoot;}Int main (){Int InOrd[7] ={1, 2, 3, 4, 6, 8};Int PostOrd[7] = {1, 3, 4, 2, 8, 6};BinaryTreeNode *pTree = create (InOrd, P)OstOrd, 6);Cout < < "hint: the two fork search tree has been created! "< < endl;Cout < < "hint: in order traversal two fork search tree..." < <Endl;InOrderTraverse (pTree);Cout < < endl;BinaryTreeNode *pNode = nullptr;/ / find elementsA node with a value of 4PNode = find (pTree, 4);If (pNode = = nullptr)Cout < < "hint: the node to be searched" does not exist; < < endl;ElseCout < < "hint: the node to be found" has been found "< < endl";/ / insert node with element value 7.PNode = insert (& pTree, 7));Cout < < "hint: the node to be inserted has been inserted" < < endl;Cout < < "hint: in order traversal two fork tree..." < < endl;InOrDerTraverse (pTree);Cout < < endl;/ / delete node with element value 3.PNode = DeleteNode (pTree, 3);Cout < < "prompt: the node to be deleted has been deleted" < < endl;Cout < < "hint: in order traversal two fork tree..." < < endl;InOrderTraverse (PTree);Cout < < endl;Return 0;}
Test results:
【Built two fork search tree]
【Two fork search tree after insertion of node 7
【Delete two node lookup tree after node 3
