The following was toss together for the sake of coding up example questions (no testing code written because I would prefer to code up a red-black implementation and that’s an exercise). See one of many examples on the web.
Code Snippet
- using System;
- using System.Collections.Generic;
- using System.Data;
- using System.Linq;
- using System.Text;
- namespace ConsoleApplication1
- {
- public class BSTNode
- {
- /// <summary>
- /// Low Value
- /// </summary>
- public BSTNode LeftNode { get; set;}
- /// <summary>
- /// Low Value
- /// </summary>
- public BSTNode RightNode { get; set; }
- /// <summary>
- /// Value or Object
- /// </summary>
- public int Value { get; set; }
- public object Object { get; set; }
- }
- public class BinarySearchTree
- {
- private BSTNode _Root;
- public BinarySearchTree(BSTNode root)
- {
- _Root = root;
- }
- public BSTNode ExactFind(int lookupvalue)
- {
- if (_Root == null)
- {
- return null;
- }
- var active = _Root;
- while (active != null)
- {
- if (active.Value == lookupvalue)
- {
- break;
- }
- if (active.Value > lookupvalue)
- {
- active = active.LeftNode;
- }
- else // Must be <, no need to test
- {
- active = active.RightNode;
- }
- }
- return active;
- }
- public BSTNode MinValue()
- {
- if (_Root == null)
- {
- return null;
- }
- var active = _Root;
- while (active.LeftNode != null)
- {
- active = active.LeftNode;
- }
- return active;
- }
- public BSTNode MaxValue()
- {
- if (_Root == null)
- {
- return null;
- }
- var active = _Root;
- while (active.RightNode != null)
- {
- active = active.RightNode;
- }
- return active;
- }
- public BSTNode NextNode(BSTNode node)
- {
- if (node == null)
- {
- return MinValue();
- }
- return NextNode(node.Value);
- }
- public BSTNode NextNode(int lookupvalue)
- {
- var path=new Stack<BSTNode>();
- if (_Root == null)
- {
- return null;
- }
- var active = _Root;
- while (true)
- {
- path.Push(active);
- if (active.Value == lookupvalue)
- {
- break;
- }
- if (active.Value > lookupvalue)
- {
- if (active.LeftNode == null)
- return active;
- active = active.LeftNode;
- }
- else // Must be <, no need to test
- {
- if (active.RightNode == null)
- return active;
- active = active.RightNode;
- }
- }
- var last = path.Pop();
- while(last.RightNode==null && path.Count > 0)
- {
- last = path.Pop();
- }
- return last.RightNode;
- }
- /// <summary>
- /// Find the node where a node would be inserted
- /// Not a red-black (balanced tree) implementation
- /// </summary>
- /// <param name="lookupvalue"></param>
- /// <returns></returns>
- public BSTNode ParentFind(int lookupvalue)
- {
- if (_Root == null)
- {
- return null;
- }
- var active = _Root;
- while (active != null)
- {
- if (active.Value == lookupvalue)
- {
- throw new DataException("Node with this value already exists");
- }
- if (active.Value > lookupvalue)
- {
- if(active.LeftNode==null)
- return active;
- active = active.LeftNode;
- }
- else // Must be <, no need to test
- {
- if (active.RightNode == null)
- return active;
- active = active.RightNode;
- }
- }
- return active;
- }
- }
- }
No comments:
Post a Comment