二叉搜索树的构造原理,二叉搜索树题目

引入二叉平衡、搜索树搜索树二叉搜索树二叉平衡树

在搜索树中引入了搜索问题，分为静态搜索和动态搜索。 数据集不变； 静态搜索可以利用二分搜索，二分搜索将一般顺序搜索的时间复杂度从logn降低到log2n。 二分搜索是将搜索的数据事先进行有效的组织并有序化，形成一种称为判定树的结构，相当于将线性搜索过程转化为树的搜索过程，搜索效率是树的高级动态搜索。 数据集发生变化，可以从与搜索同时发生插入的二分搜索中得到启发，不放入数组直接将要素放在树上。 这样，由于树的动态性很强，所以插入、删除操作比线顺序表更简单； 另外，从判定树可知，对于树的节点，也就是数据的组织，树的任何节点的值都可以大于左边子树的节点值，小于右边子树的节点值。 由此，搜索过程也成为当前节点的判断，能够根据大小的比较进行下一步骤的比较，不断缩小搜索范围

双叉搜索树(BST，Binary Search Tree )，也称为双叉排序树或双叉搜索树

非空左子树的所有键值都小于根节点的键值

非空右子树的所有键值都大于根节点的键值

左、右子树均为二叉搜索树

二叉搜索树的搜索操作： Find

首先从根节点返回空树NULL

树非空时，将根节点关键字与x进行比较：

如果x小于根节点键值，则只需在左子树中继续搜索

如果x大于根节点键值，则只需在右子树中继续搜索

如果两者的比较结果相等，则搜索完成，返回指向该节点的指针

/*二叉搜索树的递归搜索操作*/bitreefind(elementtypex，BiTree BST ) if (！ BST )返回空值； if(xBST-data )返回查找(BST-right )； /*递归右子树*/elseif(xBST-data ) return find (BST-left )； /*递归查找左侧子树*/elsereturn BST； /*检索成功，返回节点地址*/}由于非递归函数的执行效率高，所以可以将递归函数变更为迭代函数

/*二叉搜索树的迭代搜索操作*/bitreefind(elementtypex，BiTree BST ) while ) BST ) if ) xBST-data ) BST=BST-right； /*转到右子树，单击*/elseif(xBST-data ) BST=BST-left； /*移至左侧子树，继续搜索*/elsereturn BST； /*搜索成功*/}返回空值； /*搜索失败*/}另外，搜索效率依赖于树的高度(二叉树的平衡)

寻找最大、最小元素的最大元素一定在树的最右边枝端节点

bitreefindmax(bitreeBST ) if (！ BST )返回空值； else if (！ BST-right (返回BST； /*找到了最右边的节点。 返回*/elsereturnfindmin(BST-right )/*并沿着右分支*/)最小元素必须位于树的最左分支的端节点上

bitreefindmin(bitreeBST ) if ) BST ) while ) BST-left ) BST=BST-right； /*沿着右分支，到最右边节点*/return BST )插入二叉搜索树的关键是找到要插入元素的位置

bitreeinsert(bitreeBST，ElementType X ) if (！ BST ()/*当原始树为空时，生成一个节点并返回的双叉搜索树(/BST=(bitree ) malloc ) sizeof ) structbitnode )； BST-Data=X； BST-Left=BST-Right=NULL； }开始寻找要插入} else { /*元素的位置*/if(xBST-data ) BST-left=insert(BST-left，x )。 /*递归插入左侧子树*/elseif(xBST-data ) BST-right=insert ) BST-right，x )/*递归插入右侧子树*//* else X已经)删除双叉搜索树

首先找到要删除的节点的位置，考虑三种情况

要删除的是叶节点。 直接删除并修改父节点的指针。 设置为空

r> ②要删除的结点只有一个孩子结点：将其父结点的指针指向要删除结点的孩子结点
③要删除的结点有左、右两棵子树：用另一结点（相邻大小）替代被删除的结点 - - 右子树的最小元素 或 左子树的最大元素 BiTree Delete( BiTree BST, ElementType X ) { BiTree Temp; if( !BST ) printf("要删除的元素未找到"); else { if( X Data ) BST->Left = Delete( BST->Left, X ); /* 从左子树递归删除 */ else if( X > BST->Data ) BST->Right = Delete( BST->Right, X ); /* 从右子树递归删除 */ else { /* BST就是要删除的结点 */ /* 如果被删除结点有左右两个子结点 */ if( BST->Left && BST->Right ) { /* 从右子树中找最小的元素填充删除结点 */ Temp = FindMin( BST->Right ); BST->Data = Temp->Data; /* 再从右子树中删除最小元素 */ BST->Right = Delete( BST->Right, BST->Data ); } /* 被删除结点有一个或无子结点 */ else { Temp = BST; /* Temp用于记住将要释放的内存 */ if( !BST->Left ) /* 只有右孩子或无子结点 */ BST = BST->Right; else /* 只有左孩子 */ BST = BST->Left; free( Temp ); } } } return BST;} 二叉平衡树 树的查找效率取决于树的深度二叉搜索树结点的不同插入顺序，会得到树的不同深度，导致树的平均查找长度 ASL 不同，也即搜索树的查找效率不一完全二叉树的深度为 log2n引入平衡因子（ Balance Factor ，简称 BF ) ：BF = hL - hR（ hL、hR 分别为左、右子树高度）平衡二叉树（ AVL 树 ) 是空树，或者任一结点左、右二叉子树的高度差的绝对值不超过 1，即 | BF | <= 1平衡二叉树的高度可以达到 log2n

二叉平衡树的调整

typedef struct AVLNode *AVLNode;struct AVLNode{ ElementType Data; /* 结点数据 */ AVLTree Left; /* 指向左子树 */ AVLTree Right; /* 指向右子树 */ int Height; /* 树高 */}AVLTree;

①左单旋

AVLTree SingleLeftRotation ( AVLTree A ){ /* 注意：A必须有一个左子结点B */ /* 将A与B做左单旋，更新A与B的高度，返回新的根结点B */ AVLTree B = A->Left; A->Left = B->Right; B->Right = A; A->Height = Max( GetHeight(A->Left), GetHeight(A->Right) ) + 1; B->Height = Max( GetHeight(B->Left), A->Height ) + 1; return B;}

②右单旋

AVLTree SingleRightRotation ( AVLTree A ){ /* 注意：A必须有一个右子结点B */ /* 将A与B做右单旋，更新A与B的高度，返回新的根结点B */ AVLTree B = A->Right; A->Right = B->Left; B->Left = A; A->Height = Max( GetHeight(A->Left), GetHeight(A->Right) ) + 1; B->Height = Max( GetHeight(B->Left), A->Height ) + 1; return B;}

③左、右双旋

AVLTree DoubleLeftRightRotation ( AVLTree A ){ /* 注意：A必须有一个左子结点B，且B必须有一个右子结点C（原有或新插入） */ /* 将A、B与C做两次单旋，返回新的根结点C */ /* 将B与C做右单旋，C被返回 */ A->Left = SingleRightRotation(A->Left); /* 将A与C做左单旋，C被返回 */ return SingleLeftRotation(A);}

④右、左双旋

AVLTree DoubleRightLeftRotation ( AVLTree A ){ /* 注意：A必须有一个左子结点B，且B必须有一个右子结点C（原有或新插入） */ /* 将A、B与C做两次单旋，返回新的根结点C */ /* 将B与C做左单旋，C被返回 */ A->Right = SingleLeftRotation(A->Left); /* 将A与C做右单旋，C被返回 */ return SingleRightRotation(A);}

二叉平衡树的插入

AVLTree Insert( AVLTree T, ElementType X ){ /* 将X插入AVL树T中，并且返回调整后的AVL树 */ /* 插入空树，则相当于新建包含一个结点的树 */ if ( T == NULL ) { T = (AVLTree)malloc(sizeof(struct AVLNode)); T->Data = X; T->Height = 0; T->Left = T->Right = NULL; } /* 插入T的左子树 */ else if ( X Data ) { T->Left = Insert( T->Left, X); /* 如果需要左旋 */ if ( GetHeight(T->Left) - GetHeight(T->Right) == 2 ) if ( X Left->Data ) T = SingleLeftRotation(T); /* 左单旋 */ else T = DoubleLeftRightRotation(T); /* 左-右双旋 */ } /* 插入T的右子树 */ else if ( X > T->Data ) { T->Right = Insert( T->Right, X ); /* 如果需要右旋 */ if ( GetHeight(T->Left) - GetHeight(T->Right) == -2 ) if ( X > T->Right->Data ) T = SingleRightRotation(T); /* 右单旋 */ else T = DoubleRightLeftRotation(T); /* 右-左双旋 */ } /* else X == T->Data，无须插入 */ /* 更新树高 */ T->Height = Max( GetHeight(T->Left), GetHeight(T->Right) ) + 1; return T;}