Я написал класс двоичного дерева поиска. Но возникла проблема с методами "поворачивающима дерево вокруг узла". Вместо поворота узел, который должен повернуться - удаляется. как решить эту проблему ?(как правильно поворачивать дерево вокруг узла?)
| Код |
using System;
namespace Tree
{
public class TreeNode
{
public int value;
public TreeNode LeftChild;
public TreeNode RightChild;
public TreeNode(int value) { this.value = value; }
public TreeNode() : this(0) { }
}
public class BinarySearchTree
{
public TreeNode root;
public BinarySearchTree() { this.root = null; }
//////////////////////////////////////////////////////////////////////////
//Основные функции
//////////////////////////////////////////////////////////////////////////
/// <summary>
/// функция вставки элемента в дерево
/// </summary>
/// <param name="insert_value"></param>
public void Insert(int insert_value)
{
if (Find(insert_value) == null)
Insert(ref this.root, insert_value);
}
/// <summary>
/// функция удаления элемента из дерева
/// </summary>
/// <param name="deleted_value"></param>
public void Delete(int deleted_value)
{
if (Find(deleted_value) != null)
Delete(ref this.root, deleted_value);
}
/// <summary>
/// функция нахождения элемента в дереве
/// </summary>
/// <param name="find_value"></param>
/// <returns></returns>
public TreeNode Find(int find_value)
{
return Find(this.root, find_value);
}
/// <summary>
/// функции поворота дерева
/// </summary>
/// <param name="rootNode"></param>
public void Left_rotate( ref TreeNode rootNode)
{
TreeNode tmp = rootNode.RightChild;
rootNode.RightChild = tmp.LeftChild;
tmp.LeftChild = rootNode;
rootNode = tmp;
}
public void Right_rotate(ref TreeNode rootNode)
{
TreeNode tmp = rootNode.LeftChild;
rootNode.LeftChild = tmp.RightChild;
tmp.RightChild = rootNode;
rootNode = tmp;
}
/// <summary>
/// функция вычисления высоты дерева
/// </summary>
/// <returns></returns>
public int Height()
{
return Height(this.root);
}
//////////////////////////////////////////////////////////////////////////
//Вспомогательные функции
//////////////////////////////////////////////////////////////////////////
/// <summary>
/// функция удаления элемента
/// </summary>
/// <param name="rootNode"></param>
/// <param name="deleted_value"></param>
private void Delete(ref TreeNode rootNode, int deleted_value)
{
if (rootNode != null)
{
if (deleted_value < rootNode.value)
Delete(ref rootNode.LeftChild, deleted_value);
else if (deleted_value > rootNode.value)
Delete(ref rootNode.RightChild, deleted_value);
else
{
if (rootNode.LeftChild == null && rootNode.RightChild == null)
rootNode = null;
else if (rootNode.LeftChild != null && rootNode.RightChild == null)
rootNode = rootNode.LeftChild;
else if (rootNode.LeftChild == null && rootNode.RightChild != null)
rootNode = rootNode.RightChild;
else // two children
{
if (rootNode.RightChild.LeftChild == null)
{
rootNode.RightChild.LeftChild = rootNode.LeftChild;
rootNode = rootNode.RightChild;
}
else
{
rootNode.value = FindMin(rootNode.RightChild).value;
Delete(ref rootNode.RightChild, rootNode.value);
}
} // two children
} // valu == rootNode.data
} // rootNode != null
}
/// <summary>
/// функция добалвения элемента
/// </summary>
/// <param name="rootNode"></param>
/// <param name="insert_value"></param>
private void Insert(ref TreeNode rootNode, int insert_value)
{
if (rootNode == null)
rootNode = new TreeNode(insert_value);
else if (rootNode.value > insert_value)
Insert(ref rootNode.LeftChild, insert_value);
else //if (rootNode.value < insert_value)
Insert(ref rootNode.RightChild, insert_value);
}
/// <summary>
/// функцияя поиска элемента
/// </summary>
/// <param name="rootNode"></param>
/// <param name="find_value"></param>
/// <returns></returns>
private TreeNode Find(TreeNode rootNode, int find_value)
{
if (rootNode == null)
return null;
else if (rootNode.value > find_value)
return Find(rootNode.LeftChild, find_value);
else if (rootNode.value < find_value)
return Find(rootNode.RightChild, find_value);
else
return rootNode;
}
/// <summary>
/// функция нахождения минимального элемента
/// </summary>
/// <param name="rootNode"></param>
/// <returns></returns>
private TreeNode FindMin(TreeNode rootNode)
{
if (rootNode != null)
{
while (rootNode.LeftChild != null)
rootNode = rootNode.LeftChild;
}
return rootNode;
}
/// <summary>
/// функция нахождения высоты
/// </summary>
/// <param name="rootNode"></param>
/// <returns></returns>
private int Height(TreeNode rootNode)
{
if (rootNode == null)
return 0;
else if (rootNode.LeftChild == null && rootNode.RightChild == null)
return 0;
else
return 1 + Math.Max(Height(rootNode.LeftChild), Height(rootNode.RightChild));
}
}
}
|
|