我正在使用AVL树，但是在将所有部分连接在一起方面最困难，特别是在涉及到树需要旋转以实现自平衡的情况下。到目前为止，我有向左和向右旋转的功能，以及需要保持这些功能的插入功能。我的方法与我见过的方法不同，例如怪胎，这就是为什么我在这里寻求指导的原因...
这是我的右旋转：
void RightRotate(NODE* Parent, NODE* N)
{
NODE* L = N->Left;
NODE* A = L->Left;
NODE* B = L->Right;
NODE* C = N->Right;
L->Right = N;
N->Left = B;
if(Parent == nullptr){
Root = L;
}
else if (L->Key < Parent->Key){
Parent->Left = L;
}
else{
Parent->Right = L;
}
// 4. Update N's height:
int HA , HB , HC;
if(A == nullptr){
HA = -1;
}
else{
HA = A->Height;;
}
if(B == nullptr){
HB = -1;
}
else{
HB = B->Height;;
}
if(C == nullptr){
HC = -1;
}
else{
HC = C->Height;;
}
N->Height = 1 + max(HB , HC);
L->Height = 1 + max(HA, N->Height);
}// end of rightrotate(...)
与我一起向左旋转：
void LeftRotate(NODE* Parent, NODE* N)
{
NODE* R = N->Right;
NODE* A = N->Left;
NODE* B = R->Left;
NODE* C = R->Right;
//2. Rotate:
R->Left = N;
N->Right = B;
//3. Update Parent to the link:
if(Parent == nullptr){
Root = R;
}
else if(R->Key < Parent->Key){
Parent->Left = R;
}
else{
Parent->Right = R;
}
// Update N's height:
int HA, HB, HC;
if(A == nullptr){
HA = -1;
}
else{
HA = A->Height;
}
if(B == nullptr){
HB = -1;
}
else{
HB = B->Height;
}
if(C == nullptr){
HC = -1;
}
else{
HC = C->Height;
}
N->Height = 1 + max(HA , HB);
R->Height = 1 + max(HC, N->Height);
}
这是我正在使用的插件，需要帮助将所有内容与旋转情况连接在一起]
void insert(TKey key, TValue value)
{
NODE* prev = nullptr;
NODE* cur = Root;
stack<NODE*> nodes;
//
// 1. Search to see if tree already contains key:
//
while (cur != nullptr)
{
if (key == cur->Key) // already in tree
return;
nodes.push(cur); // stack so we can return later:
if (key < cur->Key) // search left:
{
prev = cur;
cur = cur->Left;
}
else
{
prev = cur;
cur = cur->Right;
}
}//while
//
// 2. if we get here, key is not in tree, so allocate
// a new node to insert:
//
NODE* newNode;
newNode = new NODE();
newNode->Key = key;
newNode->Value = value;
newNode->Height = 0; // leaf node -> sub-tree of height 0:
newNode->Left = nullptr;
newNode->Right = nullptr;
//
// 3. link in the new node:
if (prev == nullptr)
Root = newNode;
else if (key < prev->Key)
prev->Left = newNode;
else
prev->Right = newNode;
//
// 4. update size:
//
Size++;
while( !nodes.empty() ){
NODE* cur;
cur = nodes.top();
nodes.pop();
int HL;
int HR;
if(cur->Left == nullptr){
HL = -1;
}
else{
HL = cur->Left->Height;
}
if(cur->Right == nullptr){
HR = -1;
}
else{
HR = cur->Right->Height;
}
int newH = 1 + max(HL,HR);
if(cur->Height == newH){
break;
}
else if( (cur->Height) - (newH) == 1 || (cur->Height) - (newH) == -1 || (cur->Height) - (newH) == 0 ) {
cur->Height = newH; // updates the new height.
continue;
}
else{ // TODO Case conditions:
if(cur->Left->Height > cur->Right->Height){ // case 1 and 2
}
else{ // case 3 and 4
}
}
}// end while
}
用于测试，